Difference between revisions of "1996 AIME Problems/Problem 9"
(tex) |
(→Solution) |
||
Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
− | 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 <math>4</math>, leaving only lockers <math>2 \mod{8}</math> and <math>6 \mod{8}</math>. Then he goes ahead and opens all lockers <math>2 \mod {8}</math>, leaving lockers either <math>6 \mod {16}</math> or <math>14 \mod {16}</math>. He then goes ahead and opens all lockers <math>14 \mod {16}</math>, leaving the lockers either <math>6 \mod {32}</math> or <math>22 \mod {32}</math>. He then goes ahead and opens all lockers <math>6 \mod {32}</math>, leaving <math>22 \mod {64}</math> or <math>54 \mod {64}</math>. He then opens <math>54 \mod {64}</math>, leaving <math>22 \mod {128}</math> or <math>86 \mod {128}</math>. He then opens <math>22 \mod {128}</math> and leaves <math>86 \mod {256}</math> and <math>214 \mod {256}</math>. He then opens all <math>214 \mod {256}</math>, so we have <math>86 \mod {512}</math> and <math>342 \mod {512}</math>, leaving lockers <math>86, 342, 598</math>, and <math>854</math>, and he is at where he started again. He then opens <math>86</math> and <math>598</math>, and then goes back and opens locker number <math> | + | 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 <math>4</math>, leaving only lockers <math>2 \mod{8}</math> and <math>6 \mod{8}</math>. Then he goes ahead and opens all lockers <math>2 \mod {8}</math>, leaving lockers either <math>6 \mod {16}</math> or <math>14 \mod {16}</math>. He then goes ahead and opens all lockers <math>14 \mod {16}</math>, leaving the lockers either <math>6 \mod {32}</math> or <math>22 \mod {32}</math>. He then goes ahead and opens all lockers <math>6 \mod {32}</math>, leaving <math>22 \mod {64}</math> or <math>54 \mod {64}</math>. He then opens <math>54 \mod {64}</math>, leaving <math>22 \mod {128}</math> or <math>86 \mod {128}</math>. He then opens <math>22 \mod {128}</math> and leaves <math>86 \mod {256}</math> and <math>214 \mod {256}</math>. He then opens all <math>214 \mod {256}</math>, so we have <math>86 \mod {512}</math> and <math>342 \mod {512}</math>, leaving lockers <math>86, 342, 598</math>, and <math>854</math>, and he is at where he started again. He then opens <math>86</math> and <math>598</math>, and then goes back and opens locker number <math>854</math>, leaving locker number <math>\boxed{342}</math> untouched. He opens that locker. |
== See also == | == See also == |
Revision as of 16:29, 15 March 2009
Problem
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?
Solution
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.
See also
1996 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |