Maths Olympiad Prep

Library / /377 of 520

Combinatorics Difficulty 7.2 National olympiad, round 2 Find the answer

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 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?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to carefully track the student's movements and the lockers he opens. Let's break down the process step-by-step.

1. First Pass (Forward):
- The student starts at locker 1 and opens it.
- He then skips one locker and opens the next one, continuing this pattern until he reaches the end of the hall.
- This means he opens all odd-numbered lockers: 1, 3, 5, ..., 1023.
- Total lockers opened in this pass: 10242=512 \frac{1024}{2} = 512 .

2. Second Pass (Backward):
- The student turns around and starts back from locker 1024.
- He opens the first closed locker he encounters, which is locker 1022 (since all odd-numbered lockers are open).
- He then skips one closed locker and opens the next one, continuing this pattern.
- This means he opens every fourth locker: 1022, 1018, 1014, ..., 4.
- Total lockers opened in this pass: 5122=256 \frac{512}{2} = 256 .

3. Third Pass (Forward):
- The student turns around again and starts from locker 1.
- He opens the first closed locker he encounters, which is locker 2.
- He then skips one closed locker and opens the next one, continuing this pattern.
- This means he opens every eighth locker: 2, 10, 18, ..., 1018.
- Total lockers opened in this pass: 2562=128 \frac{256}{2} = 128 .

4. Fourth Pass (Backward):
- The student turns around again and starts from locker 1024.
- He opens the first closed locker he encounters, which is locker 1022.
- He then skips one closed locker and opens the next one, continuing this pattern.
- This means he opens every sixteenth locker: 1022, 1006, 990, ..., 14.
- Total lockers opened in this pass: 1282=64 \frac{128}{2} = 64 .

5. Fifth Pass (Forward):
- The student turns around again and starts from locker 1.
- He opens the first closed locker he encounters, which is locker 6.
- He then skips one closed locker and opens the next one, continuing this pattern.
- This means he opens every thirty-second locker: 6, 38, 70, ..., 998.
- Total lockers opened in this pass: 642=32 \frac{64}{2} = 32 .

6. Sixth Pass (Backward):
- The student turns around again and starts from locker 1024.
- He opens the first closed locker he encounters, which is locker 1014.
- He then skips one closed locker and opens the next one, continuing this pattern.
- This means he opens every sixty-fourth locker: 1014, 950, 886, ..., 54.
- Total lockers opened in this pass: 322=16 \frac{32}{2} = 16 .

7. Seventh Pass (Forward):
- The student turns around again and starts from locker 1.
- He opens the first closed locker he encounters, which is locker 22.
- He then skips one closed locker and opens the next one, continuing this pattern.
- This means he opens every 128th locker: 22, 150, 278, ..., 918.
- Total lockers opened in this pass: 162=8 \frac{16}{2} = 8 .

8. Eighth Pass (Backward):
- The student turns around again and starts from locker 1024.
- He opens the first closed locker he encounters, which is locker 982.
- He then skips one closed locker and opens the next one, continuing this pattern.
- This means he opens every 256th locker: 982, 726, 470, ..., 214.
- Total lockers opened in this pass: 82=4 \frac{8}{2} = 4 .

9. Ninth Pass (Forward):
- The student turns around again and starts from locker 1.
- He opens the first closed locker he encounters, which is locker 86.
- He then skips one closed locker and opens the next one, continuing this pattern.
- This means he opens every 512th locker: 86, 598.
- Total lockers opened in this pass: 42=2 \frac{4}{2} = 2 .

10. Tenth Pass (Backward):
- The student turns around again and starts from locker 1024.
- He opens the first closed locker he encounters, which is locker 854.
- This is the only locker he opens in this pass.
- Total lockers opened in this pass: 22=1 \frac{2}{2} = 1 .

Thus, the last locker he opens is locker number 854 \boxed{854} .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.