It's Like 1000 Switches When All You Need is a Light

My friends and I sometimes email each other logic problems. Yeah... we're cool like that. Because we all solved this one using different methods, I thought I'd post the puzzle as well as our methods.

The Puzzle

There are 1000 light switches labeled randomly from 1 to 1000 (uniquely), and there are 1000 people. Each person gets a number as well (randomly 1 to 1000, uniquely). All the light switches are originally off. Each person will pass by each light switch and switch the light switch if his number divides evenly with the number of the light switch. After the 1000th person passes all the lights, how many will be on?

To pad the article so no one accidentally sees the solution, enjoy this picture of an automatic light switch.

The Solution

Highlight the line to see the solution.

There will be 31 lights on.

Method 1 (Logical)

Factors nearly always come in pairs. For example, 12 has 6 factors in 3 pairs: 1 and 12, 2 and 6, and 3 and 4.

The light will only end turned on if there are an odd number of factors: 1 toggle turns on the light, 2 turns it off, 3 turns it on, etc. The only time there exists an odd number of factors is when a factor is in a pair with itself i.e. the number is a perfect square. An example of this is 16, which has 5 factors: 1 and 16, 2 and 8, and 4 and 4. Thus, light number 16 will remain on at the end of the problem.

Therefore, we need to know how many perfect squares exist that are less than or equal to 1000.

We take the highest integer that is less than 31.622. This means 31 lights will remain on.

Method 2 (Pattern)

This method can take a while. It helps to start with a smaller number. Let's use 10.

The light switches all start off.

0000000000

After person 1 walks past:

1111111111

After person 2 walks past:

1010101010

After person 3 walks past:

1000111000

After person 4 walks past:

1001111100

After person 5 walks past:

1001011101

After person 6 walks past:

1001001101

After person 7 walks past:

1001000101

After person 8 walks past:

1001000001

After person 9 walks past:

1001000011

After person 10 walks past:

1001000010

Three lights will remain on.

It may not be apparent through text, but when writing this out yourself, you'll notice that it becomes easier to update the light switches as the person's number becomes higher. This is because any light with a number less than the person's number won't be affected: any number divided by a greater number is less than 1.

Given that light switch value stop changing over time, if we were to use a larger number we would probably find a more obvious pattern. Let's try 16. You may notice that for the reasons above, the first 10 switches remain the same.

1001000010000001

Notice how the number of off lights keeps increasing between each on light? There are 2 off, then 4 off, then 6 off. The pattern is that the number of off lights continues as a multiple of 2. By determining a equation, we can extend what we know to 1000 lights and people without having to write out every iteration.

The reason for the ceiling function is that even a partial series starts with a one.

Method 3 (Brute Force)

This way is sort of cheating because it can't be done using just a paper and pencil.

To prove the number of turned-on lights, I wrote a C program that will do the calculation and show the work. Because of its length, I'm not including here. Download the source file here. You can see the output here. Note that light switch 1 is the rightmost digit on each line.

If your not worried about RAM usage, speed, or an output file showing how the solution is calculated, you can use this much shorter C source instead.

#include <string.h>
#include <stdio.h>
void main ()
{
    int lightswitch, person, sum, lights [1000];
    memset(lights, 0, sizeof(int) * 1000);
    for (person = 1; person <= 1000; ++person)
        for (lightswitch = 1000; lightswitch > 0, person <= lightswitch; --lightswitch)
            if (!(lightswitch % person)) lights[lightswitch - 1] ^= 1;
    for (sum = 0, lightswitch = 0; lightswitch < 1000; ++lightswitch)
        if (lights[lightswitch]) ++sum;
    printf("%d\r\n", sum);
}

If run from the command line, the program will confirm that 31 lights will be turned on.