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 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 to overflow? ----------------------------- (M = stepMother, C = Cinderella) What is a good first move for M? * idea1: equal distribution of water * state after step C: 0, 0, 1/5, 1/5, 1/5 * idea2: equal distribution to two not adjacent buckets * state after step C: 1/2, 0, 0, 0, 0 * one can continue from that M : 3/4, 0, 3/4, 0, 0 C : 3/4, 0, 0, 0, 0 M : 7/8, 0, 7/8, 0, 0 C : 7/8, 0, 0, 0, 0 ... * observation: this leads to almost victory of M M : 15/8, 0, 0, 0, 0 * if the buckets were just a bit smaller, it would overflow Let's try to approach the problem from the end * step -1 before M victory (M playing): * one bucket > 1 * step -1 (C playing): * at least two non-adjacent buckets > 1 * step -2 (M playing): * at least two non-adjacent buckets with sum > 1 * step -2 (C playing): * why C did not empty any of these two buckets? * state: a b c d e * WLOG (1): a+c > 1 * but also emptying a or c leads to a C loss, so * C empties a,b -> c+e > 1 or single d > 1 * + symmetrical conditions * case analysis: is there a single bucket > 1? * if YES: * there is no other such bucket, otherwise we are further in the game * WLOG (2), cancel wlog 1: a > 1 * C must empty a,b or a,e * so c+e > 1 and b+d > 1 -> state (A): a b c d e, a > 1, b+d > 1, c+e > 1 * if NO: * if C empties d,e, then: a+c > 1 * analogous for other C moves -> state (B): a b c d e, a+c>1, b+d>1, c+e>1, d+a>1, b+e>1 * is one of the states subset of the other? * For sure not (B) -> (A) * does (A) -> (B)? * <-> does (A) -> b+e>1? * does not seem so, counterexample? * 1.1, 0.4, 0.6, 0.6, 0.4 -- it works * too bad, both cases must be considered * step -3 (A) (M playing): * min(0, 1-a) + min(0, 1-b-d) + min(0, 1-c-e) > 1 * <= (implied by) * 1-a + 1-b-d + 1-c-e > 1 * <=> 2 > a+b+c+d+e * hm... can M get the sum > 2 on her move? * can we WLOG assume that? otherwise M can win in a previous step (ignoring non-strict equalities) * let's say that also getting bucket to 2 counts as overflow, we don't know if this state is achievable either * step -3 (B) (M playing): * what does it means to be able to satisfy all the cyclic conditions? * by putting water to one bucket, we help two conditions in being satisfied * so it is like being able to fill 2 liters of water into the conditions * seems that M can win only if * min(0,1-a-c) + min(0,1-b-d) + min(0,1-c-e) + min(0,1-d-a) + min(0,1-b-e) > 2 * <= 1-a-c + 1-b-d + 1-c-e + 1-d-a +1-b-e >= 2 * 3/2 >= a+b+c+d+e * this is a weaker condition than in (A) * but does it guarantee that M can actually win (we have a reversed implication in our vague reasoning) maybe, we will get back to this question later (*Q) * reversely: ignoring game objective, what is the boundary for the total amount of water that Cinderella keep under on M's turn? * we already know that M can achieve the total amount of water to be arbitrarily close to 1 on her turn (second M's strategy) Let's pursue the question about the total water amount. * M can already achieve one bucket close to 1 * 0.99, 0, 0, 0, 0 * by putting a bit to 'a' bucket, and any amount to buckets d, e, can threaten overflow, and get any amount of water to two adjecent buckets with the sum < 1 * but can M get sum > 1 on M's turn? * M: 1/2, 1/2, 1/3, 1/3, 1/3 (ignoring epsilon) * C: 0, 0, 1/3, 1/3, 1/3 * M: 2/5, 2/5, 2/5, 2/5, 2/5 * C: 0, 0, 2/5, 2/5, 2/5 * that is more than 1 but not much, where is this process converging? * C: 0, 0, x, x, x * M: y, y, y, y, y * 2y + 3(y-x) = 1 * => y = (1+3x)/5 = (2*(1/2) + 3x)/5 * that is weighted average of x and 1/2 * y is approaching 1/2 * we are approaching sum 3/2 * if M can exceed 3/2, M can probably win * also 3/2 can be the boundary that C can always keep below Let's try to make a strategy for C that would keep the total amount below 3/2 * state after M's move: a, b, c, d, e, a+b+c+d+e < 5/2 * we can suppose there is no bucket >= 1, otherwise C just empties the bucket and guarranties a+b+c+d+e < 3/2 (*T) * this is nice, since M cannot threaten overflowing in order to break the strategy * the "worst case scenario" is a+b+c+d+e = 5/2 * can we certainly find adjacent buckets with sum 1? * suppose not * a+b < 1, b+c < 1, c+d < 1, d+e < 1, e+a < 1 * summing (motivated by pursue of symmetry) of these conditions gives * 2(a+b+c+d+e) < 5 * looks like contradiction but we were arbitrarily changing < and <= as we liked, let's be more formal * formal proof attempt * a+b+c+d+e = 5/2-eps, eps > 0 * if two adjacent buckets have total amount of water strictly bigger that 1-eps, C can keep the amount of water strictly below 3/2 * suppose not: * a+b <= 1-eps, and cyclic alternations * summation gives * 2(a+b+c+d+e) <= 5-5eps * 5/2-eps = a+b+c+d+e <= 5/2 - 5eps/2 * 5/2-eps <= 5/2 - 5eps/2 * 3eps/2 <= 0 * contradicting eps > 0 * so far so good for Cinderella, she can keep the total amount under 3/2 * ad (*T): but what if M threatens two buckets at the same time? * this corresponds to the already discussed "step -1 (C)" what if M can threaten either step -1, or total amount of water >= 3/2? * AGRH, it is more complicated * C needs to also guarrantee that after her step, no not-adjacent pair of buckets will not have sum >= 1 * How many pairs like that can be threatened at once? * not all of them -- otherwise, the overall sum would be >= 5/2 * all pairs but one? * a+c, c+e, e+b, b+d >= 1 * a+b+c+d+e < 5/2 * let's try to find an example * a+c = c+e = e+b = b+d = 1 * a = e = d * b = c = 1-a * a + (1-a) + a + (1-a) + a < 5/2 * a + 2 < 5/2 <=> a < 1/2 * example: 0.4, 0.6, 0.4, 0.6, 0.4 * if C empties 'b','c', * M can get 1, 0, 0, 1, 0.4 * but if C empties 'a','b', or 'd','e' she is safe: * 0, 0, 0.4, 0.6, 0.4 * could averting a "step -1" threat prevent Cinderella from keeping the sum below 3/2? This is all complicated, let's go back to the (*Q) whether total sum of 3/2 is sufficient for M to win * simplifying observation: after C move, there are two empty buckets * state: 0, 0, c, d, e, c+d+e >= 3/2 * can M always get "step -2" or "step -1"? * of course, M can win if one of the buckets is >=1, -> let's assume otherwise * M cannot get "step -1" if c+e < 1 * suppose c+e < 1, can M get "step -2 (B)"? * that is: sum in every non-adjacent pair >= 1 * let's assume that d is already bigger than c2 and e2 (those are 'c' and 'e' in the next step) * M will add (a,b,x,0,y) * a+c2 >= 1, b+e2 >= 1, c2+e2 >= 1 * so a+b+c2+e2 >= 2, this cannot happen since c+e < 1 * contradiction * what about "step -2 (A)"? * it cannot happen as it requires the overall sum >= 2 * so it seems only c+e < 1 can prevent M from winning... without the necessity for keeping the overall water under 3/2 Let's check whether keeping c+e < 1, d < 1 is a working strategy for Cinderella: * original state: 0, 0, c, d, e * case analysis: (a) stepmother makes a bucket >= 1 * if it is 'a' or 'b', C can empty it and get back to the original state * if it is 'c', or 'e' ... it still seems too complex * Other approach: Let's say that C's default strategy would be emptying (c,d) * How could M break it? (a) putting 1 to 'a' ... but there is a trivial countermove to that (b) by making b+e bigger than 1 this is already analogous to the previous discussion: * assume after M's move, we have a, b, c', d', e', such that a,b < 1 * if a+c' >= 1, C empties c,d * if b+e' >= 1, C empties d,e * both options cannot happen since c+e < 1 * thus C can keep the buckets under the condition * QED