Problem

Suppose you are locked in a room. Next to the door there is a wheel with switches mounted to it. Each switch is in one of two states, either off (0) or on (1). To open the door, all switches have to be on at the same time. To achieve this, you can press any combination of switches simultaneously. If you manage to achieve the all-on state, the door opens and you won. If not, the door stays shut, and the wheel with the switches on it spins for a while so fast that you can’t keep track of them. And of course you can’t tell the state of any switch by looking at is.

Is there a sequence of button press patterns that is guaranteed to take you out of the room?

I have only read about this problem second-hand on a page by GitHib user shainer. It cites the book So you think you’ve got problems? by Alex Bellos as its source. Apparently that book is offering the version with switches for warming up and as the advanced version.

Interactive demo

When I find the time, I’ll do an interactive implementation of this setup, to warrant including this in the CindyJS blog.

Claim

I will focus on arbitrary powers of two, i.e. any (with ). I claim that in this case there exists a sequence of button press patterns that is guaranteed to open the door. That sequence will have steps.

Note that the following sections will contain spoilers so only continue reading if you don’t want to tackle the problem yourself. If the above statement is something you’d rather think about yourself for a while, please stop reading now and do that.

Notation

A winning strategy is a sequence of actions, where each action is a pattern of buttons to press simultaneously. I will use to denote a button you don’t press and to denote one you do press. That way, a button pattern can also be treated as the binary digits of a number. I will use a subscript to denote binary numbers.

So for four switches, denotes a pattern where you press a single button, and is two opposite buttons. As you can already see from these examples, the cyclic order of buttons doesn’t make a difference (since you can’t know the cyclic position of the wheel in any case). So and are effectively the same action. I will usually use the smallest number (most leading zeros) to uniquely identify a set of actions that only differ by rotation.

Here is an exercise for the translation between numbers and patterns: The initial pattern is unknown, but we know it has binary digits and not all of them may be set at the same time. Therefore the initial state must satisfy i.e. somewhere in the range through inclusive.

Winning strategy

We will define the winning strategy recursively, using Python notation.

def strategy(k):
  if k == 0:
    # Base case: n = 1 switch, so just press that and be done.
    return [1]
  # Recursive case: go from n to 2n switches.
  n = 1 << (k - 1)  # This is actually th n of the previous step.
  strategy_n = strategy(k - 1)   # Get strategy for half as many switches.
  doubled = [(i << n) | i for i in strategy_n]
  strategy_2n = doubled[:]       # Make a copy of the list. (1)
  for action in strategy_n:
    strategy_2n.append(action)   # Add a single action.     (2)
    strategy_2n.extend(doubled)  # Add a copy of the list.  (1)
  return strategy_2n

In case you’re not familiar with Python: 1 << k is the number 1, shifted k bits to the left. So this is the same as . In a similar vein, i << n is the number i, left shifted by n bits. Then | i is the binary or with the original number i (although I might as well have take + i here). Taken together (i << n) | i just means take a number i, imagine it written down using n binary digits, then write down those same digits a second time. In more mathematical notation, you might write but in my opinion that’s not really more useful than the verbal description.

If you just want to see the winning strategy printed out as a sequence of patterns, you can use this code snippet to do so:

for k in range(4):
  n = 1 << k
  print(f"n = {n}")
  for row in map(f"{{:0{n}b}}".format, strategy(k)):
    print(row)
  print("")

Proof

But why does this work? Since the strategy is defined by recursion, we will prove it by induction. So we will stick to being half the number of switches you’re currently trying to solve.

The base case is really simple: if you have just one switch, and the door isn’t open yet, you press that switch and the door must open. So with this base established, we may assume that the strategy works for switches, then use that to show that it also works for switches.

At any point in the process while the door is still locked, the current (unknown) state of the wheel is any sequence of bits, except all ones. This bit sequence can be decomposed into two numbers of bits each as follows:

0 <= s < (1 << (2 * n))  # s is the current state, a 2n bit number.

