AoPS - Problem

Source: Philippine MO 2022/2

Tags: number theory, combinatorics, permutations, PMO

InternetPerson10

18.03.2022 07:49

The PMO Magician has a special party game. There are $n$ chairs, labelled $1$ to $n$. There are $n$ sheets of paper, labelled $1$ to $n$. On each chair, she attaches exactly one sheet whose number does not match the number on the chair. She then asks $n$ party guests to sit on the chairs so that each chair has exactly one occupant. Whenever she claps her hands, each guest looks at the number on the sheet attached to their current chair, and moves to the chair labelled with that number. Show that if $1 < m \leq n$, where $m$ is not a prime power, it is always possible for the PMO Magician to choose which sheet to attach to each chair so that everyone returns to their original seats after exactly $m$ claps.

Really, the problem is asking for us to create a bunch of cycles (of length $\ge 2$) on $n$ vertices such that every vertex is part of exactly one cycle and such that the lcm of cycle lengths is $m$. If $m$ is not a prime power, say its $m = st$ where $s,t$ are coprime and $> 1$, since $m > st - s - t$, there exist nonnegative integers $x,y$ so that $n = sx + ty$ by the chicken mc nugget theorem. Take $x$ cycles of length $s$ and $y$ cycles of length $t$ so the lcm of cycle lengths is indeed $m$ and we use all $n$ vertices. In fact, if $m$ was a prime power of a prime say $p^k$ with $p$ not dividing $n$, then clearly this is not possible since each cycle length must be divisible by $p$ but $n$ is not. But if we had $p | n$, then take a cycle of length $p^k$, then $\frac{n-p^k}{p}$ cycles of length $p$, which works. thanks @below - fixed now