1996 AIME Problems/Problem 9
A bored student walks down a hall that contains a row of closed lockers, numbered to . He opens the locker numbered 1, and then alternates between skipping and opening each locker thereafter. When he reaches the end of the hall, the student turns around and starts back. He opens the first closed locker he encounters, and then alternates between skipping and opening each closed locker thereafter. The student continues wandering back and forth in this manner until every locker is open. What is the number of the last locker he opens?
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 , leaving only lockers and . Then he goes ahead and opens all lockers , leaving lockers either or . He then goes ahead and opens all lockers , leaving the lockers either or . He then goes ahead and opens all lockers , leaving or . He then opens , leaving or . He then opens and leaves and . He then opens all , so we have and , leaving lockers , and , and he is at where he started again. He then opens and , and then goes back and opens locker number , leaving locker number untouched. He opens that locker.
We can also solve this with recursion. Let be the last locker he opens given that he started with lockers. Let there be lockers. After he first reaches the end of the hallway, there are lockers remaining. There is a correspondence between these unopened lockers and if he began with lockers. The locker (if he started with lockers) corresponds to the locker (if he started with lockers). It follows that as they are corresponding lockers. We can compute and use the recursion to find
Solution 3 (bash)
List all the numbers from through , then do the process yourself!!! It will take about 25 minutes, but that's okay, eventually you will get .
(Note: If you try to do this, first look through all the problems! -Guy)
|1996 AIME (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|