Instead of a closed locker, think of a 0 bit, and instead of an open locker, use a 1 bit. Read off the binary expansion of a number from our lockers, using locker 1 as the least significant bit and 1000 as the most significant. At the start, not all lockers are open, so the number is between 0 and 2^1000-2, inclusive. Since each student always closes a locker, this fact remains true throughout the process, so the state of the lockers is determined by the residue class of this number modulo 2^1000-1. Student 1's actions decrement the number by 1, unless it is 0, when they change it to 2^1000-2, so in all cases, 1 is subtracted from its residue class. Similarly, student k's actions subtract 2^(k-1) from the number's residue class, for k=2, 3, ..., 1000. But

1 + 2 + 2^2 + ... + 2^999 = 2^1000-1,

so after all the students have passed the number's residue class is the same as it was at the start, and hence the lockers are all in the same state as they were at the start.

David Moews ( )

To the puzzle; to the puzzles list; to the home page