Traversing Switch Configurations

Number the dials arbitrarily from $0$ to $3$ . On the $n$ th turn ( $n = 1, \dots 15$ ), turn dial $m$ , where $2^m$ is the greatest power of two that divides $n$ . In other words, turn dials in this order: $\begin{array}{r|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline m & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 3 & 0 & 1 & 0 & 2 & 0 & 1 & 0 \end{array}$

This problem is equivalent to the search for a Gray code : a list of all $2^n$ different combinations of $n$ bits, where each entry in the list differs from its neighbors by exactly one bit. The key fact is that Gray codes exist for all $n \geq 1$ .

The search for a $n$ -bit Gray code is equivalent to finding a Hamiltonian path (or loop) through a $n$ -dimensional cube.

To generate a Gray code, start with $A_0 =$ an arbitrary combination of $n$ bits. To generate $A_n$ from $A_{n-1}$ , change the $m$ th bit, where $2^m$ is the greatest power of two dividing $n$ .

Thus,

$\begin{array}{r|c|l} n & A_n \\ \hline 0 & 0000 \\ 1 & 000\mathbf 1 & \text{change bit 0} \\ 2 & 00\mathbf 11 & \text{change bit 1} \\ 3 & 001\mathbf 0 & \text{change bit 0} \\ 4 & 0\mathbf 110 & \text{change bit 2} \\ 5 & 011\mathbf 1 & \text{change bit 0} \\ 6 & 01\mathbf 01 & \text{etc.} \\ 7 & 010\mathbf 0 \\ 8 & \mathbf 1100 \\ 9 & 110\mathbf 1 \\ 10 & 11\mathbf 11 \\ 11 & 111\mathbf 0 \\ 12 & 1\mathbf 010 \\ 13 & 101\mathbf 1 \\ 14 & 10\mathbf 01 \\ 15 & 100\mathbf 0 \end{array}$

Relevant wiki: Induction - Combinatorics Applications

Suppose it is possible for n switches, we will prove it is also possible for n + 1 switches.

For n+1 switches:

• Step 1: set the first switch to Off

• Step 2: for the remaining n switches, follow the exact sequence of combinations used in the solution for n switches.

• Step 3: turn the first switch to On

• Step 4: for the remaining n switches, follow in reverse order the exact sequence of combinations that were used in Step 2.

To beginning mathematicians out there who don't have any idea as to what Arjen Vreugdenhil is saying (it is a great solution I admit), this will be one of the possible solutions.

"F" would be Off and "T" would be On

1. F-F-F-F
2. F-F-F-T
3. F-F-T-T
4. F-F-T-F

Notice the pattern. 2^2 possible permutations of the last two switches. Notice that we didn't change the 1st and 2nd switches. We are only finding for the permutations for the two switches.

1. F-T-T-F
2. F-T-F-F
3. F-T-F-T
4. F-T-T-T

2^3=8 permutations for all the last three switches. Why? Because We changed the 2nd Switch and then again we find the permutations of the last two switches.

1. T-T-T-T
2. T-T-T-F
3. T-T-F-F
4. T-T-F-T
5. T-F-F-T
6. T-F-T-T
7. T-F-T-F
8. T-F-F-F

Then, repeating the iteration, now with the first switched on, we get another 8 permuations. Why? Because we are doing what we did in steps one to eight, with one exception, the first switch is ON.

To generalize, we need 2^n individual steps to find all the possible permutations without repeating one. Here, n=4, so we need 2^n = 2^4 = 16 steps. The base 2 is from the fact that there is two possible choices for a single switch, that are, ON and OFF.

Forgive me as this is not a proof. Tung Phung has already given one. I am trying to let beginner math students to understand.

The hint was 'what if the box had 3 switches'. Well if it had 3 switches, then Peggy should do what she had done for the 2 switches. Then turn the 3rd switch. Then do exactly the reverse of the turns for the 2 switches. And now seeing as it has 4 switches, and we know that all combinations could be achieved for 3 switches, just turn the 4th switch. And then do the reverse of the steps that we taken for 3 switches. | In general if there are n switches, and you have turned the switches for (n - 1) switches, turn the nth switch. And then turn in reverse for the (n - 1) switches. Regards, David

The question could be re-worded: Can Peggy run through every possible combination of switch settings exactly once? Of course she can! How long that takes her and how well she can keep track of what she is doing are both practical issues, but certainly there is nothing preventing her from running through all the combinations to get the box open.

although the problem is unique in making us understand combinatorics, whats the problem exactly?

To put the specific solution into simple terms Peggy could simply iterate what she did for the first box (with 2 switches) on the top 2 switches of the second box for each similar step of the lower 2 switches. Thus taking 4 steps x 4 steps both being the same sequence she used for the first box.

Let 0 denotes switch off and 1 denotes switch on. There are 2 $^{4}$ combinations of these 0 and 1. Let S be the set that denotes all possible sample points (i.e. S is the sample space). S = {{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}}.

The picture shows that the starting position is {0,0,0,0}. We need to show that there is a sequence with {0,0,0,0} as the starting point and it covers all 16 possible elements of S exactly once. Verify that one possible sequence is {0,0,0,0} - {1,0,0,0} - {1,1,0,0} - { 0,1,0,0} - {0,1,1,0} - {0,0,1,0} - {1,0,1,0} - {1,1,1,0} - {1,1,1,1} - {0,1,1,1} - {0,0,1,1} - {1,0,1,1} - {1,0,0,1} - {1,1,0,1} - {0,1,0,1} - {0,0,0,1}

This problem can be solved using {0,0,0,0} as the starting point and use a computer program to write all possible sequences that cover all 16 elements. Then do math to find absolute difference of the next sequence with the previous sequence. For example, absolute|{1,0,0,0} minus {0,0,0,0}| will give one as the answer. As long as there is a sequence that always give one for the 15 absolute differences calculation, we have an answer. I have not computed how many answers are possible but it's not hard to write an algorithm to do so.

I just want to add to Arjen that this is not the only possible combination. There is many ways of changing one bit per step, i.e.: 0000, 0001, 0011, 0010, 0110, 0100, 0101, 0111, 1111, 1110, 1100, 1101, 1001, 1000, 1010, 1011, as another possibility.

0000
1000
1100
0100
0110
0010
0011
0001
0101
1101
1001
1011
1010
1110
1111
0111