$n$ buttons on a table

Question

A generalization of Four buttons on a table:

In a certain room there is a rotating round table, with 4 symmetrically located indistinguishable buttons. Each button can be either ”on” or ”off”, however one cannot tell its the current state by its appearance. The room is lighted if and only if all the buttons are all ”on”, and there is nobody inside.

• A person is (repeatedly) allowed to enter the room, and press whichever buttons she likes. After she steps out, she is told whether she succeeded to put the light on. At the same time, a table rotates in an unknown manner.

The goal is: to design a deterministic strategy to put the light on, no matter what is the initial state of the buttons.

As a bonus I was given: The same above but with: $$n = 2^k$$ symmetrically (with respect to rotation) located buttons.

Assuming that the problem is always solvable for $n=2^k$ buttons, for which configurations of button states is it solvable when $n$ is any positive integer?

Answer 1

The answer is:

Let $d$ be the largest odd number dividing $n$. Then the problem is solvable if and only if for each of the $n/d$ groups which have $d$ equally spaced lights, all the lights are all on in the group or all off.

We know that these are solvable because:

We merely repeat the strategy for $n/d$ (which is a power of two, so we can use the linked question) on any block of $n/d$ lights, then copy it with $d$-fold rotational symmetry at all presses (e.g. if $n=12,d=3$ and we need to press the $2$ buttons $(3,4)$ under the $n/d=4$ strategy then we mirror this to $(3,4),(7,8),(11,12)$ and press those $2d=6$ buttons).

To prove the rest of the cases are unsolvable, what we are going to do is:

Assume two players, say Ana and Bob are playing of the game. At each turn Bob tells Ana a configuration he wants to input, then Ana rotates the wheel how she likes and then inputs his configuration.

What we now do:

Choose some $d$ equally spaced buttons so that one light is on and one light is off. From now on Ana can just rotate it so that these $d$ buttons always occupy the same $n$ positions, and only care about what Bob does to these $d$ buttons.

This is now equivalent to $n=d$ for our purposes. Now we claim:

Bob can never turn all these lights off or all on.

Consider what he does. If his moves is to:

Press all (or none) of the buttons, then he definitely can't turn all those lights on or off.

Otherwise:

There are two buttons in his pattern which are adjacent in his pattern, one of which he presses and one of which he doesn't. But since $d$ is odd, there are two adjacent lights in Ana's selection which are both on or both off (since an alternating sequence is impossible). So by rotating the two buttons to those two lights, one will be off and one on.

In summary:

Ana can always guarantee Bob has at least one light on and at least one light off, so in the original problem there is no strategy to definitely solve the puzzle.