Difference between revisions of "1996 AIME Problems/Problem 9"

Latest revision as of 22:51, 6 September 2023

Problem

A bored student walks down a hall that contains a row of closed lockers, numbered $1$ to $1024$ . 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?

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.

Lockers that are $2 \pmod{8}$ and $6 \pmod{8}$ are just lockers that are $2 \pmod{4}$ . Edit by Yiyj1

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)

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

@@ Line 1: / Line 1: @@
 == Problem ==
-A bored student walks down a hall that contains a row of closed lockers, numbered 1 to 1024. 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?
+A bored student walks down a hall that contains a row of closed lockers, numbered <math>1</math> to <math>1024</math>. 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 ==
+== Solutions ==
-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 mod 8 and 6 mod 8. Then he goes ahead and opens all lockers 2 mod 8, leaving lockers either 6 mod 16 or 14 mod 16. He then goes ahead and opens all lockers 14 mod 16, leaving the lockers either 6 mod 32 or 22 mod 32. He then goes ahead and opens all lockers 6 mod 32, leaving 22 mod 64 or 54 mod 64. He then opens 54 mod 64, leaving 22 mod 128 or 86 mod 128. He then opens 22 mod 128 and leaves 86 mod 256 and 214 mod 256. He then opens all 214 mod 256, so we have 86 mod 512 and 342 mod 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 598, leaving locker number 342 untouched. He opens that locker.
+=== 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 <math>4</math>, leaving only lockers <math>2 \pmod{8}</math> and <math>6 \pmod{8}</math>. Then he goes ahead and opens all lockers <math>2 \pmod {8}</math>, leaving lockers either <math>6 \pmod {16}</math> or <math>14 \pmod {16}</math>. He then goes ahead and opens all lockers <math>14 \pmod {16}</math>, leaving the lockers either <math>6 \pmod {32}</math> or <math>22 \pmod {32}</math>. He then goes ahead and opens all lockers <math>6 \pmod {32}</math>, leaving <math>22 \pmod {64}</math> or <math>54 \pmod {64}</math>. He then opens <math>54 \pmod {64}</math>, leaving <math>22 \pmod {128}</math> or <math>86 \pmod {128}</math>. He then opens <math>22 \pmod {128}</math> and leaves <math>86 \pmod {256}</math> and <math>214 \pmod {256}</math>. He then opens all <math>214 \pmod {256}</math>, so we have <math>86 \pmod {512}</math> and <math>342 \pmod {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.
+--------------------------
+Lockers that are <math>2 \pmod{8}</math> and <math>6 \pmod{8}</math> are just lockers that are <math>2 \pmod{4}</math>. Edit by [[User: Yiyj1|Yiyj1]]
+=== Solution 2  ===
+We can also solve this with recursion. Let <math>L_n</math> be the last locker he opens given that he started with <math>2^n</math> lockers. Let there be <math>2^n</math> lockers. After he first reaches the end of the hallway, there are <math>2^{n-1}</math> lockers remaining. There is a correspondence between these unopened lockers and if he began with <math>2^{n-1}</math> lockers. The locker <math>y</math> (if he started with <math>2^{n-1}</math> lockers) corresponds to the locker <math>2^n+2-2y</math> (if he started with <math>2^n</math> lockers). It follows that <math>L_{n} = 2^{n} +2 -2L_{n-1}</math> as they are corresponding lockers. We can compute <math>L_1=2</math> and use the recursion to find <math>L_{10}=\boxed{342}</math>
+=== Solution 3 (bash)===
+List all the numbers from <math>1</math> through <math>1024</math>, 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 <math>\boxed{342}</math>.
+(Note: If you try to do this, first look through all the problems! -Guy)
+--------------------------
+Edit from EthanSpoon, Doing this with only even numbers will make it faster.
+You'll see.
 == See also ==
-*[[1996 AIME Problems]]
+{{AIME box|year=1996|num-b=8|num-a=10}}
-{{AIME box|year=1996|num-b=8|num-a=10}}
+[[Category:Intermediate Combinatorics Problems]]
+{{MAA Notice}}

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

Page

Toolbox

Search