In spirit of the previous post, here’s another counting light bulbs problem to think about:
There are 100 light bulbs in a row, all turned off. You first go through and turn all of them on. Then you turn off every other bulb, starting with the second bulb. Then you toggle every third bulb, turning the off bulbs on and vice versa, starting with the third bulb. You continue this until you turn off every 100th bulb, starting with the 100th bulb. How many bulbs are lit at the end?
Of course, you could just model out the problem and spend 25 minutes (as well as over $300 if you actually decide to buy the bulbs). However, to look for patterns, let’s first solve the problem with just 10 light bulbs, which won’t take nearly as much time:
In the beginning, all the bulbs are off:
In the middle row, means “off” and means “on”. The bottom row shows the number of times each light has been turned on or off.
First we toggle every light:
Then we toggle every other light, starting with the second (so we turn off lights 2, 4, 6, 8, and 10):
Then we toggle lights 3, 6, and 9:
Continuing until we toggle just light 10:
We see that 7 lights are “on”. The real question, of course, is which seven: we note that all seven “on” bulbs have been toggled an even number of times (2 or 4 in this case). We also see that the lights that have been toggled twice are in positions 2, 3, 5, and 7. Hmm… seems like prime numbers, and they have only two factors! Lights 6, 8, and 10 were toggled 4 times, and 6, 8 and 10 all have 4 factors!
Therefore, numbers with factors are toggled times. This makes sense because when we toggle every other bulb, we toggle bulbs in even-numbered positions, when we toggle every third bulb, we toggle those in positions that are multiples of 3, and so on.
Only lights in positions that have an odd number of factors will remain “off” at the end. And we know that only perfect squares have an odd number of factors*, so the number of lights turned off at the end is just the number of perfect squares less than or equal to the total number of bulbs!
For 100 light bulbs, there are 10 perfect squares between 1 and 100 (1 through 10), so at the end, there are bulbs in the “on” position.
*Consider this: factors must come in pairs, so in most cases, a number has an even number of factors. For 24, the pairs are . However, all perfect squares have a factor that is “paired” with itself: the factor pairs for 9 are (1,9) and (3,3); the pairs for 36 are (1,36), (2,18), (3,12), (4,9), and (6,6). Therefore perfect squares have an odd number of factors.
We can easily solve the same problem for any number of bulbs: for bulbs in a row, there are perfect squares less than or equal to , and after doing all of the toggling according to the rules, there will be lights on. Not too bad.
Now we consider a (seemingly) harder question: we still have 100 off light bulbs, but what if we toggled starting at the first light in each case? That is, we toggle lights , then , and then , etc. Now our factor-counting shortcut breaks down.
Or does it? It seems like the first light will be toggled no matter what, so let’s get it out of the picture for the time being. Re-number the lights so that the first light is in position 0, the second light is in position 1, etc. We have to likewise adjust our toggling procedure: we first toggle lights , then lights , then , and so on. Hey, this is basically the original problem, and we can use our factor-counting trick!
There are two differences, however: because of our renumbering, the highest-numbered bulb is now only 99, not 100. Thus we only need to count the number of perfect squares less than or equal to 99. Furthermore, now we have a light “0”. It is toggled 100 times, so it ends up being “on” at the end.
Let’s generalize this for any number of bulbs: for bulbs, renumber the bulbs as . Then out of bulbs , exactly will be off at the end (and so bulbs are on). Bulb 0 will be toggled times, so it will be “on” if is even and “off” is odd. Therefore, the number of bulbs that are “on” is:
For 100 bulbs, there should be bulbs on. It turns out this problem is not so much harder than our original problem.
Let’s check this analysis manually (i.e. the long way) for our simple 10-bulb problem: after all of the necessary toggles, we get
There are bulbs on. Note how similar the bottom row is to what we found in the original problem.