Light bulb switching brain teaser

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.