Box

Copyright (C) 2017 Dominic Walden. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license can be found here: https://gnu.org/licenses/fdl.html.

• You are imprisoned in a pitch black, mostly featureless phonebox with a solid roof and floor
• There are four walls, with a waist-height hole in each with a button at the back; walls, holes and buttons are identical
• Each button starts randomly in one of two states and can be toggled by pressing the button; you do not know nor are you able to determine a button's state
• As an "action" you may insert your arm(s) into any of the holes and (simultaneously) press the button(s), then remove your arm(s)
• If all the buttons are now all in the same state, you escape
• If not, the phonebox spins around, eventually stopping but leaving you disorientated and with no indication as to which button(s) you just pressed
• There are no trick solutions accepted for the puzzle e.g. you can't mark walls, use your feet, etc.
• Can you guarantee your escape?

You can imagine the box like so:

        N
        ^
   +---------+
   +         +
   +         +
W  +         +  E
   +         +
   +         +
   +---------+

        S

Buttons are at N, E, S and W. Each one can be at position 0 or 1.

Starting with the button the front of the box is pointing at (indicated by the arrow), we can express the state of the buttons in four digits. For example,

1 0 0 1

would represent N=1, E=0, S=0, W=1.

There are 16 states in which the buttons can be at any time. Each one of these states can be represented in GNU Octave as a row vector:

[1, 0, 0, 1]

ans =

   1   0   0   1

As an action you can push one or two buttons, changing its state from 0 to 1 or from 1 to 0. For example, from 0 1 1 0 pushing S and W buttons will get you 0 1 0 1.

Therefore, a random push of one or two buttons is a function from one four digit binary number to another.

function finalState = pushRandom (state)

With one finger there are 4 ways to push 4 buttons.

combn(c("N", "E", "S", "W"), 1)

     [,1] [,2] [,3] [,4]
[1,] "N"  "E"  "S"  "W" 

With two fingers, there are \({4 \choose 2} = 6\) different ways.

combn(c("N", "E", "S", "W"), 2)

     [,1] [,2] [,3] [,4] [,5] [,6]
[1,] "N"  "N"  "N"  "E"  "E"  "S" 
[2,] "E"  "S"  "W"  "S"  "W"  "W" 

For a total of 10 different actions.

Each of these ways can also be expressed as a four digit binary number, with a 1 in each position of button you are pushing. For example, 0 1 1 0 represents pushing E and S buttons.

Only binary numbers with one or two "1"s are possible as you can only push one or two buttons. Therefore, not all the 16 four digit binary numbers are possible.

allPushes = [1, 0, 0, 0
             0, 1, 0, 0
             0, 0, 1, 0
             0, 0, 0, 1
             1, 1, 0, 0
             1, 0, 1, 0
             1, 0, 0, 1
             0, 1, 1, 0
             0, 1, 0, 1
             0, 0, 1, 1];

Push one or two buttons at random. This will be the push state.

push = allPushes(randi(10), :);

To simulate pushing the buttons, xor the input state with the push state. Xor will flip 1 to 0 and 0 to 1 in any position where the push state has a "1".

finalState = xor(state, push);

endfunction

When the box spins around, the position of the arrow in the above diagram moves to N, E, S or W. It may spin more than 360°, but will still end up on one of those 4 positions. The state of the buttons relative to one another does not change, just their position in the sequence.

[Diagram]

For example, starting from 0 1 0 1 if the box spun 450° = 360 + 90 the arrow will now be pointing at E and the button state will be 1 0 1 0.

[Diagram]

We will choose a number from 0 to 3 to represent ending in each position. Then use the shift function to do a circle shift of the state.

function finalState = shiftRandom (state)
  finalState = shift(state, randi([0, 3]));
endfunction

As mentioned above, there are 16 different starting states represented by 4 digit binary numbers. We will go through each in turn.

allStartStates = [0, 0, 0, 0
                  1, 0, 0, 0
                  0, 1, 0, 0
                  1, 1, 0, 0
                  0, 0, 1, 0
                  1, 0, 1, 0
                  0, 1, 1, 0
                  1, 1, 1, 0
                  0, 0, 0, 1
                  1, 0, 0, 1
                  0, 1, 0, 1
                  1, 1, 0, 1
                  0, 0, 1, 1
                  1, 0, 1, 1
                  0, 1, 1, 1
                  1, 1, 1, 1];
for startState = 1:16

Let's do 1000 experiments from each starting state.

for i = 1:1000

