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 istoo crowded and moves to the next room. All these movements are simultaneous (sonobody moves more than once within a minute). After one hour, how many differentrooms 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 istoo crowded and moves to the next room. All these movements are simultaneous (sonobody moves more than once within a minute). After one hour, how many differentrooms 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 eachcontain 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.