Maths Olympiad Prep

Library / /9 of 10

Algebra Difficulty 8.8 Shortlist Prove it Netherlands

We play a game of musical chairs with nn chairs numbered 11 to nn. You attach nn leaves, numbered 11 to nn, 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 mm that is not a prime power with 1<mn1 < m \le n, it is possible to attach the leaves to the seats in such a way that after mm claps everyone has returned to the chair they started on for the first time.

Solution

If m=nm = n, then attach to chair ii the leaf with number i+1i+1. Everyone then moves up a chair every clap and for everyone, the first time they return to the chair they started on is after nn claps. So after nn claps for the first time, everyone has returned to the chair they started on. Now suppose m<nm < n.

Since mm is not a prime power, we can write mm as m=km = k\ell with gcd(k,)=1\gcd(k, \ell) = 1. We claim that there are a,b>0a, b > 0 such that
ak+b=n. ak + b\ell = n.
Note that the numbers nakn-ak with a{1,2,,}a \in \{1, 2, \dots, \ell\} are all different modulo \ell. We show this by contraposition. Suppose that there are a1a_1 and a2a_2 in {1,2,,}\{1, 2, \dots, \ell\} such that na1kna2k(mod)n - a_1k \equiv n - a_2k \pmod \ell. Then we also have (a1a2)k0(mod)(a_1 - a_2)k \equiv 0 \pmod \ell. As gcd(k,)=1\gcd(k, \ell) = 1, it follows that (a1a2)\ell \mid (a_1 - a_2). Since a1a_1 and a2a_2 both are in {1,2,,}\{1, 2, \dots, \ell\}, it follows that a1=a2a_1 = a_2. Therefore if a1a_1 and a2a_2 are in {1,2,,}\{1, 2, \dots, \ell\} and a1a2a_1 \ne a_2, then na1k≢na2k(mod)n - a_1k \not\equiv n - a_2k \pmod \ell. So the numbers nakn-ak with a{1,2,,}a \in \{1, 2, \dots, \ell\} are indeed all different modulo \ell.

It follows that the nakn-ak for a{1,2,,}a \in \{1, 2, \dots, \ell\} are all the \ell residue classes modulo \ell. Since naknk=nm>0n-ak \ge n-\ell k = n-m > 0, these \ell numbers are also all greater than 00. Now choose the aa for which nakn - ak is congruent to 00 modulo ll. Since nakn - ak is greater than 00, there is now a b>0b > 0 such that nak=bln - ak = bl. This gives the a,b>0a, b > 0 such that ak+bl=nak + bl = n.

Now we divide the chairs into aa groups of kk chairs and bb groups of ll chairs. In each group, we arrange the chairs in a circle and attach the leaves to chairs in such a way that each leaf has the number of the next chair in the circle. The players on a chair in a group with kk chairs, return to the chair they started on every kk claps (and not on any other clap). The players on a seat in a group with ll seats, return to the chair they started on every ll claps (and not on any other clap). So the first time everyone returns to the chair they started on is after lcm(k,l)\text{lcm}(k, l) claps. But
lcm(k,l)=k=m, \text{lcm}(k, l) = k\ell = m,
because gcd(k,l)=1\gcd(k, l) = 1.

\square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.