Light the Halls

The problem: You stand in a hall, with 100 light switches that are all off. You go down the hall, and flip each switch. You then start again, but only do every other switch, starting with the first even number. You then do the same process for each number divisible by 3, then divisible by 4, until you get to numbers divisible by 100. You then flip the 100th switch. Which lights are on after the last flip (numbers divisible by 100)?

First, let’s operationalize our approach. We’ll say that each switch has been flipped 0 times before we begin. Each time we flip a switch, we add 1 to the number of times it has been We’ll also call each trip down the hall “run p” where p is the number which all flipped switches index must be divisible by. switched, let’s call this a light’s “flip count”. So, if the flip count is odd, it has been flipped on then off any number of times, and then switched one more time, meaning it’s currently on. The reverse is true for the even flip counts, if a light has a even flip count it will be off. So, our goal is to find the lights which have and odd flip count, as those lights will be on.

So what determines a light’s flip count? Well it’s the number of times it has been flipped, because it is a multiple of a number less than or equal to itself. Let’s use a general case to make this concept more clear. Say we examine an arbitrary light, numbered n. The flip count of light n will be equal to the numbers from 1 to n that divide n. The nth light will be switched once when we flip every light (divisible by 1) and when we flip every nth light, starting with n. So, any number that is not divisible by a number that is not itself or 1 (i.e. a prime number) will be off. So, the criteria for determining if a light is on or off can be reduced to the number of factors each number has between 2 and n-1.

Let us now examine a concrete case. Take the 12th switch. It will be switched on during run 1 (12/1=1), run 2 (12/2=6), run 3 (12/3=4), run 4 (12/4=3), run 6 (12/6=2), and run 12 (12/12=1). This switch is flipped 6 times, and since 6 is an even number this light will be off.

We can observe an interesting symmetry in the above example. 12*1=2*6=3*4. We count all the factors, and this is the same as the flip count for light 12: 6. But wait, wouldn’t that mean every light would be off, because how can a number have an odd number of factors, they come in pairs of 2?!

Yes, that is true, however let’s revisit the problem. We move up one number each run, and as such, even if a number is divisible by that number 2 times (e.g. 4*4=16), this only counts as 1 flip. That is, the only lights that will be on once we are finished, are those where n is divisible by the same number twice. This is another way of saying a*a =x. However, we have a more concise name for such numbers, they are the perfect squares. So, only the lights with an index which is a perfect square will be left on once we are finished. More explicitly, lights with index 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 will be left on, as there’s are the only perfect squares from 1 to 100.