### PUZZLE #9: LIGHTING A HALLWAY (SOLUTION)

We chose a thousand for the number of lights to indicate a pretty large number, enough to see a general pattern if you cared to try a few special cases.

So let N be the number of light bulbs, and let's focus on bulb number j. Notice that if j=1, there is just one flip and the switch is never touched again. Therefore, at the end, the bulb is on just in case it started out off. If j=2, the switch is flipped by both Mr. ONE and Mr. TWO, and left alone by all succeeding switch flippers. Hence this bulb is on at the end just in case it started out that way.

In general, Mr. i flips switch j just in case j is a whole number multiple of i (or i is a divisor of j). Hence the end configuration of bulb j will agree with the initial one just in case the number of divisors of j is even.

If j happens to be a perfect square, say j=n2, then there will be a certain number d of divisors of n, other that 1 and n itself. Furthermore, for each of these divisors, one may multiply it by n and obtain a divisor of n2 strictly between n and n2. This gets them all, by the way; and hence the number of divisors of j=n2 is equal to 2d+3, an odd number. So at bulbs numbered 1,4,9,16,25,36, etc., the end configuration will be opposite that of the initial one.

If j happens not to be a perfect square, let s be the square root of j, by definition not a whole number. Let n be the largest divisor of j less than s. Then j=mn, where m is a divisor of j greater than s. There are no other divisors of j between n and m, and each divisor of j that is strictly between 1 and n (there may be none) is matched by its "complementary" divisor that is strictly between m and j. Thus, if d is the number of divisors of j strctly between 1 and n, then the number of divisors of j=mn is 2d+4, an even number. So at bulbs not numbered 1,4,9,16,25,36, etc., the end configuration will be the same as the initial one.