Maths Olympiad Prep

Library / /21 of 23

Algebra Difficulty 7.3 National Olympiad, round 2 Prove it Romania

Let (G,)(G, \cdot) be a finite group of order nNn \in \mathbb{N}^*, with n2n \ge 2. We shall call the group (G,)(G, \cdot) arrangeable if there is an ordering of its elements, such that
G={a1,a2,,ak,,an}={a1a2,a2a3,,akak+1,,ana1}. G = \{a_1, a_2, \dots, a_k, \dots, a_n\} = \{a_1 \cdot a_2, a_2 \cdot a_3, \dots, a_k \cdot a_{k+1}, \dots, a_n \cdot a_1\}.

a) Determine all positive integers nn for which the group (Zn,+)(\mathbb{Z}_n, +) is arrangeable.

b) Give an example of an arrangeable group of even order.

Solution

a. We will show that the group (Zn,+)(\mathbb{Z}_n, +) is arrangeable if and only if n2n \ge 2 is an odd positive integer.

If (G,)(G, \cdot) is an abelian arrangeable group, then considering the arrangement G={a1,a2,,ak,,an}={a1a2,a2a3,,akak+1,,ana1}G = \{a_1, a_2, \dots, a_k, \dots, a_n\} = \{a_1 \cdot a_2, a_2 \cdot a_3, \dots, a_k \cdot a_{k+1}, \dots, a_n \cdot a_1\}, we have
gGg=k=1nak=k=1n(akak+1)=(gGg)2, \prod_{g \in G} g = \prod_{k=1}^{n} a_k = \prod_{k=1}^{n} (a_k \cdot a_{k+1}) = \left( \prod_{g \in G} g \right)^2,
(where an+1=a1a_{n+1} = a_1), so that gGg=1\prod_{g \in G} g = 1, where 11 is the unit element of the group (G,)(G, \cdot).

In any finite abelian group the product of all the elements is equal to the product of all its elements of order 22.

For nNn \in \mathbb{N}^*, n2n \ge 2, if k{0,1,,n1}k \in \{0, 1, \dots, n-1\} with ord(k^)=2\mathrm{ord}(\hat{k}) = 2, then
k^0^=k^+k^=2k^, \hat{k} \neq \hat{0} = \hat{k} + \hat{k} = 2\hat{k},
so that nn divides 2k2k, but does not divide kk. This is only possible if nn is even and n=2kn = 2k. Thus, if nn is even, with n=2kn = 2k, and (Zn,+)(\mathbb{Z}_n, +) were arrangeable, we would have
0^=xZnx=k^, \hat{0} = \sum_{x \in \mathbb{Z}_n} x = \hat{k},
which is false. Hence, if nn is even, the group (Zn,+)(\mathbb{Z}_n, +) is not arrangeable.

Let now n3n \ge 3 be an odd positive integer. We consider the set [0,n1]N={0,1,,n1}[0, n-1]_N = \{0, 1, \dots, n-1\} and the function f:[0,n1]NZnf : [0, n-1]_N \to \mathbb{Z}_n, defined by f(k)=2k+1f(k) = \overline{2k+1}.

Since
f(k)=f(l)    2k+1=2l+1    n(2k2l)    n(kl)    k=l, f(k) = f(l) \iff \overline{2k+1} = \overline{2l+1} \iff n|(2k-2l) \iff n|(k-l) \iff k=l,
the function ff is injective and since [0,n1]N[0, n-1]_N and Zn\mathbb{Z}_n are finite sets with equal cardinals, it follows that ff is bijective. Denoting ak=k1a_k = \overline{k-1} for any 1kn1 \le k \le n and an+1=a1a_{n+1} = a_1, it follows then that ak+ak+1=f(k1)a_k + a_{k+1} = f(k-1) for any k=1,nk = \overline{1, n}, so that Zn={a1,a2,,an}={f(0),f(1),,f(k),,f(n1)}={a1+a2,a2+a3,,ak1+ak,,an+a1}\mathbb{Z}_n = \{a_1, a_2, \dots, a_n\} = \{f(0), f(1), \dots, f(k), \dots, f(n-1)\} = \{a_1 + a_2, a_2 + a_3, \dots, a_{k-1} + a_k, \dots, a_n + a_1\}, whence we deduce that the group (Zn,+)(\mathbb{Z}_n, +) is arrangeable.

The set of all positive integers such that the group (Zn,+)(\mathbb{Z}_n, +) is arrangeable is thus the set of all odd positive integers nn, with n3n \ge 3.

b. According to part a), there are no cyclic arrangeable groups of even order. We consider Z4={0^,1^,2^,3^}\mathbb{Z}_4 = \{\hat{0}, \hat{1}, \hat{2}, \hat{3}\}, Z2={0,1}\mathbb{Z}_2 = \{\overline{0}, \overline{1}\} and the group G=Z4×Z2G = \mathbb{Z}_4 \times \mathbb{Z}_2 with component-wise defined addition (k^,l^)+(m^,n^)=(k+m,l+n)(\hat{k}, \hat{l}) + (\hat{m}, \hat{n}) = (\overline{k+m}, \overline{l+n}). Then G={a1=(0^,0),a2=(1^,0ˉ),a3=(1^,1ˉ),a4=(3^,1ˉ),a5=(2^,0ˉ),a6=(2^,1ˉ),a7=(0ˉ,1ˉ),a8=(3^,0ˉ)}={a1+a2,a2+a3,a3+a4,a4+a5,a5+a6,a6+a7,a7+a8,a8+a1}G = \{a_1 = (\hat{0}, \overline{0}), a_2 = (\hat{1}, \bar{0}), a_3 = (\hat{1}, \bar{1}), a_4 = (\hat{3}, \bar{1}), a_5 = (\hat{2}, \bar{0}), a_6 = (\hat{2}, \bar{1}), a_7 = (\bar{0}, \bar{1}), a_8 = (\hat{3}, \bar{0})\} = \{a_1+a_2, a_2+a_3, a_3+a_4, a_4+a_5, a_5+a_6, a_6+a_7, a_7+a_8, a_8+a_1\}, so that (G,+)(G, +) is an arrangeable group of order 88.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.