HMMT 十一月 2021 · 冲刺赛 · 第 32 题

HMMT November 2021 — Guts Round — Problem 32

[17] There are N lockers, labeled from 1 to N , placed in clockwise order around a circular hallway. Initially, all lockers are open. Ansoon starts at the first locker and always moves clockwise. When she is at locker n and there are more than n open lockers, she keeps locker n open and closes the next n open lockers, then repeats the process with the next open locker. If she is at locker n and there are at most n lockers still open, she keeps locker n open and closes all other lockers. She continues this process until only one locker is left open. What is the smallest integer N > 2021 such that the last open locker is locker 1? √ ◦ AP

解析

[17] There are N lockers, labeled from 1 to N , placed in clockwise order around a circular hallway. Initially, all lockers are open. Ansoon starts at the first locker and always moves clockwise. When she is at locker n and there are more than n open lockers, she keeps locker n open and closes the next n open lockers, then repeats the process with the next open locker. If she is at locker n and there are at most n lockers still open, she keeps locker n open and closes all other lockers. She continues this process until only one locker is left open. What is the smallest integer N > 2021 such that the last open locker is locker 1? Proposed by: Hahn Lheem Answer: 2046 n Solution: Note that in the first run-through, we will leave all lockers 2 − 1 open. This is be- n n cause after having locker 2 − 1 open, we will close the next 2 − 1 lockers and then start at locker n n n +1 2 − 1 + 2 − 1 + 1 = 2 − 1. Now we want 1 to be the last locker that is open. We know that if N < 2046 , then closing 1023 lockers after 1023 will lead us to close locker 1 . However, if N = 2046 , then locker 1 will stay open, 3 will close, 7 will stay open, closing the next 10 and then 1 stays open and we close locker 7 , therefore N = 2046 does work. √ AP ◦