Circular Locker Problem

From a friend's brother:

There are 1000 lockers and 1000 students. The lockers are arranged in a circle, all closed. The 1st student opens all the lockers. The 2nd student closes every other locker. The 3rd student goes to every 3rd locker. If it’s open he closes it, if it’s closed, he opens it. When he gets to locker #999, he continues to locker #2 and continues until he reaches a locker that he has already touched. The 4th student goes to every 4th locker: again, if it’s closed, he opens it, if it’s open, he closes it. Every student after that does the same, until student #1000, who will obviously just open or close locker #1000. After they are all finished, which lockers will be open?

Solution


First, let's think about what happens when student $n$ does his turn.

If $n$ is relatively prime to 1000, that is, $n$ does not contain any factor of 2 or 5, then $n$ will touch all the lockers exactly once. For example, student #3 will go touching lockers 3,6,...,999,2,5,...,998,1,4,7,...,997,1000. In this case student $n$ behaves exactly like student #1.

If $n$ is a multiple of $2$ or $5$, then let $d = \gcd(1000,n)$ Student $n$ touches locker $m$ if and only if $d$ divides $m$. For example, if $n=16$, then $d = 8$. Student #16 will go touching lockers 16,32,...,992,8,24,...,1000, which are exactly all multiples of 8. In this case, student $n$ behaves exactly like student #8.

Now, how many students have numbers that are NOT relatively prime to 1000? Such students must have numbers in the form of $n = 2^a 5^b$ We can enumerate the possibilities:

If $b=0$, then the student numbers are: 2,4,8,16,32,64,128,256,512, for a total of 9 students. Remember that students #16,32,...,512 behave exactly like student #8,and there are 6 of them, so it's equivalent to student #8 going 6 extra times. Their effects cancel out pairwise. So we only need to consider the effects of students #2,4,8.

If $b=1$, then the student numbers are: 5,10,20,40,80,160,320,640, for a total of 8 students. Remember that students #80,...,640 behave exactly like student #40,and there are 4 of them, so their effects cancel out pairwise. So we only need to consider the effects of students #5,10,20,40.

If $b=2$, then the student numbers are: 25,50,100,200,400,800, for a total of 6 students. Remember that students #400,8000 behave exactly like student #200, so their effects cancel out. So we only need to consider the effects of students #25,50,100,200.

If $b=3$, then the student numbers are: 125,250,500,1000.

If $b=4$, then the student number is: 625, which behaves like student #125, and thus cancels the effect of student #125.

So in total, there are 9+8+6+4+1 = 28 numbers that are not relatively prime to 1000, so there are an even numbers of students that are relatively prime. Each of these students touches all lockers exactly once, so their effects again cancel out pairwise. Thus, the student numbers that we need to consider are: (grouped by their largest factor of 2):
5,25
2,10,50,250
4,20,100,500
8,40,200,1000

In order to determine if locker $n$ is closed or open, find all numbers above that divides $n$. If there are even such numbers, then the locker is close, otherwise it's open.

For example, 120 = 3 x 5 x 8, so 120 is divisible by 2,4,8, 5,10,20,40. That means locker #120 is open.

For a more explicit list of open lockers, the following are the open lockers:
1. Lockers with numbers (not divisible by 5 or divisible by 25), and (divisible by 2 but not by 4, or divisible by 8).
2. Lockers with numbers divisible by 5 but not 25, and (divisible by 4 but not by 8).