MathDB
The PMO Magician

Source: Philippine MO 2022/2

March 18, 2022
number theorycombinatoricspermutationsPMO

Problem Statement

The PMO Magician has a special party game. There are nn chairs, labelled 11 to nn. There are nn sheets of paper, labelled 11 to nn.
[*] On each chair, she attaches exactly one sheet whose number does not match the number on the chair. [*] She then asks nn 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≤n1 < m \leq n, where mm 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 mm claps.
Back to ProblemsView on AoPS