## 1997-02 Solution

All numbers have roots, and all roots have 'buddies' - the
complementary root which when multiplied by that root gives the
original number. The states of all lights will be toggled by all their
roots and their buddies. The only numbers which have roots that don't
have buddies are perfect squares - the root which is the sqrt of the
number is its own buddy. So all lights which are not perfect squares
will have an even number of roots (the roots and their buddies) and
thus will be off - the final state is the same as the starting
state. All the perfect squares will be short one root (the sqrt will
not have a buddy) and thus have an odd number of roots and thus be on.

WWW Maven: Dan
Garcia (ddgarcia@cs.berkeley.edu)
Send me feedback