CombinatoricsDifficulty 7.5National Olympiad, round 2Prove itUnited States
Problem:
An underground burrow consists of an infinite sequence of rooms labeled by the integers …,−3,−2,−1,0,1,2,3,…. Initially, some of the rooms are occupied by one or more rabbits.
Each rabbit wants to be alone. Thus, if there are two or more rabbits in the same room (say, room m), half the rabbits (rounding down) will flee to room m−1, and half (also rounding down) to room m+1. Once per minute, this happens simultaneously in all rooms that have two or more rabbits. For example, if initially all rooms are empty except for 5 rabbits in room #12 and 2 rabbits in room #13, then after one minute, rooms #11-#14 will contain 2, 2, 2, and 1 rabbits, respectively, and all other rooms will be empty.
Now suppose that initially there are k+1 rabbits in room k for each k=0,1,2,…,9,10, and all other rooms are empty.
a. Show that eventually the rabbits will stop moving.
b. Determine which rooms will be occupied when this occurs.
Solution
Solution:
First, we show that the process eventually stops.
Call a room interior if it is occupied, or if at least one room somewhere to its left and at least one room somewhere to its right are occupied.
We claim that it is not possible for a gap of two or more consecutive unoccupied interior rooms to ever appear, given that no such gap exists in the initial configuration. For consider the first moment when such a gap appears, and let A and B be the two leftmost rooms in that gap. Either A or B must have been occupied at the previous step. But when rabbits leave A, some of them must go to B, and vice versa, creating a contradiction. This proves the claim.
Rabbits move in pairs, from room k to rooms k−1 and k+1. Since k+k=(k−1)+(k+1), the sum of the rabbits' room numbers is constant. However, the sum of their room numbers' squares increases at every step, since (k−1)2+(k+1)2=k2+k2+2. This shows that the rabbits' configuration can never recur, neither exactly nor up to a shift.
Up to a shift, there are finitely many possible configurations of rabbits with no internal gaps of two or more rooms. Thus we have shown that the process terminates after a finite number of steps.
Now we will determine the final configuration.
We claim that the final configuration cannot have two empty interior rooms (consecutive or otherwise!). In particular, we will prove by strong induction on n that at no time do n consecutive interior rooms contain n−2 or fewer rabbits.
Base case (n=0): In this case, the claim is that 2 consecutive interior rooms cannot contain 0 rabbits. We already proved this above.
Inductive step: Suppose the proposition has been proven up to some fixed n (inclusive). We wish to show that n+1 consecutive interior rooms cannot ever contain n−1 or fewer rabbits. Aiming for a contradiction, suppose that, at some time, some n+1 consecutive interior rooms do contain n−1 or fewer rabbits. We claim those rooms must contain 0,n−11,1,…,1,0 rabbits respectively. Proof: Any other possible distribution among those rooms would include at least three empty rooms 0,r rooms……,,0,n−r−2 rooms………,0. By the inductive hypothesis, there must be at least r+1 rabbits in the first r+2 rooms and at least n−1−r rabbits in the last n−r rooms. But that makes n rabbits, which is a contradiction. The claim is proved; let us proceed.
Let the two rooms on the ends of the 0,n−11,1,…,1,0 sequence be room k and room k+n. These rooms must have been occupied at some point (since they are interior). Without loss of generality, suppose room k contained a rabbit at least as recently as room k+n, and consider the last moment when room k was occupied. At the next moment, a rabbit must have fled from room k to room k+1. After that time, the total number of rabbits in rooms k,…,k+n cannot have changed. Thus, the state 0,n−11,1,…,1,0 was attained at that moment.
If at that moment rooms k and k+n discharged simultaneously, then before they did so, rooms k+1,k+2,…,k+n−1 must have contained at most n−3 rabbits. If room k+n was already empty when room k discharged for the last time, then rooms k+1,k+2,…,k+n must have contained at most n−2 rabbits. Either way, the inductive hypothesis is violated, which completes our proof that the final configuration does not have two empty interior rooms.
We have determined that the final configuration consists of a sequence of consecutive rooms of which all, or all but one, are occupied by 1 rabbit each. There are 66 rabbits total. We also know that the sum of the rabbits' room numbers never changes from its initial value of (0)(1)+(1)(2)+(2)(3)+⋯+(10)(11)=440.
To find a configuration meeting the requirements, we first consider whether the rabbits could be in 66 consecutive rooms. If so, their median room number would have to be 66440=632, but this is neither an integer nor half an integer, so we can rule it out.
Thus the rabbits occupy some 67 consecutive rooms (except one), centered somewhere near room 7. The 67 rooms centered at room 7 are rooms −26,…,40, with a sum of 469. Thus, to achieve a sum of 440, we can fill all these rooms except room 29. That's a possible final configuration.
Finally, we verify that this answer is unique. If the 67 consecutive rooms are farther to the left, then their sum is at most (−27)+(−26)+⋯+39=402, and omitting one room from this sum can't get us to 440. If they are further to the right, then their sum is at least (−25)+(−24)+⋯+41=536, which is likewise too high. Thus, the configuration we computed must be the correct one.
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: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.