2
$\begingroup$

Going through the official solutions of IMO'09 (can be found here: http://www.imo-official.org/problems/IMO2009SL.pdf), namely Solution 2 for the C5 problem. Here goes:

Statement

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?

Solution 2

Throughout we denote the five buckets by $B_0, B_1, B_2, B_3$, and $B_4$, where $B_k$ is adjacent to bucket $B_{k−1}$ and $B_{k+1}$ ($k = 0, 1, 2, 3, 4$) and all indices are taken modulo 5.

Denote by $x_k$ ($k = 0, 1, 2, 3, 4$) the contents of bucket $B_k$ at the beginning of the round and by $y_k$ the corresponding contents after the Stepmother has distributed her liter of water in this round.

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 1.

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

The two conditions clearly hold at the beginning. Assume that Cinderella maintained these two conditions until the beginning of the $r$-th round. A pair of non-neighboring buckets $(B_i, B_{i+2}), i = 0, 1, 2, 3, 4$ is called critical if $y_i + y_{i+2} > 1$. By condition (2'), after the Stepmother has distributed her water we have $y_0 + y_1 + y_2 + y_3 + y_4 \leq \frac{5}{2}$. Therefore, $$ (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 $(B_0, B_2)$. Now, if both of the pairs $(B_3, B_0)$ and $(B_2, B_4)$ are critical, we must have $y_1 < \frac{1}{2}$ and Cinderella can empty the buckets $B_3$ and $B_4$. This clearly leaves no critical pair of buckets and the total contents of all the buckets is then $y_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 $(B_3, B_0)$ is not critical. If in this case $y_0 \leq \frac{1}{2}$, then one of the inequalities $y_0 + y_1 + y_2 \leq \frac{3}{2}$ and $y_0 + y_3 + y_4 \leq \frac{3}{2}$ must hold. But then Cinderella can empty $B_3$ and $B_4$ or $B_1$ and $B_2$, respectively and clearly fulfill the conditions.

...

This - the last paragraph - is where I'm getting lost. I don't see how condition (1') is satisfied. For it to be satisfied we need $y_i+y_{i+2}\leq1$ for all $i$ after emptying. Assume in the last paragraph that of the two inequalities $y_0+y_1+y_2\leq\frac{3}{2}$ holds and we empty buckets $B_3$ and $B_4$. We then have:

$y_0+y_2\leq1, y_3+y_0\leq1$, by assumption that $(B_0, B_2)$ and $(B_3, B_0)$ are not critical;

$y_2+y_4=y_2\leq1$, since we empty $B_4$ and assume $(B_0, B_2)$ is not critical, from which it follows that $y_2\leq1$.

For condition (1') to be satisfied, we are left to check $y_1+y_3=y_4+y_1=y_1\leq1$ (where two equalities follow from the emptying of $B_3$ and $B_4$), and this is precisely what I fail to grasp.

How come $y_1\leq1$?

Thanks.

$\endgroup$
1
+50
$\begingroup$

If $y_1>1$ then $y_0+y_3+y_4\le3/2$, and Cinderella can empty $B_1$ and $B_2$

If $y_4>1$ then $y_0+y_1+y_2\le3/2$, and Cinderella can empty $B_3$ and $B_4$

They can't both be greater than $1$ because their sum was at most $1$ before the Stepmother's previous move.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In this case conditions $y_2+y_4\leq1$ and $y_4+y_1\leq1$ after emptying of $B_1$ and $B_2$ will be reduced to $y_4\leq1$, which doesn't seem any easier than the original $y_1\leq1$. $\endgroup$ – user75619 Jun 2 '18 at 14:56
  • $\begingroup$ $y_1$ and $y_4$ can't both be greater than $1$ because their sum was at most $1$ before the Stepmother's turn. $\endgroup$ – Michael Jun 2 '18 at 15:06
  • $\begingroup$ Sounds plausible. I'll go through it once more and be back with the bounty award. $\endgroup$ – user75619 Jun 2 '18 at 15:30
  • $\begingroup$ At your convenience please add some details, such as your Comment above, to the body of the Question. $\endgroup$ – hardmath Jun 2 '18 at 15:45
  • $\begingroup$ So, if I understand well, if the bucket has a capacity of $\geq2$, Stepmother can't succeed in overflowing some bucket; otherwise she can. Can anyone draft an example for both cases? I tried starting with 0 in all 5 buckets and then adding 1 liter in various ways, but I can't achieve an overflow in any of the two cases. Thank you! $\endgroup$ – Creton Laplace Jun 27 '18 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.