A Light Maths Puzzle
Between me and my friends, many of whom are mathematicians, there is a long-standing tradition of passing around puzzles. If one of us hears about an interesting puzzle, it gets handed around until everyone has had a chance to play with it. In that spirit I would like to share with you a lovely puzzle I learned about a long while ago, have shared with many people since and have recently been reminded of.
The puzzle can be formulated in many different ways, but one presentation is as follows: 100 light bulbs are numbered 1-100, and each has a switch underneath it. The switches are toggles, so when they are pressed they turn the light on if it was turned off, and turn the light off if it is already on.
In this scenario, 100 people are also each assigned numbers from 1-100, and they each go into the room with the 100 light switches and press all the switches which are a multiple of their own number: person 1 would have a busy time pressing every single switch, person 2 hits every other switch, person 3 visits every third switch, and so on. Some might be turning lights off, others will be turning them on, and some might do a mixture.
The room starts with all 100 lights switched off, and all 100 people go through the room exactly once. The question is then, which lights will be switched on after everyone has had a go? Take a minute to think about it now, and I will add some more observations and context before sharing a solution.
Illuminating the Problem
With a mathematical puzzle, it is often productive to start by working through the first few steps: what happens when the first few people pass through? Person 1 will hit every button and switch all the lights from off to on. Then person 2 comes through, and turns off every second light; the even-numbered lights will be off, and the odd-numbered lights will remain on.
The problem gets less simple when person 3 enters: they switch every multiple of three, which will mean any odd multiple of three will get switched off, and any even multiple of three (which will have been switched off by person 2’s efforts) gets switched on.
As we introduce more people, the pattern of lights left on and switched off becomes more and more complicated, to the point where it is not easy to keep track any more: a light will be on after person 4 if it is either an odd number that did not get switched off by person 3, or an even multiple of three that is not also a multiple of 4 … maybe we need a simpler way to think about it.
A few nice observations can also be gleaned from thinking about how ‘every multiple of their own number’ will work in practice. For example, person 100 will just walk in, hit switch 100 and walk out – and indeed, anyone with a number greater than 50 will just hit their own number, as the next multiple of it will be outside our range of 1-100.
It is also notable that nobody hits a switch with a number smaller than their own number; assuming everyone goes into the room in order, once for example person 20 has been through, all the light bulbs with numbers below 20 will stay in their current state forever.
Light Bulb Moment
While all of this is interesting, it does not get us any closer to an answer. What might help with that is thinking about this problem in terms of the switches, rather than the people: for a given switch, how many times will it get flipped from off to on or on to off, and what does that mean about its final state? If all the switches start turned off, any light which gets switched an even number of times will stay off, and any which get hit an odd number of times will remain on.
So, for a given number, who will press the switch? Since each person presses the multiples of their own number, each numbered switch will be hit by anyone whose number it is exactly divisible by. And if we are thinking about divisors of a number, there is a natural place to go first, which is to think about prime numbers.
These are particular numbers whose only factors are 1 and themselves – for example, 7, which is only divisible by 1 and 7. A more concise way to define a prime, which many people prefer, is to say ‘a number with exactly two factors’; this is also helpful in excluding the annoying edge case of whether 1 is a prime.
This means any button which is attached to a prime numbered light bulb would be pressed exactly twice, and would therefore remain off at the end of our game. While this is a nice insight, it turns out considering prime numbers does not necessarily help as much as you would think – it is certainly not the case that all non-primes are left on.
When thinking about factors, we should remember that dividing a number by its factor will give us another whole number – that is pretty much what we mean by a factor. But this other whole number will itself be a factor – for example, we can write:
12 = 1 × 12
12 = 2 × 6
12 = 3 × 4
Once we reach 3 × 4, there is no point in looking for any larger factors: they will all be present as the right-hand number on an earlier row. So, for any number, we can write a list of its factors in this way and this will result in a list of pairs. If we study that light switch carefully, we will see each of these numbered people come in to hit the switch – even if it is not in the same order listed here – but for every person switching it on, another will come to turn it off again.
So does this mean all the lights end up off? Not necessarily. There is one exception to the rule above, which is that of a square number. We can write:
4 = 1 × 4
4 = 2 × 2
Here we still have pairs of factors – dividing by one will give another – but since this is a square number, one of our pairs is the same number twice. Since person 2 just hits every multiple of 2 once, the 2 will not be cancelled out by its opposite factor. In general, any factor that is the square root of a square number will only get hit once.
This means the square numbered light switches will be exactly the ones that get hit an odd number of times: when we finish our game, the numbers 1, 4, 9, 16, 25 and so on will remain lit, and all the others will be switched off.
It is a slightly surprising twist that square numbers should pop out as the special numbers in this case, but it is a lovely puzzle to play with and each of these insights is a pleasing a-ha towards the goal.
I have seen this puzzle stated in a large variety of ways, including as light switches, and the slightly more serious case of prisoners in cells with keys that can be turned one way or another. I also recently presented it as part of a ‘Pints and Puzzles’ event as a peculiar drinking game: a line of 100 shots, which either get drunk or refilled by visiting partygoers. In this case, other interesting questions arise, including how much booze will be needed to complete the whole game – and who gets the most drunk?
I was recently reminded of the existence of this puzzle by the news that my colleague Ben made a video about it for the Numberphile YouTube channel, which is worth a watch if you have time – he touches on many of the same points I have made here, as well as going a bit more into how this connects to prime factorisations. And don’t forget to share the puzzle with your friends!
The post A Light Maths Puzzle originally appeared on the HLFF SciLogs blog.