## May 2017 riddle

UPDATE (5 May): Here is another basic theorem in group theory you might find useful. If G is a finite group and H is a subgroup of it (a subset of the elements, with the same group operation, that also forms a group), then |H| divides |G|. This is known as Lagrange's theorem, and is most often used when H is the group {1, x, x2,...} for some x in G.

UPDATE (3 May): You may find the following basic theorem in group theory, known as Cauchy's theorem, to be useful: if G is a finite group over a set of size n, and p is a prime divisor of n, then G has an element, w, not equal to the identity, such that wp is the identity. (The theorem is usually worded somewhat differently, but was simplified here.)

This month's riddle comes from Serge Gautier. (Thanks, Serge!) It extends one of the very earliest Using your Head is Permitted riddles (December 2007), which is a personal favourite of mine, and one that has already been extended once (in June 2010).

A group is a set, S, and a binary operation, "*" over it. (Here, "binary" just means it acts on two elements, as in x*y.) The result of x*y for any x, y in S must also be in S. The operation must also satisfy the following conditions:

• Associativity: For every x, y, z in S, x*(y*z)=(x*y)*z.
• Identity: There exists an element, i in S, such that for every x in S, x*i=i*x=x. This is known as the group's identity element. (It is necessarily unique.)
• Inverse element: For every x in S there exists a y in S such that x*y=y*x=i, the identity element.

A group is called abelian if it furthermore satisfies commutativity: for every x, y in S, x*y=y*x.

Traditionally, the group operation of abelian groups is denoted "+".

We now repeat the December 2007 riddle:

Let n>1 be an integer, let S be the set of numbers {0, 1, ... , n-1} and let A, B and C be one-to-one functions to and from S.

#### Part 1:

For which values of n is it possible to find such A, B and C satisfying that for all x in S, A(x)+B(x)=C(x)?

#### Part 2:

For which values of n is it possible to find such A, B and C satisfying that for all x in S, A(x)*B(x)=C(x)?

The only difference from the original riddle is that now we are asking this question not only over standard multiplication and standard addition, but over any group operation "*" in Part 2 and any abelian group operation "+" in Part 1.

In other words, you are to answer whether for each possible choice of n one can find not only A, B and C, but also a corresponding group, to satisfy the equalities. The only constraint imposed on the group is that its underlying set should be S. (Note that i may be any element in S.)

A separate list of solvers will be kept for each of the two parts. Answer either or both.

### List of solvers:

#### Part 1:

JJ Rabeyrin (1 May 20:14)
Harald Bögeholz (3 May 12:24)
Uoti Urpala (3 May 12:38)
Lian Wang (3 May 19:06)
Hanlin Ren (3 May 21:33)
Jens Voss (4 May 16:07)
Dan Dima (5 May 03:52)
Lin Jin (9 May 14:06)
Oscar Volpatti (30 May 00:02)

#### Part 2:

Uoti Urpala (3 May 12:38)
Lian Wang (3 May 19:06)
Hanlin Ren (3 May 21:33)
Jens Voss (4 May 16:07)
JJ Rabeyrin (8 May 07:34)
Lin Jin (9 May 14:06)
Harald Bögeholz (23 May 10:50)

Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!