HMMT 二月 2004 · COMB 赛 · 第 1 题

HMMT February 2004 — COMB Round — Problem 1

There are 1000 rooms in a row along a long corridor. Initially the first room contains 1000 people and the remaining rooms are empty. Each minute, the following happens: for each room containing more than one person, someone in that room decides it is too crowded and moves to the next room. All these movements are simultaneous (so nobody moves more than once within a minute). After one hour, how many different rooms will have people in them?

解析

There are 1000 rooms in a row along a long corridor. Initially the first room contains 1000 people and the remaining rooms are empty. Each minute, the following happens: for each room containing more than one person, someone in that room decides it is too crowded and moves to the next room. All these movements are simultaneous (so nobody moves more than once within a minute). After one hour, how many different rooms will have people in them? Solution: 31 We can prove by induction on n that the following pattern holds for 0 ≤ n ≤ 499: after 2 n minutes, the first room contains 1000 − 2 n people and the next n rooms each contain 2 people, and after 2 n + 1 minutes, the first room contains 1000 − (2 n + 1) people, the next n rooms each contain 2 people, and the next room after that contains 1 person. So, after 60 minutes, we have one room with 940 people and 30 rooms with 2 people each.