I’d like to tell you about a problem that’s very famous in some circles; I’ve seen it used as an interview question for admissions tests, but I’ve also seen it just as a puzzle.
Imagine Brady, there are 100 light switches in front of you. At the moment they’re all off. The first person comes along and turns them all on. The second person turns every second light switch off. The third person deals with every third light switch - in that they don’t just turn them on or off, if they’re on they’ll turn them off and if they’re off they’ll turn them on. And the fourth person deals with every fourth light switch, the fifth person deals with every fifth light switch - I suspect you have the pattern. And that continues for 100 people. That’s the setup, the question which probably you’ve already arrived at: what happens at the end? Which light switches are on when 100 people have done this thing?
Brady asked if the 100th person just comes on and changes the state of the 100th switch? I said Brady was a pleasure to work with as he was already thinking of the extremes of the problem; a really good approach to anything you’re not sure about. The 100th person is going to deal with every 100th light switch which in this particular sample is just the last one in our lot.
After a moment’s thought you might realise that anyone beyond the 50th switch is only going to have to deal with one switch because they’re- sort of the next multiple is is out of our sample. But that- we’ve done the setup, so as ever in a good puzzle, if you want to actually go and think about it, now is a good time.
Obviously the further we go the early lights are frozen in time, they’re not going to get changed anymore. So after the fourth person’s been through, the first four lights are not going to change again. If you could sort out what happens for the first 10 and get a picture of what’s left on then maybe you get a clue about what’s happening.
I said that I wanted to show you some of the answer - spoiler coming - here’s the situation; all the lights are on now, first person’s gone in and turned all the lights on, so 100 lights on. And person 2 comes in and turns every other light off because they were all on. Just because it gets harder to see what happens next I’ll do the third person and this pattern emerges which is maybe not too difficult to arrive at after a bit of thought but then as soon as you put the fourth person in- me personally I feel slightly surprised about the pan and I didn’t expect sort of a 5 and then a double gap and then a single gap and- and after that the pattern maybe is very hard to predict and we’ve got to go all through 100 here.
So I said that I’m going to claim that maybe number 1 and number 4 are on. If I go one more - and this is the last spoiler I’m gonna give before I give it away - 5 has gone off and 5 is never going to change again. But the pattern now is really even quite hard to spot, I think if you look long enough you can see something repeating but the repeat in the pattern is getting longer each time.
And I sort of dread to try and predict what happens by this method if I go much further. So we should maybe generalise and figure out what is going to make a light switch turn on or off, and how many times, and is it going to be off or on by the end. Every time I’ve posed this problem with people - and I’m curious to know if you’re the same or if anyone watching is the same - people have mentioned a certain type of number to me that seems to be important, which are prime numbers. Do they feel like they have any bearing on this?
(I wouldn’t have thought so)
Well the interesting thing about it is that if a number is switched it’s because the person going in has- their their number is a factor of that number. So in that sense factors or divisors are going to be important here. It’s a slightly dead end here, so if you imagine a prime like the number 5; we’ve already established from our little example here the number 5 is off, it’s never getting changed again, so maybe we could conjecture that primes are going to be off? And indeed if you look at earlier primes, 2 and 3 are indeed off. And the rest we’re not sure about, but we could for example think of the number 7 - let me just write down a fact you know about 7. Those are the factors of 7, because it’s prime it only has two factors. If it only has two factors, only two people are going to switch that switch, the first person and the seventh person. Therefore I think it’s not a million miles away for anyone to lead to the conclusion that it will be off. Because it’s been turned off on by the first person and then off by the seventh. In fact any prime is going to do that because it only gets touched twice.
(So primes are always off?)
Yes but if we look at the number 6 for example - and I could I could do it on the demo but maybe it’s easier to think about how we could do it, I’m going to write this down. Who’s going to uh- who’s going to hit number 6? Well this is obvious, but I can also write it in another way. And I think what I’ve kind of pointed out the long way around is that 6 has four factors, or four divisors. I’m going to ask you to make the leap- if if it’s going to get hit by person 1 because that’s a factor, person 2, person 3, and person 6 - what will happen by the end for number 6?
(So 1 turns it on, 2 turns it off, 3 turns it on, 6 turns it off.)
Yeah.
(So if it has an even number of factors it ends up off? If it has an even number of divisors it ends up off)
I think you just said the same thing twice using two different words that people use for the same thing; divisors, factors - I think maybe uh US and UK differ, divide in fact about how they uh they choose. But factors are divisors- I mean the numbers that divide exactly into another. And you’re right, 6 ends up off, and if you want to check let’s do the uh experiment. Sixth person’s gone in, number 6 is off, and our conjecture so far that 6 should be off is correct. And you made it even more general, an even number of factors and the light will be off by the end, okay. Let me give you another bonus fact which maybe is obvious - factors come in pairs.
(Right…) (So does every number have an even number of- no it doesn’t, because we see that 4 is on- hang on) I’m really glad you’ve said the word hang on here, this should be the mathematical moment, because factors come in pairs.
(Oh but they can be duplicate pairs, can’t they?)
When would that happen? (Like 2 times 2, 4)
So if I wrote down 4, all right, I could write it down as 1 times 4. I could also write it as 2 times 2, but the duplication here has meant there’s actually only three factors. Good! We’re making progress, we’ve established why I think number 4 is left on. You’re doing so well so far. What would be the next light that stays on?
(A square number)
Do you want to pick your favourite square that’s not been done?
(Well 9?)
9 is the next one, should we check it? I mean, having a an ability to experiment like this by the way is underrated I think in mathematics. A lot of people think you should be doing it all in your head but just experimenting and testing your conjectures is nice. Let’s try to answer the question: Which numbers have an odd number of factors?
The only numbers that have an odd number of factors are squares. This can be demonstrated by using the Fundamental Theorem of Arithmetic, which states that every number has a unique prime factor decomposition. Experiments with numbers such as 16 (which is 4 squared) and 24 (which is not a square number) can be used to show that any number that is a square will have an odd number of factors, while any number that is not a square will have an even number of factors. So that’s four, five, six, seven, eight - there’s eight factors.So if you look at the prime factorisation, you can see the number of factors is controlled by the powers here, and that’s why the squares have an odd number of factors. So for any number, if you want to know how many factors it has, you can look it up in this sequence.And the answer to the puzzle of the light switches is that it is the squares that stay on.This is because the squares have an odd number of factors, while all other numbers have an even number of factors.We can also see that the number of times each switch gets switched is equal to its number of factors.The sequence of the number of divisors of a number is labelled a000005 in the online encyclopedia of integer sequences. It appears that the number 60 is the first to have 12 factors and is switched the most in the first 100. Additionally, 180 is the number that is knobbled more often than the others up to 200 light switches. This is because 60 and 360 are highly composite numbers, which are helpful to have fractions for, like portions of a circle. Interestingly, only square numbers have an odd number of factors.
If you enjoyed this video, you should check out Brilliant, which offers thousands of lessons and courses for all levels of learners. There is a 30-day free trial and a discount on the premium subscription if you use the URL brilliant.org/Numberphile. Thanks to Brilliant for supporting Numberphile and making such cool stuff on the internet.