Problem

Source: Philippine MO 2022/2

Tags: number theory, combinatorics, permutations, PMO



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.