Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# 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$,

 $\displaystyle m$ $\displaystyle m+\big[\tfrac{m}3\big]+\big[\tfrac{m}6\big]+1$ number of cycles $\displaystyle 12s+1$ $\displaystyle 18s+2$ even $\displaystyle 12s+2$ $\displaystyle 18s+3$ odd $\displaystyle 12s+4$ $\displaystyle 18s+6$ even $\displaystyle 12s+5$ $\displaystyle 18s+7$ odd $\displaystyle 12s+7$ $\displaystyle 18s+11$ odd $\displaystyle 12s+8$ $\displaystyle 18s+12$ even $\displaystyle 12s+10$ $\displaystyle 18s+15$ odd $\displaystyle 12s+11$ $\displaystyle 18s+16$ even

### 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