Problem A. 734. (November 2018)

A. 734. For an arbitrary positive integer \(\displaystyle m\), not divisible by \(\displaystyle 3\), consider the permutation \(\displaystyle x\mapsto 3x\pmod{m}\) on the set \(\displaystyle \{1,2,\ldots,m-1\}\). This permutation can be decomposed into disjoint cycles; for instance, for \(\displaystyle m=10\) the cycles are \(\displaystyle (1\mapsto3\mapsto9\mapsto7\mapsto1)\), \(\displaystyle (2\mapsto6\mapsto8\mapsto4\mapsto2)\) and \(\displaystyle (5\mapsto5)\). For which integers \(\displaystyle m\) is the number of cycles odd?

(7 pont)

Deadline expired on December 10, 2018.

Solution (outline). We will use some basic facts about parities of permutations.

Let \(\displaystyle \pi(x)=3x\pmod m\). Suppose that the number of cycles is \(\displaystyle c\), the length of the cycles are \(\displaystyle k_1,k_2,\ldots,k_c\); in the example we had \(\displaystyle m=10\), \(\displaystyle c=3\), \(\displaystyle k_1=k_2=4\) and \(\displaystyle k_3=1\). Each of \(\displaystyle 1,2,\ldots,m-1\) appears exactly in one cycle, so \(\displaystyle k_1+\ldots+k_c=m-1\).

Every cycle \(\displaystyle (x_1\mapsto x_2\mapsto\ldots\mapsto x_k\mapsto x_1)\) is the product of the transpositions \(\displaystyle (x_1,x_2), (x_2,x_3) \ldots, (x_{k-1},x_k)\); the permutation \(\displaystyle \pi\) is the product of altogether \(\displaystyle (k_1-1)+(k_2-1)+\ldots+(k_c-1)=m-c-1\) transpositions. So \(\displaystyle \pi\) is odd if and only if \(\displaystyle m-c-1\) is odd.

In order to determine the parity of \(\displaystyle \pi\), define

\(\displaystyle I = \big\{ (x,y): x<y, ~\text{and}~ \pi(x)>\pi(y) \big\}, \)

the set of inversions, i.e. pairs \(\displaystyle (x,y)\) with \(\displaystyle 1\le x<y\le m-1\) and \(\displaystyle \pi(x)>\pi(y)\). We want to determine the parity of \(\displaystyle |I|\).

Split \(\displaystyle I\) into three disjoins subsets:

\(\displaystyle A = \big\{ (x,y): ~ x<y, ~ \pi(x)>\pi(y) ~\text{and}~ x+y<m \big\}, \)

\(\displaystyle B = \big\{ (x,y): ~ x<y, ~ \pi(x)>\pi(y) ~\text{and}~ x+y>m \big\}, \)

\(\displaystyle C = \big\{ (x,m-x): ~ x<\tfrac{m}{2} ~\text{and}~ \pi(x)>\pi(m-x) \big\}. \)

Claim 1. The map \(\displaystyle (x,y)\mapsto (m-y,m-x)\) is a bjection between \(\displaystyle A\) and \(\displaystyle B\), therefore \(\displaystyle |A|=|B|\).

Proof: Notice that \(\displaystyle \pi(x)+\pi(m-x)\equiv3x+3(m-x)\equiv0\pmod{m}\). Due to \(\displaystyle 0<\pi(x)+\pi(m-x)<2m\), this yields \(\displaystyle \pi(x)+\pi(m-x)=m\).

For any \(\displaystyle (x,y)\in A\) we have \(\displaystyle m-y<m-x\) and \(\displaystyle (m-y)+(m-x)>m\), moreover \(\displaystyle \pi(m-y)=m-\pi(y)>m-\pi(x)=\pi(m-x)\), so indeed \(\displaystyle (m-y,m-x)\in B\). The opposite direction can be in the same way.

Claim 2. \(\displaystyle C=\big\{(x,m-x): \tfrac{m}{6}<x<\tfrac{m}3 \big\}\), therefore \(\displaystyle |C|=\big[\tfrac{m}3\big]-\big[\tfrac{m}6\big]\).

Proof: If \(\displaystyle 0<x<\tfrac{m}{6}\) then \(\displaystyle \pi(x)=3x<m-3x=\pi(m-x)\), so \(\displaystyle (x,m-x)\notin C\).

If \(\displaystyle \tfrac{m}{6}<x<\tfrac{m}{3}\) then \(\displaystyle \pi(x)=3x>m-3x=\pi(m-x)\), therefore \(\displaystyle (x,m-x)\in C\).

Finally, if \(\displaystyle \tfrac{m}{3}<x<\tfrac{m}{2}\) then \(\displaystyle \pi(x)=3x-m<2m-3x=\pi(m-x)\), so \(\displaystyle (x,m-x)\notin C\).

Now we have two formula for the parity of \(\displaystyle \pi\): it matches the parities of both \(\displaystyle m-c-1\), and \(\displaystyle |I|\). Hence, \(\displaystyle m-c-1\equiv |I|\equiv |C|=\big[\tfrac{m}3\big]-\big[\tfrac{m}6\big]\pmod{2}\); for the number of cycles we obtain

\(\displaystyle c \equiv m+\big[\tfrac{m}3\big]+\big[\tfrac{m}6\big]+1 \pmod{2}. \)

Separating the cases by the modulo \(\displaystyle 12\) remainder of \(\displaystyle m\),

Statistics:

8 students sent a solution.
7 points:	Molnár Bálint, Schrettner Jakab, Szabó 417 Dávid, Szabó Kristóf.
5 points:	1 student.
1 point:	1 student.
0 point:	2 students.

Problems in Mathematics of KöMaL, November 2018