CCC '06 S4 - Groups

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem type
Canadian Computing Competition: 2006 Stage 1, Senior #4

In mathematics, a group, GG, is an object that consists of a set of elements and an operator (which we will call \times\times) so that if xx and yy are in GG so is x \times yx \times y. Operations also have the following properties:

  • Associativity: For all xx, yy and zz in GG, x \times (y \times z) = (x \times y) \times zx \times (y \times z) = (x \times y) \times z.
  • Identity: the group contains an "identity element" (we can use ii) so that for each xx in GG, x \times i = xx \times i = x and i \times x = xi \times x = x.
  • Inverse: for every element xx there is an inverse element (we denote by x^{-1}x^{-1}) so that x \times x^{-1} = ix \times x^{-1} = i and x^{-1} \times x = ix^{-1} \times x = i.

Groups have a wide variety of applications including the modeling of quantum states of an atom and the moves in solving a Rubik's cube puzzle. Clearly, the integers under addition from a group (00 is the identity, and the inverse of xx is -x-x, and you can prove associativity as an exercise), though that group is infinite and this problem will deal only with finite groups.

One simple example of a finite group is the integers modulo 1010 under the operation addition.

That is, the group consists of the integers 0, 1, \dots, 90, 1, \dots, 9 and the operation is to add two keeping only the least significant digit. Here the identity is 00. This particular group has the property that x \times y = y \times xx \times y = y \times x, but this is not always the case. Consider the group that consists of the elements aa, bb, cc, dd, ee and ii. The "multiplication table" below defines the operations. Note that each of the required properties is satisfied (associativity, identity and inverse) but, for example, c \times d = ac \times d = a while d \times c = bd \times c = b.

\displaystyle \begin{array}{c|cccccc}
\times & i & a & b & c & d & e \\\hline
i & i & a & b & c & d & e \\
a & a & i & d & e & b & c \\
b & b & e & i & d & c & a \\
c & c & d & e & i & a & b \\
d & d & c & a & b & e & i \\
e & e & b & c & a & i & d \end{array}\displaystyle \begin{array}{c|cccccc}
\times & i & a & b & c & d & e \\\hline
i & i & a & b & c & d & e \\
a & a & i & d & e & b & c \\
b & b & e & i & d & c & a \\
c & c & d & e & i & a & b \\
d & d & c & a & b & e & i \\
e & e & b & c & a & i & d \end{array}

Your task is to write a program which will read a sequence of multiplication tables and determine whether each structure defined is a group.

Input Specification

The input will consist of a number of test cases. Each test case begins with an integer nn (0 \le n \le 100)(0 \le n \le 100). If the test case begins with n = 0n = 0, the program terminates. To simplify the input, we will use the integers 1, \dots, n1, \dots, n to represent elements of the candidate group structure; the identity could be any of these (i.e., it is not necessarily the element 11). Following the number nn in each test case are nn lines of input, each containing integers in the range [1, \dots, n][1, \dots, n]. The q^{th}q^{th} integer on the p^{th}p^{th} line of this sequence is the value p \times qp \times q.

Output Specification

If the object is a group, output yes (on its own line), otherwise output no (on its own line). You should not output anything for the test case where n = 0n = 0.

Sample Input

2
1 2
2 1
6
1 2 3 4 5 6
2 1 5 6 3 4
3 6 1 5 4 2
4 5 6 1 2 3
5 4 2 3 6 1
6 3 4 2 1 5
7
1 2 3 4 5 6 7
2 1 1 1 1 1 1
3 1 1 1 1 1 1
4 1 1 1 1 1 1
5 1 1 1 1 1 1
6 1 1 1 1 1 1
7 1 1 1 1 1 1
3
1 2 3
3 1 2
3 1 2
0

Sample Output

yes
yes
no
no

Explanation

The first two collections of elements are in fact groups (that is, all properties are satisfied). For the third candidate, it is not a group, since 3 \times (2 \times 2) = 3 \times 1 = 33 \times (2 \times 2) = 3 \times 1 = 3 but (3 \times 2) \times 2 = 1 \times 2 = 2(3 \times 2) \times 2 = 1 \times 2 = 2. In the last candidate, there is no identity, since 11 is not the identity, since 2 \times 1 = 32 \times 1 = 3 (not 22), and 22 is not the identity, since 2 \times 1 = 32 \times 1 = 3 (not 11) and 33 is not the identity, since 1 \times 3 = 31 \times 3 = 3 (not 11).

CCC problem statements in large part from the PEG OJ


Comments


  • -3
    georgezhang006  commented on July 28, 2020, 12:47 p.m.

    Are the Operators +, -, *, / only or does it include %(mod)?


    • 0
      littlecat  commented on Aug. 11, 2020, 1:00 p.m. edited

      The operators are simply 2 variable functions, not necessarily arithmetic functions. For example, in the 6 element group (iabcde), there is no mapping of the elements to (1,2,3,4,5,6) with an arithmetic function. (I think it is isomorphic to the group of symmetries of a triangle as well as the group of permutations with 3 elements.)


  • 2
    sushi  commented on June 29, 2020, 5:44 p.m.

    For those that are a bit confused about this problem, I have a few tips:

    The i described in the inverse definition is actually the identity element described in the identity definition, they are the same variable.

    The grid is a times table, so a hint would be that (x \times y) is equivalent as the element at position (x, y) in the grid.

    An identity element could be 0 as hinted in the problem statement, use indexes as the elements to cover that case.

    This problem is surprisingly annoying, and I hope this helps.


    • 0
      littlecat  commented on Aug. 11, 2020, 2:18 p.m.

      In the input specification, the elements are given as 1 to n, so the elements can be used directly without indexes. I think there is no way to solve the problem without testing all triples (a, b, c) for the associativity, so that the solution would take O(n^3) time. In C++, a vector<vector<int>> also works for recording the function definition.


  • -9
    Beautiful_Times  commented on Feb. 9, 2018, 9:50 p.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.