2006 Canadian Computing Competition, Stage 1

Problem S4: Groups

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

  • Associativity: For all x, y, and z in G, x × (y × z) = (x × y) × z.
  • Identity: the group contains an “identity element” (we can use i) so that for each x in G, x × i = x and i × x = x.
  • Inverse: for every element x there is an inverse element (we denote by x-1) so that x × x-1 = i and x-1 × 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 (0 is the identity, and the inverse of x is -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 10 under the operation addition.

That is, the group consists of the integers 0, 1, ..., 9 and the operation is to add two keeping only the least significant digit. Here the identity is 0. This particular group has the property that x × y = y × x, but this is not always the case. Consider the group that consists of the elements a, b, c, d, e and i. The “multiplication table” below defines the operations. Note that each of the required properties is satisfied (associativity, identity and inverse) but, for example, c × d = a while d × c = b.

× i a b c d e
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

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

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

Output

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 = 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 × (2 × 2) = 3 × 1 = 3 but (3 × 2) × 2 = 1 × 2 = 2. In the last candidate, there is no identity, since 1 is not the identity, since 2 × 1 = 3 (not 2), and 2 is not the identity, since 1 × 3 = 3 (not 1).

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Can someone explain how that works?

Exactly as stated. If x, y, and z are three elements of a group, then (x*y)*z = x*(y*z) - that is, it doesn't matter what order you do operations in, as long as what is on the left of a multiplication sign stays on the left and what is on the right stays on the right.

What does z represent?

If x, y, and z are three elements of a group, then (x*y)*z = x*(y*z)
That is, associativity is the statement that this holds true no matter how you select x, y, and z: they may be any elements whatsoever of the group.