At the start you have not escaped and you have not done anything yet. Set the current state to the start state.

currState = allStartStates(startState, :);
escaped = false;
steps = 0;

While you are still in the box, your action is to push one or two buttons at random.

while (escaped == false)
  steps = steps + 1;
  currState = pushRandom(currState);

To escape, the state of all the buttons after pushing needs to be the same. This means either all are "1" (i.e. 1 1 1 1) or not any are "1" (i.e. 0 0 0 0).

if (all(currState) | !any(currState))
  escaped = true;

Otherwise, the box spins and you go back to the start of the while loop.

  else
    currState = shiftRandom(currState);
  endif
endwhile

Once you have escaped, write the starting state and number of steps it took to a csv file and go back to the start of one of the for loops.

    csvwrite("random_tries.csv", [startState, steps], "-append");
  endfor
endfor

tries <- read.csv("random_tries.csv", header=FALSE)
summary(tries$V2)

 Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
1.000   3.000   5.000   7.285  10.000  74.000 

tries <- read.csv("random_tries.csv", header=FALSE)
hist(tries$V2, nclass=74, probability=TRUE)

tries <- read.csv("random_tries.csv", header=FALSE)
length(subset(tries, V2 == 1)$V2)

1

On the one hand I am very suspicious that the number of experiments ending in 1 steps is significantly lower than I predicted. On the other, the fact that most end in very few steps and that the histogram above looks so like a mathematical function seems to corroborate my hypothesis.

The function representing the probability of escaping in n steps would seem to be similar to f(n) = log(n).

After trying a few more runs of the experiment, I saw this odd output from R.

blah <- read.csv("random_tries1.csv", header=FALSE)
length(subset(blah, V2 == 1)$V1)
subset(blah, V2 == 1)

[1] 3
     V1 V2
1001  1  1
5001  5  1
9001  9  1

The fact that the times that it was happening in 1 step were always the first of the 1000 tries for the starting states made me realise that perhaps I was not setting the current state back to the starting state after the escape. This was in fact the case.

Indeed, this makes the above outcome predictable, as whenever the current state was one of the escape states (0 or 15) it is impossible to escape in one step.

graphics_toolkit ("gnuplot")
tries2 = dlmread("random_tries.csv", ",", 0, 1)
hist(tries2, 74, 1)

That looks better, although the figure for 1 seems incorrect. I do not think I am using hist() correctly w.r.t. bin sizes.

Redoing the graphs in Octave gives me better results for bin size. The above graph appears to have got the correct y value for x=1.

With the exception of x=1 and x=2 the y values still appear to be decreasing logarithmically as I previously thought.

graphics_toolkit ("gnuplot")
tries2 = dlmread("random_tries.csv", ",", 0, 1)
stepsCounts = histc(tries2, 0:74)
cumStepsCounts = cumsum(stepsCounts)
cumProbSteps = cumStepsCounts / 16000
bar(0:74, cumProbSteps)

Each time there is a 1/7 average chance of pressing the right one or two buttons to escape. Therefore, the chances of getting to step n without escaping is 6/7^n.

function prob = pSteps (n)
  prob = 1 - (6/7)^n
endfunction

Comparing this with the data collected during the simulations and they appear to match pretty closely.

tries2 = dlmread("random_tries.csv", ",", 0, 1)
stepsCounts = histc(tries2, 0:74)
cumStepsCounts = cumsum(stepsCounts)
cumProbSteps = cumStepsCounts / 16000

diff -w -u1 box.octave box_nospin.octave > diff.patch
cat diff.patch

--- box.octave	2016-12-31 17:02:53.241880505 +0000
+++ box_nospin.octave	2016-12-31 17:03:43.194128205 +0000
@@ -56,3 +56,3 @@
       else
-	currState = shiftRandom(currState);
+	## Stay where you are
       endif
@@ -60,3 +60,3 @@
 
-    csvwrite("random_tries.csv", [startState, steps], "-append");
+    csvwrite("random_tries_nospin.csv", [startState, steps], "-append");
   endfor

octave box_nospin.octave

tries <- read.csv("random_tries.csv", header=FALSE)
summary(tries$V2)
tries <- read.csv("random_tries_nospin.csv", header=FALSE)
summary(tries$V2)

 Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
1.000   3.000   5.000   7.285  10.000  74.000 
 Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
1.000   2.000   5.000   7.169  10.000  77.000 

Compared with the run with spinning, it does not appear to make a great deal of difference.