Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution 1)
(→‎Solution 1)
Line 4: Line 4:
 
== Solutions ==
 
== Solutions ==
 
=== Solution 1 ===
 
=== 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 \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.
+
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.
  
 
=== Solution 2  ===
 
=== Solution 2  ===

Revision as of 18:51, 3 June 2020

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.

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

list all the numbers from 1 through 1024, then do the process yourself!!!! It will take about 25 minutes, but thats ok! eventually you will get 342

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_AIME_Problems/Problem_9&oldid=123612"