# Solution

A large version of the numbered grid shown below is drawn in chalk in a parking lot. 16 people arrange themselves, one person per square on the large grid. At the sound of a bell, if a person is standing on square $n$, they now move to the square whose number is congruent to $5n \pmod{16}$. How many bells must ring before everyone returns to their original squares?

$$\begin{array}{c|c|c|c} 1&2&3&4\\\hline 5&6&7&8\\\hline 9&10&11&12\\\hline 13&14&15&16 \end{array}$$

We are essentially finding the order of a permutation here. The geometry is irrelevant -- consider where each integer goes under the mapping $n \rightarrow 5n \pmod{16}$:

$$\begin{array}{cccccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\ 5 & 10 & 15 & 4 & 9 & 14 & 3 & 8 & 13 & 2 & 7 & 12 & 1 & 6 & 11 & 16 \end{array}$$

This gives the following cycles:

$$(1,5,9,13), (2,10), (3,15,11,7), (4), (6,14), (8), (12), (16)$$

So when the bell has rung a multiple of 4 times, persons starting at 1, 5, 9, 13, 3, 15, 11, and 7 are back in their original positions. For 2, 10, 6, and 14, the bell need ring only a multiple of 2 times for these people to be back in their original positions. The rest of the people never leave their square. Consequently, the least common multiple of the cycle lengths 4 and 2 is the first time everyone is back where they started. So four bells ring before this happens.