2020-06-07-switches.md

layout	title	date	categories	cjs	katex
post	Spinning switches	2020-06-07 23:00 +0100	recreation	version v0.8	true

Problem

Suppose you are locked in a room. Next to the door there is a wheel with <script type="text/x-tex">n</script> 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 <script type="text/x-tex">n=2</script> switches for warming up and

<script type="text/x-tex">n=4</script> 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

<script type="text/x-tex">n=2^k</script>

(with <script type="text/x-tex">k\in\mathbb N_0</script>). 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 <script type="text/x-tex">2^n-1=2^{(2^k)}-1</script> 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

<script type="text/x-tex">0</script> to denote a button you don't

press and <script type="text/x-tex">1</script> 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

<script type="text/x-tex">_2</script> to denote binary numbers.

So for four switches, <script type="text/x-tex">0010_2</script> denotes a pattern where you press a single button, and

<script type="text/x-tex">0101_2</script> 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 <script type="text/x-tex">0010_2</script> and

<script type="text/x-tex">0001_2</script> 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

<script type="text/x-tex">n</script> binary digits and not all of them may

be set at the same time. Therefore the initial state must satisfy

<script type="text/x-tex">0\le i_0\le 2^n-2</script> i.e. somewhere

in the range <script type="text/x-tex">000\ldots 000_2</script> through <script type="text/x-tex">111\ldots 110_2</script> 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

<script type="text/x-tex">2^k</script>.

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

<script type="text/x-tex">d_i = s_i \cdot 2^n + s_i</script>

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:

{% raw %}

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("")

{% endraw %}

Proof

But why does this work? Since the strategy is defined by recursion, we will prove it by induction. So we will stick to <script type="text/x-tex">n</script> 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

<script type="text/x-tex">n</script> switches, then use that to show that it

also works for <script type="text/x-tex">2n</script> switches.

At any point in the process while the door is still locked, the current (unknown) state of the wheel is any sequence of

<script type="text/x-tex">2n</script> bits, except all ones.

This bit sequence can be decomposed into two numbers of

<script type="text/x-tex">n</script> 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 <script type="text/x-tex">2n</script> 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 <script type="text/x-tex">0</script> in positions that are the same in both halfs and a <script type="text/x-tex">1</script> if the two halfs differ in that position.

This representation as <script type="text/x-tex">(a,b)</script> has a number of useful properties:

1. Spinning the wheel with its <script type="text/x-tex">2n</script> switches will result in a rotation of <script type="text/x-tex">b</script> (and some effect on <script type="text/x-tex">a</script> that I don't really care about).
2. If <script type="text/x-tex">b = 0</script> then spinning the wheel will leave <script type="text/x-tex">b = 0</script> and rotate <script type="text/x-tex">a</script> by some amount.
3. An operation from doubled performs the same operation on both halfs of the current state, it does not change <script type="text/x-tex">b</script> at all.
4. An operation from doubled toggles those bits in <script type="text/x-tex">a</script> 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 <script type="text/x-tex">a</script> unchanged but toggles the corresponding bits in <script type="text/x-tex">b</script>.

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 <script type="text/x-tex">b = 0</script> then one complete run of doubled will solve the game. That's because

<script type="text/x-tex">b = 0</script> 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 <script type="text/x-tex">a</script> via actions (property 4) and spins (property 2).

The actions from (2) are responsible for solving the game on the

<script type="text/x-tex">b</script> 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 <script type="text/x-tex">b</script> 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

<script type="text/x-tex">b</script> to leave <script type="text/x-tex">a</script> unmodified.

We merely require that once <script type="text/x-tex">b = 0</script> is solved, we will solve the full game from there.

Optimality

The number of actions is guaranteed to be optimal. There are

<script type="text/x-tex">2^n-1</script> 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 <script type="text/x-tex">2^n-1</script> possible patterns, <script type="text/x-tex">2^n-1</script> 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

<script type="text/x-tex">n=2^k</script> 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

<script type="text/x-tex">b</script>, the effect this has on <script type="text/x-tex">a</script> 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

<script type="text/x-tex">n=4</script> solution. The abve algorithm

will use <script type="text/x-tex">0001_2</script> there. But you might as well use <script type="text/x-tex">0111_2</script>. Both of these will toggle one difference bit and leave one as is. The variation can then proceed to next generations: the solution for

<script type="text/x-tex">n=8</script> switches may use <script type="text/x-tex">00000111_2</script> instead of <script type="text/x-tex">00000001_2</script> and it may use <script type="text/x-tex">01110111_2</script> instead of <script type="text/x-tex">00010001_2</script>. Both of these are

independent of one another.

A sequence

Taking the case of <script type="text/x-tex">n=8</script> as an example, you can also find the winning strategy for this as follows:

<script type="text/x-tex;mode=display"> \begin{aligned} s_8 &= A + [00000001_2] + A \\ A &= B + [00000011_2] + B \\ B &= C + [00000101_2] + C \\ C &= D + [00001111_2] + D \\ D &= E + [00010001_2] + E \\ E &= F + [00110011_2] + F \\ F &= G + [01010101_2] + G \\ G &= H + [11111111_2] + H \\ H &= [] \end{aligned} </script>

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

<script type="text/x-tex">1,3,5,15,17,51,85,255</script>.

For different values of <script type="text/x-tex">n</script> 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 <script type="text/x-tex">n</script> 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 <script type="text/x-tex">n</script> 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.

{% comment %} https://stackoverflow.com/q/62492390/1468366 {% endcomment %} {% assign post_custom_url = site.url | append: site.baseurl %} {% assign post_full_base_url = post_custom_url | default: site.github.url %}

I'm exploring these cases in more depth in a [follow-up post]({{post_full_base_url}}{% post_url 2020-06-21-three-switches %}).