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.
