If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains ***.kastatic.org** and ***.kasandbox.org** are unblocked.

Main content

Current time:0:00Total duration:11:19

Let's say we have
100 light bulbs. Well, let me actually
just draw them. So I have one light
bulb there. I have another light bulb. And I have 100 of them. 100 light bulbs. And what I'm going to do is--
Well actually, before I even start turning these light bulbs
on and off, let me let you know that they
are all off. So they start off. Now, the next thing I'm going
to do is I'm going to number the hundred light bulbs. I'm going to number them
one through 100. So the first light bulb
is light bulb one. The second light bulb
is light bulb two. All the way to light bulb 100. And what I'm going to do is,
first I'm going to go and I'm going to switch essentially
every light bulb. So if they all start off, I'm
going to turn them all on. So let me do it. So on my first pass-- let's
call this pass one-- so in pass one, I'm going to
turn all of these on. On, on, on. They're all going
to be turned on. On. And then in pass two, what I'm
going to do is I'm going to switch only every other
light bulb. So, for example I'll say, OK, I
won't switch light bulb one. I'll only switch
light bulb two. So light bulb one
will stay on. Light bulb two will be off. Light bulb three will be on. Light bulb four will be off. And so essentially, every light
bulb-- if you look at their numbers-- that
is a multiple of two, will be switched. So 100 will be switched,
so that'll also be off. Then I'm going to come-- and
ignore this right here-- and I'm going to switch every
third light bulb. So what's going to happen? This one's going to-- let me
switch colors arbitrarily-- this one's going to stay on. This one's going to stay off. And I'm going to switch
the third light bulb. So this one was on. Now this one will be off. The fourth light bulb will
stay off, because I'm not touching it. The fifth light bulb
would have been on and it'll stay on. Now the sixth light bulb, in
this case we switched it off, and now it'll be on again. But I think you get the point. Every third light bulb, or if we
look at the numbers of the light bulb, every numbered light
bulb would that is a multiple of three is going
to be switched. And if it was a multiple of
three and two, it would have been switched on the
first time and then off the second time. But I think you're getting
the point. But what I'm going to do is,
I'm going to do 100 passes. So the first pass, I switch
every light bulb. They all started off,
so they're all going to be turned on. The second pass, I switch every
other light bulb or every second light bulb. The third pass, I do every
third one, or that's a multiple of three. And my question to you is, after
100 passes, how many light bulbs are still on? Or how many are on, period? And that is the brain teaser? How do you figure out, of
the hundred, which ones are going to be on? You should be able to do
this in your head. You don't have to make an Excel
spreadsheet and actually do all the on and
off switches. So the first question is, how
many of these are going to be on after I do 100 passes? And just to make it clear,
what's the 100th path going to be? Well, I'm only going to switch
every 100th light bulb. So whatever this light bulb was
already doing, I'm just going to switch it. If it was off, it'll come on. If it was on, it'll
become off. So the first question is, how
many of these are going to be on after 100 passes? And then the bonus question
is, which of these are going to be on? And so that's the question. Pause it if you don't
want the answer. And then try to solve it. I think it shouldn't take
you too much time. But now I'm going to give
you the answer. Or maybe I'll start with
a couple of hints. So, when do we know that a light
bulb is being switched? So if I'm on the second
pass, I will-- I don't want to say turn on. It might already be on. I will switch every light bulb
that's divisible by two. And then if I'm on the third
pass, I'll switch every light bulb that's divisible
by three. So on every pass,
what am I doing? If I'm on pass n-- this
is a hint if you want it-- what do I know? I know all the light bulbs that
are numbered where n is a factor of that light bulb,
that will get switched. So we know that switched
if n is a factor of the light bulb number. And that's just a fancy way of
saying, look, if I'm on pass 17, I'm going to switch all
the multiples of 17. Or I could say, I know that I'm
going to switch light bulb 51, because 17 is
a factor of 51. So that tells you that we're
always going to be switching one of these light bulbs on
or off when one of its factors is our pass. So for example, if we're looking
at light bulb eight. This is light bulb eight. So when will it be switched? So on pass one, we're
definitely going to switch it on. So pass one, it's going
to be switched on. Pass two, it'll be
switched off. I know that because two is
divisible into eight. Pass three, nothing's
going to happen. On pass three, nothing's going
to happen because this isn't a multiple of three. Pass four, what'll happen? It will be switched. It'll be switched back on. And then pass eight is the next
time we'll touch this light bulb, and it'll
be switched back. So every time one of its factors
go by, we're going to switch this thing. And as you can see, in order
for it to be on at the end, you have to have an odd
number of factors. So that's an interesting
thing. So in order for a light bulb to
be on, it has to have odd number of factors. Now that's an interesting
question. What numbers have an odd
number of factors. And this is something that I
think they should teach you in grade school, and
they never do. But it's a really interesting
kind of number theory. It's a simple one, but it's
interesting to think about. So what numbers are true? Let's do all the factors for
some of the starting numbers. So all the factors of one. Well one, the only factor
is just one. So one works? One has an odd number
of factors. So that means that one
will remain on. Because you're only going to
turn it on in the first pass. Makes sense. Two. What are all the
factors of two. Well you have one and two. So two has an even number. You're going to switch it on the
first time, then off the second time. Then you're never going
to touch it again. So this is going to stay off. Three. Your factors are
one and three. Four. Your factors are one,
two and four. Interesting. Here we have three factors. We have an odd number
of factors. So four is going to stay on. We're going to turn it on in our
first pass, we're going to turn it off on our
second pass. And we're going to turn it on
again in our fourth pass. Let's keep going. So five. The factors of five
are one and five. Six. The factors are one,
two, three and six. It's an even number, so they're
going to be off when we're done with it. Seven. it's one and seven. Eight. We just did that. It's one, two, four and eight. Still going to be off. Nine. Let's see. Nine. The factors are one,
three and nine. Interesting. Once again we have an odd
number of factors. So the light bulb number nine
is also going to be on when everything's done. Let's keep going. I don't know, I actually did
this at our mental boot camp with some of the kids. And they immediately said,
the distance between one and four is three. The distance between four
and nine is five. And maybe the distance between
nine and the next number is going to be seven. It increases by odd numbers. What's nine plus seven? Let's just try that out. 16. What are the factors of 16? They're one, two, four,
eight and 16. Interesting. That worked, right? From nine to 16, you incremented
by seven. From four to nine, you
incremented by five. So it seems like we
have a pattern. But can you see something even
more interesting about the numbers one, four,
nine and 16. And you could try all the
numbers between nine and 16, and you'll see that they have
an even number of factors. But what's interesting about
all of these numbers? Why do they have an odd
number of factors? In all of these other cases,
every factor is paired with another number. One times two is two. One time six is six. Two times three is six. There's always a pair. Except for these numbers. There's no pair. Why isn't there? One times four is four. But two times two
is also four. So we only write the two once. Three times three is nine. Four times four is 16. So all the lights that are going
to be on are actually perfect squares. That's why they have an
odd number of factors. So what's our question? So this problem of what light
bulbs are going to be on, boils down to how many perfect
squares are there between one and 100? And you could just
list them out. And you could say, oh well
the perfect squares are one, four, nine, 16. And you could try to
think of them all. Or you could say, well how many
numbers can I square and get a number less than
or equal to 100? Well 100 is equal
to 10 squared. So you can only square the
numbers between one and 10 to get a perfect square. So there's only 10 perfect
squares between one and 100. Hopefully you didn't lose that,
but if that confuses you, just list them all out. Given that 100 is the largest
number, it's the whole largest perfect square there. And that's 10 squared. The only other perfect squares
in our range we're talking about are one squared, two
squared, three squared, all the way up to 10 squared. And we could do that. Four squared is 16. Five squared is 25. 36, 49, 64, 81, and 100. So the light bulbs with these
numbers on it are the ones that will stay lit when
they're all done. Anyway, hope you enjoyed that.