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

Made With Macintosh