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 a hundred light bulbs instead of let me actually just draw them so I have one light bulb there I have another light bulb and I have a hundred of them a hundred light bulbs and what I'm going to do is first I'm going to go well actually before I even start turning in these light bulbs on and off let me let you know that they are all off so they start off they start off now the next thing I'm going to do is I'm going to number the hundred light bulb I'm going to number them 1 through 100 so the first light bulb is light bulb 1 the second light bulb is light bulb 2 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 I'm going to switch every light bulb that essentially every light bulb I'm going to go and I'm going to so if I go I'm going to switch if they all start off I'm going to turn them all on right so they'll all be you know let me do it so on my first pass so let's call this pass one pass so one 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 passed to what I'm going to do is I'm going to switch only the light only every other light bulb so for example I'll say ok I once I won't switch light bulb one I'll only switch light bulb 2 so light bulb one will stay on light bulb 2 will be off light bulb 3 will be on light bulb for 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 is going to stay on this was 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 the fifth lightbulb will what was it before the fifth the lightbulb would have been on and will stay on and now the sixth lightbulb in this case we switch it off and now it'll be on again but I think you get the point every third lightbulb or if we look at the numbers of the lightbulb every every numbered lightbulb with 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 get you I think you're getting the point but what I'm going to do is I'm going to do a hundred passes so the first pass I switch every lightbulb they all started off so they're all going to be turned on the second pass I switch every other lightbulb or every second lightbulb the third pass I do every lightbulb every third one or that's a multiple of three and my question to you is after a hundred passes so after a hundred passes after one hundred passes after one hundred passes how many light bulbs are still on or how many are on period how many are on and that is the brainteaser how do you figure out of out of the hundred which ones are going to be on it you should be able to do this in your head you don't have to make like an Excel spreadsheet and actually do all the on and off switches how do we know so the first question is how many of these are going to be on after I do one hundred passes and just to make clear what's the hundredths Pass going to be well I'm only going to switch every hundredths light bulb so I'm only whatever this light bulb is already doing I'm just going to switch it if it was off it'll be come on if it was on it'll be come off so the first question is how many of these are going to be on after one hundred 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 we know when do we know that a light bulb is is being switched so if I'm on the second pass I will turn on all I don't want to say turn on it might already be on I will which every light bulb that's divisible by two and then if I'm on the third pass I'll switch every light bulb is divisible by three so on every pass what am i doing what went went on if I've if I'm if I'm on pass n this is a hint if you want it if I'm on pass n pass n what do I know I know all the light bulbs that are numbered that where n is a factor of that light bulb that will get switched right so we know that switched if n is a factor of the light bulb number 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 right so for example so example if we're looking at if we're looking at light bulb let me draw a light bulb light bulb eight this is light bulb eight so one 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 - it'll be switched off I know that because two is divisible into eight pass three is nothing's going to happen pass four and past three nothing's going to happen because this isn't a multiple of three pass for what will happen it will be switched it'll be pet switched back on and then what's the and then pass eight is the next time we'll touch this light bulb and we'll be switched back off 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 so for a lightbulb to be on has to have odd number of factors now that's an interesting question or 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 it's interesting to think about so what what numbers are true well 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 make sense to what are all the factors of two well you have one and two so two it has an even number you're going to switch it on the first time and then off the second time and then you're never going to touch it again so this going to stay off three your factors are one and three for your factors are one two and four interesting here we have three factors right we have an odd number of factors so four is going to stay on we're going to turn it on when 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 5 or one and five six the factors are one two three and six it's an even number so it's going to be off when we're all done with it seven it's one and seven eight we just did that it's one two four and eight it's 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 nine is also going to be the light bulb number nine is also going to be on when everything is done let's keep going I don't know you know maybe actually we did this at our mental boot camp and some of the kids immediately they said oh well you know the distance between one and four is three and this is between four and nine is this between four and nine is five and maybe the distance between nine next number is going to be seven right it increases by odd numbers and that's what's nine plus seven let's just try that out 16 what are the factors of 16 there 1 2 4 8 and 16 interesting that worked right from 9 to 16 you increment it by 7 from from 4 to 9 you credit about 5 so it seems like we have a pattern but can you see something even more interesting about the numbers 1 4 9 and 16 you could try all the numbers between 9 and 16 and you'll see that they have an even number of factors but what's what's interesting about all of these numbers what why do they have an odd number of factors in all of these other cases every factor is paired with another number right 1 times 2 is 2 1 times 6 is 6 2 times 3 6 there's always a pair except for these numbers there's no pair right why isn't there 1 times 4 is 4 but 2 times 2 is also 4 so we only write the 2 once 3 times 3 is 9 4 times 4 is 16 so all of the lights that are going to be on are actually perfect squares that's why they have an odd number of factors so all right what's our question how many so the question this problem of what light bulbs are going to be on boils down to how many perfect squares are there between 1 and 100 and if you know you could just list them out and you could say oh that's just you know the perfect squares or 1 4 9 16 and you could try to think them all or you could say is well how many numbers can I square and get a number less than 100 or less than equal to 100 well 100 is equal to 100 is equal to 10 squared so you can only square the numbers between 1 and 10 to get a perfect square so there's only 10 perfect squares between 1 and 100 all right hopefully didn't lose that but if that confuses you just list them all out you have to you know given that hundreds is the largest number its the largest perfect square there and that's 10 squared the only other perfect squares in the in our range we're talking about our 1 squared 2 squared 3 squared all the way up to 10 squared and we could do that 4 squared is 16 5 squared is 25 30 649 64 81 and 100 so these the numbers with these the light bulbs with these numbers on it are the ones that will stay lit when we're all done anyway hope you enjoyed that