Problem:
A bored student walks down a hall that contains a row of closed lockers, numbered to . He opens the locker numbered , and then alternates between skipping and opening each closed 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?
Solution:
Suppose that there are lockers in the row, and let be the number of the last locker opened, once all the lockers are open. After the student makes his first pass along the row, there are closed lockers left. These closed lockers all have even numbers and are in descending order from where the student is standing. Now renumber the closed lockers from to , starting from the end where the student is standing. Notice that the locker originally numbered (where is even) is now numbered . Thus, because is the number of the last locker opened with this new numbering, we have
Solving for we find
Iterate this recursion once to obtain
When there are lockers to start with, the last locker to be opened is numbered . Apply repeatedly to to find that , , and .
Follow the given solution to the recursion , which can be written in the form
Because and , it follows that
These formulas may be combined to yield
for all nonnegative . In particular, .
Query: How would the solution change if there were lockers in the hall?
The problems on this page are the property of the MAA's American Mathematics Competitions