One possible initial reaction to this problem is that there is rather too much movement of caramels ${ }^{2}$ at each step to keep track of easily. This leads to the question: 'How little can I do in, say, two steps?' If every student passes all their caramels left on one step using (b), and all their caramels right on the next step, then no caramels move. (This is rather too little movement.) Let us see what a small change to this sequence can accomplish. We choose a student with at least one caramel. At the first step, she passes one caramel to the right and any others she has to the left. Every one else passes everything left. At the next step everybody passes everything right. The effect of this is that exactly one caramel has moved exactly two places to the right. Similarly, there is a double step which moves exactly one caramel two places to the left.

If we have not already done so, now is the time to start working through some small values of $n$.
The case $n=3$ yields a useful observation. Going two places (let's call this a double jump) to the left on a triangle is the same as going one place to the right. Indeed if $n$ is odd, say $2 k+1$, then $k$ double jumps to the left moves the caramel one place to the right and vice versa.

It is now clear that, if $n$ is odd, any arrangement of caramels is possible. We simply move them into position one at a time.

In the case $n=4$ it seems hard to get all the caramels into one place. Indeed, if we limit ourselves to double jumps, then we can only get $(1,1,1,1),(1,2,1,0),(2,2,0,0)$ and rotations of these arrangements. What can we say about these? Well it seems that students one and three always hold two candies between them. Having noticed this, it is not too hard to make a more general observation: if $n$ is even then a double jump cannot change the total number of caramels held by the odd numbered students. However, double jumps are not the only moves available to us. For example, it is possible to go from $(2,2,0,0)$ to $(3,1,0,0)$. A double jump now gives $(2,1,1,0)$ as well.

To squeeze maximum value out of the $n=4$ case, it is worth looking at the arrangements we have not yet managed to get to. They are (rotations of) $(4,0,0,0),(3,0,1,0)$ and $(2,0,2,0)$. What do these have in common? They are precisely the arrangements where the even numbered students hold all the caramels. Can we prove that these are illegal? Well, what can we say about an arrangement which precedes one of these elusive ones? This question leads to the last big idea in the solution to this problem. If after some step the even numbered students have all the caramels, they cannot have had any at all before the step, else they would have passed at least one caramel to an odd numbered student.

Turning this around gives a crucial lemma for even values of $n$. Let's call a caramel held by an odd numbered student an odd caramel and define even caramels similarly. Let's call an arrangement with at least one odd caramel and at least one even caramel balanced. If the arrangement is balanced before some step, then it will be balanced after the step. The initial position is balanced, so every legal position is balanced.

Finally we are on the home straight. We claim that every balanced position is legal. Using double jumps we can move to $\left(\ldots, \frac{n}{2}, \frac{n}{2}, 0, \ldots\right)$. Now we need to tinker with the numbers of odd and even caramels. There are lots of usable sequences. For example:

$$\begin{gathered} (\ldots, a, b, 0, \ldots) \\ (\ldots, a-1,1, b, \ldots) \\ (\ldots, a-1, b+1,0, \ldots) \end{gathered}$$

can be used to change the number of odd caramels provided $a-1 \geq 1$.
Once we have the correct number of odd and even caramels, they can be moved into place using double jumps.

It remains to observe that there are $\binom{2 n-1}{n}$ possible arrangements of caramels, and that if $n$ is even, then $2\left(\frac{\frac{3 n}{2}-1}{n}\right)$ of these are not balanced.

Another sensible approach is to think about which steps are reversible. It turns out that many are, including all those where the students all use option (b).

It is possible to argue that if $n$ is odd, then we can start with any position, move to $(\ldots, n, \ldots)$ reversibly, then move to the initial position reversibly. Playing the whole tape backwards shows all positions are legal.

If $n$ is even it is possible to start from any balanced position and reversibly move to $(\ldots, n-1,1, \ldots)$ and thence to the initial position so we are done.

[^0]
[^0]: ${ }^{2}$ The word 'candy' was a little too grating for my delicate British ears. I am grateful to the Italians for suggesting the more elegant alternative.