 # Pulling strings: The Weekly Puzzle by Dilip D’Souza

An eccentric Maharani’s palace has one long, and I mean REALLY LONG, room. Hanging from the ceiling in a line down the middle are 25,000 identical lamps, the kind that are switched on or off by pulling on a dangling length of string.

Every evening, with all the lights off, Her Majesty calls in the palace staff for a peculiar ritual. The first man walks the length of the room, pulling every string, thus turning every light on. The second man follows, pulling every second string, thus leaving the first lamp on, but switching the second off, etc. The third man follows, pulling every third string; the fourth, every fourth string. And so it goes, until the 25,000th man walks the room and pulls only the 25,000th string.

Question 1: At the end of this bizarre exercise, which lamps are on?

Actually, you’ll get a good idea of the answer by walking through the exercise with, say, 20 lamps. So try this follow-up:

Question 2: Can you explain why those particular lamps are on?

.

.

.

.

.

Answer 1: Lamps #1, 4, 9, 16, 25, etc, will be lit. Those are the squares (1 x 1 = 1, 2 x 2 = 4, 3 x 3 = 9, 4 x 4 = 16, 5 x 5 = 25, etc).

Answer 2: First, note that for any lamp, an odd number of string-pulls leaves it on, an even number switches it off.

Next, when does a given string get pulled? Only by a walker whose serial number is a factor of the serial number of the string. For example, string #12 will be pulled only by walkers #1, #2, #3, #4, #6 and #12 (all factors of 12). #19? By walkers #1 and #19 (factors of 19).

In every case, this is an even number of factors, an even number of string pulls — which means that that particular lamp will remain off…

…except that there are some numbers that have an odd number of factors. Which are those? The squares. Take 9: 1, 3, 9, or three factors. 64? 1, 2, 4, 8, 16, 32, 64, or seven factors, etc. So these strings will be pulled an odd number of times.

Thus the squares are the only lamps that will remain on.

I told you: Eccentric!