m = (1 << n) & 1         # m is a mask, consisting of n ones.
a = s >> n               # a is simply the higher n digits of s.
b = (s & m) ^ a          # b is the difference between the two halfs of s.

0 <= a < (1 << n)        # a is an n bit number.
0 <= b < (1 << n)        # b is an n bit number.
s == (a << n) | (a ^ b)  # s can be reconstructed from a and b.

Here ^ in Python denotes exclusive or (XOR). The idea is to split the bit number into two halfs, but instead of just representing each half independently, we represent one half (I picked the higher but it doesn’t really matter) as is and also represent the XOR of the two halfs. That XOR is the symmetric difference: it has a in positions that are the same in both halfs and a if the two halfs differ in that position.

This representation as has a number of useful properties:

1. Spinning the wheel with its switches will result in a rotation of (and some effect on that I don’t really care about).
2. If then spinning the wheel will leave and rotate by some amount.
3. An operation from doubled performs the same operation on both halfs of the current state, it does not change at all.
4. An operation from doubled toggles those bits in which correspond to the original action before it was doubled.
5. An operation from strategy_n only touches half the words, so it effectively leaves unchanged but toggles the corresponding bits in .

So looking back at the winning strategy, we had the row marked (2) perform every operation from strategy_n and in between each of these actions we had the rows marked (1) perform all of the doubled actions.

If then one complete run of doubled will solve the game. That’s because is maintained by actions (property 3) and spins (property 2). At the same time, the sequence essentially applies the strategy for half as many switches to via actions (property 4) and spins (property 2).

The actions from (2) are responsible for solving the game on the half of the representation (i.e. the difference between half the bit patterns). The actions apply directly to that (property 5). The effect of the (1) parts in between is no worse than a random rotation of because the actions don’t change it (property 3) and the spins merely rotate it (property 1).

Note for clarity that we don’t need the game on to leave unmodified. We merely require that once is solved, we will solve the full game from there.

Optimality

The number of actions is guaranteed to be optimal. There are possible initial (non-winning) situations. Assuming that by pure chance the wheel were to spin only by full turns between actions, then every action would be an XOR on that initial state. To clear every one of these possible patterns, steps are required since in the absence of rotations each step turns exactly one initial state to the winning situation. Having random spins can only make things worse, never better. So there can be no shorter strategy for switches.

Uniqueness

The winning strategy as computed above is not unique. Of course you could arbitrarily rotate every action and still achieve the same result. But there is a more general source of variation: When we use the actions from (2) to solve the game on , the effect this has on is irrelevant. So any action with the same difference between both halfs will do.

The first time this shows up is in the middle of the solution. The abve algorithm will use there. But you might as well use . Both of these will toggle one difference bit and leave one as is. The variation can then proceed to next generations: the solution for switches may use instead of and it may use instead of . Both of these are independent of one another.

A sequence

Taking the case of as an example, you can also find the winning strategy for this as follows:

So there is one new number in each row, the rest is re-using numbers from the previous row. The new numbers, written down in decimal, are . For different values of you would get more or fewer numbers, but they would all start the same, so you can see them as different finite prefixes of some underlying infinite sequence. OEIS knows this sequence as A001317. Actually with the 8 numbers given above you will find more matches, but with greater you can get more numbers to search for, until the match is unique. OEIS calls this sequence “Sierpiński’s triangle (Pascal’s triangle mod 2)”. And if you squint at the rows above, you can see a slanted version of that triangle.

So presumably one can use that sequence to generate the winning strategy, too. So far I haven’t bothered writing a proof to show that this sequence will agree with the code I wrote above. And since the proof is very centered on the recursive properties of my definition, where the number of elements is doubled in each step, proving a winning strategy directly from this sequence likely would require some different approach. Particularly one that still rules out a winning strategy for sizes that are not powers of two.

Not a power of two

Experiments suggest that if is not a power of two, then no strategy exists at all that is guaranteed to lead to a win in a finite number of steps. But at the moment this is merely a conjecture, supported by experiments for n up to 10 or so.

I’m exploring these cases in more depth in a follow-up post.