CCC '06 S4 - Groups

View as PDF

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

Problem type
2006 Canadian Computing Competition, Stage 1

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

• Associativity: For all , and in , .
• Identity: the group contains an "identity element" (we can use ) so that for each in , and .
• Inverse: for every element there is an inverse element (we denote by ) so that and .

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 ( is the identity, and the inverse of is , 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 under the operation addition.

That is, the group consists of the integers and the operation is to add two keeping only the least significant digit. Here the identity is . This particular group has the property that , but this is not always the case. Consider the group that consists of the elements , , , , and . The "multiplication table" below defines the operations. Note that each of the required properties is satisfied (associativity, identity and inverse) but, for example, while .

× 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 Specification

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

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 .

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

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

CCC problem statements in large part from the PEG OJ