The N-barrel problem. From some national math olympiad.

Question

Does anyone know how to solve this problem?

At the entrance to a cave is a rotating round table. On top of the table are $n$ identical barrels, evenly spaced along its circumference. Inside each barrel is a herring either with its head up or its head down. In a move, Ali Baba chooses from $1$ to $n$ of the barrels and turns them upside down. Then the table spins around. When it stops, it is impossible to tell which barrels have been turned over. The cave will open if the heads of the herrings in all $n$ barrels are up or are all down. Determine all values of $n$ for which Ali Baba can open the cave in a finite number of moves.

International Mathematics TOURNAMENT OF THE TOWNS Senior A-Level Paper Fall 2009.

Answer 1

I'm not sure I've properly understood your description of the problem. As I understand it, it appears to be equivalent to the following:

• Each of $\ N\ $ barrels contains a light which might be on or off, but you have no idea which lights are on and which are off unless they are all on.
• There's some mechanism which will will be triggered when all the lights are on, and alert you to the fact that they're all on.
• There's a switch on each barrel. If you press the switch it will toggle the state of that barrel's light from off to on or from on to off.
• At successive instants of time $\ t_1, t_2,\dots\ $ you can choose to press the switch on any barrel you please. Your goal is to choose a sequence of barrels the toggling of whose switches will eventually result in all lights being on and the alert mechanism being triggered.

The last bullet point is the part that I'm not entirely sure about, since it ignores the seemingly redundant specification that the barrels are on a rotating circular platform. I'm assuming that on each round you will have a barrel in front of you, and that barrel is the only one whose switch you're able to press. I'm also assuming, however, that you know the value of $\ N\ $. If that's the case, then you can simply label the barrels $\ B_1,$$\,B_2,$$\ \dots,$$\, B_N\ $ in the order in which they come to you, and as long as you keep count of the number of rounds that have passed, you will always know the label borne by the barrel currently in front of you. When $\ B_i\ $ is the next barrel whose switch you want to press, you simply have to wait until it rotates around to the position in front of you.

Assuming my understanding of the problem is correct, then there's always a sequence of switch presses (for any value of $\ N\ $) which guarantees that all the lights will eventually come on. You can represent the statuses of both the switches and the lights by $\ 1\times N\ $ binary vectors $\ s\ $ and $\ \ell\ $, respectively, where \begin{align} s_i&=\cases{0&if you've pressed the switch on $\ B_i\ $ an even\\ &number of times\\ 1&if you've pressed it an odd number of times}\\ \ell_i&=\cases{0&if the light in $\ B_i\ $ is off\\ 1&if it's on} \end{align} Although you never know the value of $\ \ell\ $ until it reaches $\ (1,1,\dots,1)\ $, you do know that $\ \ell_i\equiv\ell(0)_i+s_i\pmod{2}\ $, where $\ \ell(0)\ $ is the initial status of the lights and $\ s\ $ is the current status of the switches. Therefore, to guarantee that the lights will all eventually come on, you merely need to cycle the status of the switches through all $\ 2^N\ $ of its possible values. When $\ s_i\equiv\ell(0)_i+1\pmod{2}\ $ for all $\ i\ $, then all the lights will be on.

The most convenient way of cycling through all $\ 2^N\ $ values of the switches' status is to do it in Gray code order: if you have pressed a total of $\ n\ $ switches, and $\ n+1=2^rk\ $, where $\ r\ $ is a non-negative integer, and $\ k\ $ is an odd positive integer, then the next switch you press should be the one on $\ B_{r+1}\ $ ($\ r\ $ is uniquely determined).

Answer 2

First note: A winning strategy must every now and then flip all barrels in one move. For if each round leaves one barrel untouched, it may happen by the rotations that it is always the same barrel that is left unturned.

In fact, we may view this as a game, where a second player knows Ali Bava‘s strategy and picks an initial situation and the rotations to prevent a win.

The antagonist can win if $n$ is odd and $>1$: Start with a mixed situation of some up and some down barrels. If Ali‘s next move flips all (or no) barrels, the situation will again be mixed; for every other move, there is a flipped next to a non-flipped position and the adversary can rotate two adjacent barrels of same orientation (both up or both down; these exits because $n$ is odd and $>1$) to this positions. Then we will again have a mixed position. Hence Ali cannot win.

The same strategy if the antagonist works for even $n$ as long as it is not a power of two, i.e., has a nontrivial odd divisor $d$. The antagonist simply ignores all barrels apart from an equidistant subset of $d$ barrels.

Remains the case that $n$ is a power of two.

The case $n=1$ is trivial: flip it till you win.

For $n=2$, flip both; if this fails (and failed in the initial situation), the two barrels are now different. Flip one barrel to make the barrels the same. A final flip of both may be needed to win.

For $n+4$, assume we start with an even number of good barrels. The flipping two adjacent barrels either createsc an all-same situation thatched solve with a flip-all move. Or we have an alternating situation (which the flip-all does not change); hence flipping two opposing barrels creates an all-same situation and we may need a final flip-all move. If we still did not win, the number of good barrels must be odd. Flip a single barrel to be sure the number is even and start over , this time with guaranteed success.

Can you see how to recursively obtain a winning strategy for higher powers of two?