I'd like to tell you about a problem that's very famous in some circles; I've seen it
used as like an interview question for uh admissions tests, but I've also seen it just
as a puzzle. I would like you to 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: So the 100th person just comes on and)
(changes the state of the 100th switch?) - I've said this before Brady, you're a pleasure to
work with. You're already thinking of the extremes of the problem, and it's a really good approach to
anything you're not sure about, you sort of jump to the extreme thing. 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. Which light switches are on after 100 people have been through?
Do you have any thoughts about the sort of numbers we're going to have to talk about in
this problem? - (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 are you- what are you saying
the first four lights? - (Yeah) - They're 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. So I want 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 that's my first spoiler, but what you said is
nice because you know that after the first four people have gone through those four are not gonna
change again. So I'm gonna 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 pose 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. So let's do it, 7, 7 is off, 8- and 9 is already off. So when I put the ninth
person in, lo and behold, 9 is on. And if we check it right, 9, you can write it as 1 times 9,
how else can you write it? Well it's not 2 times anything but it is 3 times 3 and that's it.
In fact if you're checking factors you only ever need to check up to the square root of a number
before you should probably stop wasting your time and checking anymore. And how many factors? Well,
one, two, three. Conjectures so far? Squares are looking good? - (Squares, odd- numbers numbers)
(with an odd number of factors. Anything that has a times itself, unless that does it twice.)
(Unless it has two two numbers that can do it.) - Well, we- already you've kind of talked yourself into the square
numbers are apparently going to be on because of the duplication, but now you're worried
about whether that happens twice if it's going to change it. So maybe we should try an example.
Can you think of it- a square of a square? I'm asking you to do so much while you're holding the
camera. Uh 4 is square, and you could square 4 to get uh still a relatively low number,
4 times 4 - so we should check 16. - (Let's check 16.) - Do you want to try on paper before we actually?
(Yeah, let's do it on paper.) - So 16. - (1 times 16.)
Nice, Brady keep going. - (4 times 4 times, 2 times 8)
Nice, because if we if we go up in a sort of nice pattern we'll know when we've got them all. 3 times I
don't think is going to work, and 4 times 4. First things first, is it a square? Yes, it's got
this duplicated. So were you expecting to see more here? - (No but I don't know whether the fact that)
(you can expand that to 2 times 2 times 2 means anything - probably not.) - Well what we should
be doing here is bearing in mind something which sounds important called the Fundamental Theorem
of Arithmetic. The fundamental theorem of arithmetic says that every number has a unique prime factor
decomposition. So we're writing down factors, not prime factors, and there's more than one
way of writing them down which is kind of what we're using, but every number has a unique way of
writing it in primes - and you probably know that. And maybe that's going to help us because that's
kind of to do with what you're pointing out here, that you could expand the 8 into 2 times
2 times 2. So let's just do the prime factor decomposition of 16. Uh, it's just 2 to the 4. If
you break all these down to primes you're just left with that. 9 is 3 squared. If we jump say to-
let's do 24, not a square number, let's see what it decomposes as. Well let's just do the old-fashioned
way: 1 times 24, 2 times 12, 3 times 8, 4 times 6 and then we're done. Interestingly they're
coming in pairs still, and if you write it as a prime factor decomposition it's going to be 2
times 12 - but 12 is 2 times 6 and 6 is 2 times 3 - so it's that and I would write it as 2
cubed times 3. So it's worth, I think, whenever you're working with a problem
that has factors involved, noting the difference between factors or divisors and prime factors.
And I think you've already got to the heart of this. And I guarantee some people are watching
this video, they're like we've got there straight away because if you spot the one thing which you
have already spotted, this becomes a number theory question. And you said it, the numbers with an odd
number of factors are going to be on and the ones with an even number are going to be off.
So it becomes, which numbers have an odd number of factors? We've already established by experimenting
that squares appear to, but is only them? And do some squares not? Well we've checked the 16.
Let me give one spoiler, the only numbers that have an odd number of factors are the squares.
Which I think we should dive into to finish this video, but if that's true can you predict
which lights are going to be on at the end of our story? - (Well we did 2 squared, 3 squared, 4 squared - 25, 36.)
Should we just animate it and see? I mean there's two things to watch out for: which one's
turn on by the end and the patterns we get along the way which, uh even if you've done
this problem before, maybe you haven't seen this before and it's quite it's quite pleasing so
let's just animate and see how that goes. 16, 25 is on, 36 is on, 49's looking good Brady. 64, 81,
and 100. Congratulations; even though I don't think you said it, you told me the equivalent
statement which is the numbers with an odd number of factors are on. And this surprises some people-
(The square numbers, I would never have guessed that at the start.) - No, and a lot of people immediately
say this problem, they're like oh it's gonna be to do with the primes, which is why I mentioned
that earlier. Which I think is why people like it as an interview style question because it has
that slightly unexpected - squares are something to do with factors? But they are and it's quite a
nice profound number theory fact that I haven't proved yet: it is only the squares that have an
odd number of factors. And maybe we should prove that - are you up for that? - (Yeah, because I want to)
(figure out whether or not this was a complete red herring, the fundamental theorem of- ) - Yeah, well now
we've established that because of the on and off nature it's- you'd need an odd number of facts of
factors for it to stay on; and crucially all factors come in pairs, because that's what factors do, and you
spotted the crucial thing is that that only breaks down when you have a duplication, that's where the
count changes. But let's prove it a little bit more formally and I'll try to give us our
space down here. - (Do you want more paper?) - I don't think we need more paper, Brady. Let's
do it with 24 as an example. So 24 is 2 cubed times 3. That's its prime decomposition and
that's almost always a good place to start. Let me point out how you'd figure from that how to
count the factors. Now we've done it, and there aren't very many, but if this was a huge number
I don't think I'd want to list them by hand. So if this is its prime factor decomposition, a factor
must be some subset of numbers in that, otherwise it wouldn't multiply it together. So I could for
example pull out 2, a 2 is in there, agreed? I could pull out two of the 2s and I could go up
to three of the 2s but if I tried to put four 2s it's not in here so it's not a subset. And I
could pull out a 2 with a 3, or I could pull out the 3 on its own and then - have we done
them all? One, two, three, four, five - I think there should be a few more factors, what have I missed?
Well I could pull out 2 squared with the 3, I could put out 2 cubed with the 3,
and there's got to be a better way to count this. So what I've- I've got 2
times 3, 2 squared with the 3, 2 cubed times a 3 - that's the full one. What have I missed?
There should be eight. I'm thinking there are eight over here, and I'm wondering if it's obvious.
(So the- the number its- what about the number itself and 1?) - Well that's- that's there, the number itself,
but you're right, the 1 is the hard one to spot because it's kind of the weird subset of this.
And so here's what's happening, I'm choosing some of the numbers in the list to make a factor;
and actually the only way I can do it is is controlled by the power here, there's actually
a power 1 here that's kind of invisible. And I can go- I could do any of the numbers up to
3 - including 0. So to make this a bit more obvious, I could have 2 to the 0, I could have
2 to the 1, I could have 2 to the 2, and I can have 2 to 3 in the mix. And I can have
3 to the 0 or 3 to the 1 in the mix. And any combination gives me one of the factors.
So that's it, it's just how many options do I have for that which is always going to be one
more than that number; and how many options do I have for that? So if we're going to generalise -
I'd like a piece of paper. - (Told you!) - Now we've got an appropriately fresh piece of paper to
generalise on, I'm going to write down uh for some number n you can always write it as a product of
primes. Let's call them p1 and p2 and p3 and so on, what should we go up to, pk? Are you happy with
that so far? And to condense the notation, like some of these primes might be the same, so let's- you
can put them as a power so let's call this uh c1, c2 - and these are the indices of the powers - and ck.
That- every number can be written like that. Some of these don't exist, but we just pointed out on
the previous page that it's the number of options you have for each prime that controls it. So we had
3 there before but we had four options for the 2. There's 2 to the 0, 2 to the 1, 2 to the 2 and
2 the 3. So c1 plus 1 options for how many of that prime to include. But then completely
separately there's the options here; so you can multiply- like whatever you do there, you can do
a different option here, so I've got c2 plus 1, c3 plus 1, all the way to ck plus 1. And the
number of factors is well defined as this: it's the product of the powers of the prime factors
plus 1. Which means we are almost within grasp of proving your conjecture earlier, which is that
it's only the squares which have an odd number. So the square numbers will have one integer
which multiplies by itself to give you that number, that's the definition of a square, which means when
you look at its prime factors they will always come in duplicates, there will always be a
prime squared or to the power of 4 - it will be an even power. Otherwise you couldn't split it in
half. Which means all of these numbers are even in a square, which means if you add 1 to them all;
for a square number all odd. All of these will be odd. Which means the product of them all
is odd. And we can also see kind of the reverse: if any one of them
was odd originally at the top then adding 1 to it would make it even, and we would actually
just get an even number here. Which is why you normally get an even number, factors come in
pairs, it only takes one of them to break it, because a product of anything with an even number is also
even. The only time they end up all odd is if you had a square to start with - and we're done.
The answer to the puzzle of the light switches is it's the squares that stay on.
There are lots of other questions you could ask if you want to explore which is, how many times
does each switch get switched? And that is just its number of factors. Do some get switched-
which light switch is going to break first if you repeatedly have fun with this! And that's
less obvious because it's asking which numbers have lots of factors, and I don't think we have a
very good intuition about this. We know the primes don't have many factors, but some factors- some
numbers have lots of factors. So actually this uh this puzzle hinges on a really important sequence
called tau or sigma - it's important enough to have a name - which is the number of divisors of a number.
And if you look it up on the online encyclopedia of integer sequences it has the name a000005.
(It's very early) - The naming of the integer sequences, or the labelling, I don't quite
understand but it- however you name it, you've got to attach importance to the first ones;
even though the first one is something to do with groups. Feels profound and the rest of them I'm
not quite sure I recognise. However number five is the sequence of the numbers of divisors of a
number. And if you look at the ones that have high number of devices it's numbers like 60,
60 is the first one to have 12 factors which we could check by doing this if you wanted to.
(So 6- is 60 the switch that gets switched the most in the first 100?) - There are others
with 12 factors but it's the first one to get switched 12 times. It's what they call a highly
composite number, it's the first time that its number of factors beats all the ones before it.
And I looked briefly up to this, and if you carried on to say 200 light switches, the number
180 gets knobbled more than often than the others. And you start to recognise those numbers as the
ones we use to divide things which are helpful to have fractions for, like portions of a circle. You
won't be surprised to know that another highly composite number is 360. So we measure time in
60s, we measure angles in 360s; it's partly because of the number of factors here. I'm
glad you found a route to the nub of the problem here which is only the square numbers
have an odd number of factors, and that feels like a pleasing outcome to a potentially contrived puzzle.
If you enjoyed that video, well you're going to love all the courses quizzes and puzzles
on Brilliant. Here's the leaning tower of Lire, also known as the block stacking problem. It's part of
their superb 'Calculus in a Nutshell' course. It's great. And here's where Brilliant really shines,
it's super interactive! You can really get hands-on with this stuff. There are thousands of lessons and
courses on Brilliant, and new ones are being added all the time. From beginner to advanced mathematics,
computer science, AI, neural networks - this is a treat beyond compare for all level of learners.
To check out Brilliant yourself, maybe give it as a gift for the learner in your life,
go to brilliant.org/Numberphile. That URL, which is also in the description, can get
you a discount on their premium subscription and there's also a 30-day free trial. Thanks
Brilliant for supporting Numberphile and making such cool stuff on the internet.