AIME 1996 · 第 9 题

Solutions

Solution 1

On his first pass, he opens all of the odd lockers. So there are only even lockers closed. Then he opens the lockers that are multiples of $4$, leaving only lockers $2 \pmod{8}$ and $6 \pmod{8}$. Then he goes ahead and opens all lockers $2 \pmod {8}$, leaving lockers either $6 \pmod {16}$ or $14 \pmod {16}$. He then goes ahead and opens all lockers $14 \pmod {16}$, leaving the lockers either $6 \pmod {32}$ or $22 \pmod {32}$. He then goes ahead and opens all lockers $6 \pmod {32}$, leaving $22 \pmod {64}$ or $54 \pmod {64}$. He then opens $54 \pmod {64}$, leaving $22 \pmod {128}$ or $86 \pmod {128}$. He then opens $22 \pmod {128}$ and leaves $86 \pmod {256}$ and $214 \pmod {256}$. He then opens all $214 \pmod {256}$, so we have $86 \pmod {512}$ and $342 \pmod {512}$, leaving lockers $86, 342, 598$, and $854$, and he is at where he started again. He then opens $86$ and $598$, and then goes back and opens locker number $854$, leaving locker number $\boxed{342}$ untouched. He opens that locker.

~edit made by Yiyj1: the $2 \pmod 8$ and $6\pmod 8$ are the same as $2 \pmod 4$.

Solution 2

We can also solve this with recursion. Let $L_n$ be the last locker he opens given that he started with $2^n$ lockers. Let there be $2^n$ lockers. After he first reaches the end of the hallway, there are $2^{n-1}$ lockers remaining. There is a correspondence between these unopened lockers and if he began with $2^{n-1}$ lockers. The locker $y$ (if he started with $2^{n-1}$ lockers) corresponds to the locker $2^n+2-2y$ (if he started with $2^n$ lockers). It follows that $L_{n} = 2^{n} +2 -2L_{n-1}$ as they are corresponding lockers. We can compute $L_1=2$ and use the recursion to find $L_{10}=\boxed{342}$

Solution 3 (bash)

List all the numbers from $1$ through $1024$, then do the process yourself!!! It will take about 25 minutes (if you don't start to see the pattern), but that's okay, eventually, you will get $\boxed{342}$.

(Note: If you try to do this, first look through all the problems! -Guy)

Solution 4 (bash but it takes less than 3 minutes)

Note that whenever the student makes a pass starting on one end, the number at the other end of that line will remain. This is very important.

Pass $0$:

$1,2,3,4...,1024$

Pass $1$:

$2,4,6,...,1022, 1024$

Pass $2$ (reversed, note that we take the second-to-last term of the previous sequence for every new sequence):

$1022, 1018,...,(2+4), 2$

Pass $3$:

$6, (6+4+4),...,(1022-4-4), 1022$

Pass $4$:

$1014, (1014-16),..., (6+16), 6$

Pass $5$:

$22, (22+32),..., (1014-32), 1014$

Pass $6$:

$982, (982-64),..., (22 + 64), 22$

Pass $7$:

$86, (86+128),..., (982-128), 982$

Pass $8$:

$854, (854-256),..., (86+256), 86$

Pass $9$:

$342, (342+512)$

Pass $10$:

$342$

The answer is therefore $\boxed{342}.$

~martianrunner

---

Edit from EthanSpoon, Doing this with only even numbers will make it faster. You'll see. 02496

Edit from Iamaimogoldmedalist. Doing some few rounds in your head till you get Multiples of 4 or possibly numbers of the form 8k+2 will enhance your speed.