×   Home   Blog   Newsletter   Privacy   Contact Us   About

Six Switch Puzzle

Infront of you is a box with six switches. Above each switch is an LED indicator. Each switch has two positions: ON and OFF. When the switch is ON, the LED lights up, when the switch is OFF, the LED is dark.
Each switch is labelled with a unique number [1-6].
You start a game. Initially all the switches are on the OFF position.
You have a single regular, six-sided, die. You roll the die, and then toggle the corresponding switch based on the result (If it is OFF, you click it ON. If it was ON, you click if OFF). Then you roll again, and again …
The game is over when all six LEDs are on. What is the expected number of rolls it will take to complete the game?
On average, how many rolls will it take to get all the lights lit up?
This is not as simple as it sounds as you could flick a switch back off (moving you a step away from victory) whilst trying to obtain ON conditions for other switches.

Symmetry

It’s tempting to think about modelling the positions of all the switches, but there is an awful lot of symmetry. All we really need to do to keep track of the system is record the number of currently lit LEDs. From this we can determine the probability of getting to a different state.
When the die is rolled, only one of two things can happen. If there are currently n LEDs on, then on the next roll:
On each roll, we either increase by one, or decrease by one, the number of lit LEDs. There is no way to keep the same number. All we need to keep track of the state is the number of lit LEDs.
It’s simple to calculate the probability of each path based on the current number of lit LEDs. If there are currently n lit LED’s, the probability of rolling one of these lit LED’s is just n/6. The probability of rolling an unlit LED is (6-n)/n
It does not matter the configuration of the individual switches. All we care about is the number of switches in the ON state.
Advertisement:

Expected number of moves

Now let’s answer the question about the expected number of moves to get all the switches ON. To do this, we need to calculate the expected number of moves from various states. We’ll define Rn to represent the number expected moves to complete the game from the state where there are currently n lit LEDs on the machine.
First the easy one; if there are five LED’s lit, there is a 1/6 chance of rolling the missing switch (this will take one roll), or there is a 5/6 chance of hitting an already lit light (which will also burn one roll, and then place us back to the state R4. In equation form:
Next, we can look at the expected number of rolls to finish if there are four lit LEDs (R4). There are two chances in six that we’ll advance (take one roll and transfer us to state R5), and four chances in six that we’ll take one roll and end up back at state R3.
Following this logic down the rabbit hole, we can generate other equations:
Finally, when game starts, all switches are initially OFF (R0), and it’s a sure thing that we’ll take one roll and end up in state R1 (the expected number of moves is one plus the expected number of moves to complete with the state with one LED lit).
What we have here are six simultaneous equations, and six unknowns. You can solve this using your favorite method of choice to get the following results:
R0416/5 = 83.2
R1411/5 = 82.2
R2404/5 = 80.8
R3393/5 = 78.6
R4372/5 = 74.4
R5315/5 = 63
What this tells us is that the expected number of rolls to solve the game (from a starting condition of all OFF), is 83.2 rolls.
The expected number of rolls to complete the game is 83.2!
I don’t know about you, but this is a lot higher than I guessed before running the calculation.

Almost there (or not!)

What was even more counter-intuitive (to me at least), was the result for the expected number of rolls when there were already five of the six LEDs lit. It’s a staggering average of 63 expected rolls to finish the game from this point! Sure, you have a 1/6 chance of finishing the game with just one roll, but if you miss, you will start to spiral down a rabbit hole and getting into who-knowns-what state before getting back up for air.
If you start the game with five of the six LEDs already lit, it will still take you an average of 63 moves to finish the game!
I bet you could probably make a really unfair carnival game based on this principle.