100 Bright Ideas

The Problem

A room contains a row of 100 light bulbs. Below each light bulb is a switch to control the bulb above. To begin, each bulb is off. You decide to pass through the row, flipping each light on, one-by-one. Your then make a second pass, this time flipping the switch for every 2nd light (#2, #4, #6…..#100), turning half of the lights off. You make a third pass toggling the switch for every 3rd light, then another pass toggling every 4th, then 5th, then 6th, all the way up to your 100th pass when you change the setting of only the 100th light.

How many bulbs are on after the 100th pass?

The Solution

Each switch will be flipped once for each factor it has. After running through the whole sequence the only switches that will be left on are the switches whose number has an odd number of factors. This just happens to be all of the squares. So, the number of switches that will be on is equal to the size of the set of numbers whose squares are less than or equal to 100, also know as 10.

Here’s a link to a visualization of the iterations. This makes it much easier to see what’s going on. The number at the end of each row is the number of switches that are on after completing that iteration.

Incidentally, I tried like The Dickens to come up with a formula to represent what I saw. But I failed to come up with a correct one. If anyone out there manages to come up with one I’d love to hear about it.