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
(
dmoews@fastmail.fm )
To the puzzle;
to the puzzles list;
to the home page