###
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=n^{2}, 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 n^{2} strictly between n and n^{2}.
This gets them all, by the way; and hence
the number of divisors of j=n^{2} 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.