Tee Jet Whaw

There are 10,000 lights in a line which are all turned off. Each light is controlled by a pull cord. 10,000 people come by. The 1st person pulls all of the cords; the 2nd person pulls every 2nd cord – so the 2nd, 4th, 6th etc. The 3rd person pulls the cords that are multiples of 3, the 4th person all cords that are multiples of 4 and so on. After all 10,000 people have passed how many lights remain on?

Scroll down for the solution

.

.

.

.

.

.

.

.

.

.

Solution

Note that a light will be on at the end only if its cord is pulled an odd number of times (since they all start off). Due to the way in which the cords are pulled, this means the number must have an odd number of divisors.

The question then becomes, which numbers have odd numbers of divisors? We can think of it as follows…

If a number can be divided by another to give a whole number answer, then it in fact has two divisors. For example, 12 can be divided by 1 and 12, 2 and 6, or 3 and 4. If one divisor exists, then it has a corresponding partner – they come in pairs.

This is true unless both numbers are the same. For example, 16 is equal to 4 times 4 and so here we only add one to the total number of divisors. [Bonus: can you write out all of the divisors of 16?]

But what does it mean to have the same number as a repeated divisor? Well, this is exactly the definition of a square number! Therefore, we add one to the total number of divisors whenever the number is a perfect square.

Going back to our original question, we can conclude that all numbers will have an even number of divisors (as they each come in a pair), except for square numbers. These will have an even number due to the pairs, plus an additional one from the square root. Therefore, the only numbers that have an odd number of divisors (and by extension will remain on at the end of the process), are the square numbers.

So, finally, how many square numbers are there between 1 and 10,000? Well, 10,000 is equal to 100² which means the first 100 square numbers fall in the required range. Thus, the answer is that 100 lights will remain on.