1996 AIME Problem 9

Question

A bored student walks down a hall that contains a row of closed lockers, numbered

1

to

1024.

He opens locker

1,

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?

Answer

Answer: 342

Concepts:process simulation pattern recognition arithmetic sequence

Difficulty rating: 2270

Small hint:

After each trip, the still-closed lockers form an arithmetic sequence

Big hint:

Record only the first term, common difference, and number of terms after each trip

Solution:

On every trip the student opens the first, third, fifth, and so on among the remaining lockers in his direction of travel. Tracking the closed arithmetic sequence after each trip gives:

trip	first	difference	count
$1$	$2$	$2$	$512$
$2$	$2$	$4$	$256$
$3$	$6$	$8$	$128$
$4$	$6$	$16$	$64$
$5$	$22$	$32$	$32$
$6$	$22$	$64$	$16$
$7$	$86$	$128$	$8$
$8$	$86$	$256$	$4$
$9$	$342$	$512$	$2$

Thus only lockers

342

and

854

remain after the ninth trip. On the tenth trip, starting from the right, locker

854

is opened and

342

remains. Therefore the last locker opened is

342.