Introduction

This is a follow-up question to a previous post.

While that post was concerned with cases where the number of switches is a power of two, here I’m investigating setups where that is not the case, mostly using a setup with three switches as my example.

Problem

This section is copied from my previous post, so feel free to skip if if you already read that.

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.

Conjecture

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.

Optimization criterion

Not having a guaranteed winning strategy doesn’t mean that you are stuck in the room forever. Chances are that if you keep pressing switches long enough, you will open the room by chance. Some strategies of pressing buttons are better than others. For example, always pressing all buttons will never release you from the room if doing so once did not do the trick already.

One reasonable way how a winning strategy can be optimal is with respect to the expected number of actions to free you.

Optimality depends on an assumed probability distribution for the initial state. One such assumption could be that all non-winning states are equally probable.

So let’s take three switches as an example, and assume all seven possible initial states are equally likely.

Optimal strategy for three switches

The infinite strategies shown in the above graph all lead to a minimal expected number of actions, namely

In the following sections I’ll explain where this figure is coming from.

Modeling three switches

If the initial probability distribution is known (or assumed), then the probability distribution after a given sequence of actions can be expressed as a vector

This is considering switch states as equivalent if they only differ by rotation, similar to the power of two case I discussed before. The individual properties add up to one. The last component indicates the probability that we already solved the door by that state (so we probably assume this to be zero up front). Assuming that all seven non-winning states are equally probable, we get

We get threes there because for the one and two button arrangement, three rotationally equivalent patterns exist. We can model the actions as matrix multiplications.

You can read each matrix by column to figure out what a given state will transform to: if you are in state (i.e. one button is on and two are off) and press one button, then the second column of tells you that with probability you end up in state but with probability you get to . You can also read the matrix by row to figure out where a given state could come from. If after pressing one button you end up in state , then this will happen all the time (probability ) if the previous state was , and it also will happen with probability if the previous state was . The bottom row indicates ways to get to the winning state, and the one in the bottom right entry ensures you never leave the winning state after reaching it.

Expected wait while repeating one action

How do you compute the expected number of actions needed for a given probability distribution? This is linear, so you can sum expected wait times for a single state weighted by probability of that state:

The expected number of actions is the product with a row vector of expected times for each state times a column vector of the probability of that state. The expected time if you already are in the winning state is always zero so I did not include an entry .

One possible strategy would be to always press one button. In that case the initial strategy is the same as the remaining strategy after the first operation has been performed. This allows us to rewrite the waiting time vector as the probability of needing one more step (which is zero for the winning state and one for all other states) plus the time we need from whatever distribution we end up in after that first step:

Here denotes the identity matrix. The final line of the equation is a simple linear equation, although you should note that it is solved for an unknown vector on the left, not on the right as you may be more familiar with. For a strategy of always pressing one button we find so you can expect to need 10 actions if you happened to start in the all-off state, 9 if one switch was on when you started, and 7 if two were on already.

Strategies repeating different actions

Computing that value is a matter of applying the considerations above to strategies that repeat several different steps. Let’s take the strategy of alternating between three buttons and one button.

Here is the expected time per state if you start with all buttons then one button then repeat these two. We compute it as the chances of needing one more step (expressed by plus the expected times per state for a strategy that starts in one button then all buttons then repeat, which we denote by . As we can express in a similar way, we can combine both to get rid of and solve for . We get

So even though starting with all buttons or starting with one button can make a difference depending on the distribution you start in (as evidenced by ), they make no difference when applied to the assumed initial distribution .

Different paths leading to the same distribution

The above computation can show that the expected number of actions is the claimed value of for some of the strategies included in the graph. It is also possible to show that where two different arrows meet in a node, the distribution in that node will be the same. For example the two big initial branches in the beginning join again after three steps, which can be shown using

So at that point, the chances of already having opened the door are while the chances of still being stuck are .

For the infinite number of options in the lower path of the graph, we can show that as long as the state and the state are equally likely, the choice between and doesn’t make a difference:

Computer-aided experiments

Standard graph-searching algorithms such as Dijkstra’s algorithm

can be used to find strategies that for each achievable probability distribution minimize the expected number of actions up to that node. Counting actions up to that node is effectively assuming zero waits after this. Such an algorithm will never over-estimate the cost of a given strategy, but it may under-estimate the cost if the steps needed for the remaining (infinite) path are still too high. Cost here is the probability of needing another step (i.e. not having won yet) summed for all the path to a given node.

Knowing that a cost of is achievable allows the algorithm to disregard any nodes with a higher cost than this, which makes the computation considerably faster and more goal-oriented. Such a run did find that up to a depth of over 20 actions, all paths still under consideration were following the pattern shown in the above graph diagram.

Strictly speaking this is no proof that there can’t be an even better strategy, which looks like those above in the beginning (so it is still derived from one of the paths still under consideration) but then deviates from that after some number of actions to reach an even lower total cost.

I consider this very unlikely, but as I said, that is not a proof.

Other numbers

The above was considerable manual work, namely in setting up the matrices, in doing the graph exploration, and in computing a plausible threshold. For more than four switches (remember that there is a finite winning strategy for four) that work would be harder, so it might make sense to automate some of it.

Chances are that if similar computations were done for other numbers of switches, patterns would emerge that can be generalized to arbitrary numbers. That is essentially what I had done for the finite strategies, too. Work for some later time, though.