CCC '06 S4 - Groups - DMOJ: Modern Online Judge

CCC '06 S4 - Groups

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2006 Stage 1, Senior #4

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

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

That is, the group consists of the integers $0, 1, \dots, 9$ ~0, 1, \dots, 9~ and the operation is to add two keeping only the least significant digit. Here the identity is $0$ ~0~. This particular group has the property that $x \times y = y \times x$ ~x \times y = y \times x~, but this is not always the case. Consider the group that consists of the elements $a$ ~a~, $b$ ~b~, $c$ ~c~, $d$ ~d~, $e$ ~e~ and $i$ ~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 \times d = a$ ~c \times d = a~ while $d \times c = b$ ~d \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}$

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 $n$ ~n~ $(0 \le n \le 100)$ ~(0 \le n \le 100)~. If the test case begins with $n = 0$ ~n = 0~, the program terminates. To simplify the input, we will use the integers $1, \dots, n$ ~1, \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 $1$ ~1~). Following the number $n$ ~n~ in each test case are $n$ ~n~ 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 q$ ~p \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 = 0$ ~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 \times (2 \times 2) = 3 \times 1 = 3$ but $(3 \times 2) \times 2 = 1 \times 2 = 2$ . In the last candidate, there is no identity, since $1$ ~1~ is not the identity, since $2 \times 1 = 3$ ~2 \times 1 = 3~ (not $2$ ~2~), and $2$ ~2~ is not the identity, since $2 \times 1 = 3$ ~2 \times 1 = 3~ (not $1$ ~1~) and $3$ ~3~ is not the identity, since $1 \times 3 = 3$ ~1 \times 3 = 3~ (not $1$ ~1~).

Comments

-5

georgezhang006 commented on July 28, 2020, 4:47 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

1

littlecat commented on Aug. 11, 2020, 5: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.)

3

sushi commented on June 29, 2020, 9:44 p.m.

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

The $i$ ~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)$ ~(x \times y)~ is equivalent as the element at position $(x, y)$ ~(x, y)~ in the grid.

An identity element could be $0$ ~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.

1

littlecat commented on Aug. 11, 2020, 6:18 p.m. ← edited →

In the input specification, the elements are given as $1$ ~1~ to $n$ ~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)$ ~(a, b, c)~ for the associativity, so that the solution would take $\mathcal{O}(n^3)$ ~\mathcal{O}(n^3)~ time. In C++, a vector<vector<int>> also works for recording the function definition.