Maths Olympiad Prep

Library / /16 of 16

Combinatorics Difficulty 9.1 IMO level Prove it IMO

Five identical empty buckets of 2-liter capacity stand at the vertices of a regular pentagon. Cinderella and her wicked Stepmother go through a sequence of rounds: At the beginning of every round, the Stepmother takes one liter of water from the nearby river and distributes it arbitrarily over the five buckets. Then Cinderella chooses a pair of neighboring buckets, empties them into the river, and puts them back. Then the next round begins. The Stepmother's goal is to make one of these buckets overflow. Cinderella's goal is to prevent this. Can the wicked Stepmother enforce a bucket overflow?

Solutions — 2

Solution 1

No, the Stepmother cannot enforce a bucket overflow and Cinderella can keep playing forever. Throughout we denote the five buckets by B0,B1,B2,B3B_{0}, B_{1}, B_{2}, B_{3}, and B4B_{4}, where BkB_{k} is adjacent to bucket Bk1B_{k-1} and Bk+1B_{k+1} (k=0,1,2,3,4k=0,1,2,3,4) and all indices are taken modulo 55. Cinderella enforces that the following three conditions are satisfied at the beginning of every round:

(1) Two adjacent buckets (say B1B_{1} and B2B_{2}) are empty.

(2) The two buckets standing next to these adjacent buckets (here B0B_{0} and B3B_{3}) have total contents at most 11.

(3) The remaining bucket (here B4B_{4}) has contents at most 11.

These conditions clearly hold at the beginning of the first round, when all buckets are empty.

Assume that Cinderella manages to maintain them until the beginning of the rr-th round (r1r \geq 1). Denote by xkx_{k} (k=0,1,2,3,4k=0,1,2,3,4) the contents of bucket BkB_{k} at the beginning of this round and by yky_{k} the corresponding contents after the Stepmother has distributed her liter of water in this round.

By the conditions, we can assume x1=x2=0x_{1}=x_{2}=0, x0+x31x_{0}+x_{3} \leq 1 and x41x_{4} \leq 1. Then, since the Stepmother adds one liter, we conclude y0+y1+y2+y32y_{0}+y_{1}+y_{2}+y_{3} \leq 2. This inequality implies y0+y21y_{0}+y_{2} \leq 1 or y1+y31y_{1}+y_{3} \leq 1. For reasons of symmetry, we only consider the second case.

Then Cinderella empties buckets B0B_{0} and B4B_{4}.

At the beginning of the next round B0B_{0} and B4B_{4} are empty (condition (1) is fulfilled), due to y1+y31y_{1}+y_{3} \leq 1 condition (2) is fulfilled and finally since x2=0x_{2}=0 we also must have y21y_{2} \leq 1 (condition (3) is fulfilled).

Therefore, Cinderella can indeed manage to maintain the three conditions (1)-(3) also at the beginning of the (r+1)(r+1)-th round. By induction, she thus manages to maintain them at the beginning of every round. In particular she manages to keep the contents of every single bucket at most 11 liter. Therefore, the buckets of 22-liter capacity will never overflow.

Solution 2

We prove that Cinderella can maintain the following two conditions and hence she can prevent the buckets from overflow:

(1') Every two non-adjacent buckets contain a total of at most 11.

(2') The total contents of all five buckets is at most 32\frac{3}{2}.

We use the same notations as in the first solution. The two conditions again clearly hold at the beginning. Assume that Cinderella maintained these two conditions until the beginning of the rr-th round. A pair of non-neighboring buckets (Bi,Bi+2),i=0,1,2,3,4(B_{i}, B_{i+2}), i=0,1,2,3,4 is called critical if yi+yi+2>1y_{i}+y_{i+2}>1. By condition (2), after the Stepmother has distributed her water we have y0+y1+y2+y3+y452y_{0}+y_{1}+y_{2}+y_{3}+y_{4} \leq \frac{5}{2}. Therefore,

(y0+y2)+(y1+y3)+(y2+y4)+(y3+y0)+(y4+y1)=2(y0+y1+y2+y3+y4)5 (y_{0}+y_{2})+(y_{1}+y_{3})+(y_{2}+y_{4})+(y_{3}+y_{0})+(y_{4}+y_{1})=2(y_{0}+y_{1}+y_{2}+y_{3}+y_{4}) \leq 5

and hence there is a pair of non-neighboring buckets which is not critical, say (B0,B2)(B_{0}, B_{2}). Now, if both of the pairs (B3,B0)(B_{3}, B_{0}) and (B2,B4)(B_{2}, B_{4}) are critical, we must have y1<12y_{1}<\frac{1}{2} and Cinderella can empty the buckets B3B_{3} and B4B_{4}. This clearly leaves no critical pair of buckets and the total contents of all the buckets is then y1+(y0+y2)32y_{1}+(y_{0}+y_{2}) \leq \frac{3}{2}. Therefore, conditions (1') and (2') are fulfilled.

Now suppose that without loss of generality the pair (B3,B0)(B_{3}, B_{0}) is not critical. If in this case y012y_{0} \leq \frac{1}{2}, then one of the inequalities y0+y1+y232y_{0}+y_{1}+y_{2} \leq \frac{3}{2} and y0+y3+y432y_{0}+y_{3}+y_{4} \leq \frac{3}{2} must hold. But then Cinderella can empty B3B_{3} and B4B_{4} or B1B_{1} and B2B_{2}, respectively and clearly fulfill the conditions.

Finally consider the case y0>12y_{0}>\frac{1}{2}. By y0+y1+y2+y3+y452y_{0}+y_{1}+y_{2}+y_{3}+y_{4} \leq \frac{5}{2}, at least one of the pairs (B1,B3)(B_{1}, B_{3}) and (B2,B4)(B_{2}, B_{4}) is not critical. Without loss of generality let this be the pair (B1,B3)(B_{1}, B_{3}). Since the pair (B3,B0)(B_{3}, B_{0}) is not critical and y0>12y_{0}>\frac{1}{2}, we must have y312y_{3} \leq \frac{1}{2}. But then, as before, Cinderella can maintain the two conditions at the beginning of the next round by either emptying B1B_{1} and B2B_{2} or B4B_{4} and B0B_{0}.

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 and solution reproduced as published; topic and difficulty added by this site.