MathDB

We play a game of musical chairs with

n

chairs numbered

1

n

. You attach

n

leaves, numbered

1

n

, to the chairs in such a way that the number on a leaf does not match the number on the chair it is attached to. One player sits on each chair. Every time you clap, each player looks at the number on the leaf attached to his current seat and moves to sit on the seat with that number. Prove that, for any

m

that is not a prime power with

1 < m \leq n

, it is possible to attach the leaves to the seats in such a way that after

m

claps everyone has returned to the chair they started on for the first time.

Problem Statement