Let $k$ be a positive real. $A$ and $B$ play the following game: at the start, there are $80$ zeroes arrange around a circle. Each turn, $A$ increases some of these $80$ numbers, such that the total sum added is $1$. Next, $B$ selects ten consecutive numbers with the largest sum, and reduces them all to $0$. $A$ then wins the game if he/she can ensure that at least one of the number is $\geq k$ at some finite point of time. Determine all $k$ such that $A$ can always win the game.
Problem
Source: China TST Test 1 Day 2 Q6
Tags: combinatorics, game, China TST
11.03.2019 13:02
https://artofproblemsolving.com/community/c6h355786p1932930 Edit:Oops!I was sniped by the title!
12.03.2019 09:46
Nearly every contestant was reminded of the Cinderell's SL problem, but this one was much harder, with an answer like $\frac{363}{140}$.
12.03.2019 09:55
I would have time to write my proof after TST phase 2. if still no proof is published then.
12.03.2019 15:04
The proof can be found in the following paper: Marijke Hans L. Bodlaender, Cor A. J. Hurkens, Vincent J. J. Kusters, Frank Staals, Gerhard J. Woeginger, Hans Zantema: Cinderella versus the Wicked Stepmother https://link.springer.com/chapter/10.1007%2F978-3-642-33475-7_5 The desired value $k$ coincides with $F(80,10)$ in the notation of that paper. By Lemma 1 in the paper $F(80,10)=F(8,1)$, and by Theorem 5 in the paper $F(8,1)=H_7=363/140$.
13.03.2019 15:37
Sorry but I could not visit the website. However, it would be reasonale to suppose that in the paper, Cinderella could choose ANY 10 buckets while in this problem she could only choose 10 with THE LARGEST SUM. This leads to a serious difference though the answer is the same. test20 wrote: The proof can be found in the following paper: Marijke Hans L. Bodlaender, Cor A. J. Hurkens, Vincent J. J. Kusters, Frank Staals, Gerhard J. Woeginger, Hans Zantema: Cinderella versus the Wicked Stepmother https://link.springer.com/chapter/10.1007%2F978-3-642-33475-7_5 The desired value $k$ coincides with $F(80,10)$ in the notation of that paper. By Lemma 1 in the paper $F(80,10)=F(8,1)$, and by Theorem 5 in the paper $F(8,1)=H_7=363/140$.
13.03.2019 16:59
The proofs for $F(80,10)$ and $F(8,1)$ in the paper are very simple. They work for the variant where Cinderella must empty $10$ consecutive buckets with largest total, and they also work for the variant where Cinderella may emoty any $10$ consecutive buckets. The two problems are so similar that the same analysis works for both variants.
14.03.2019 13:35
Clearly we want to find the largest possible amount of water in one of the buckets at any moment. First we reduce the problem from $F(80,10)$ as suggested above to $F(8,1)$.
Now we play the game on $F(8,1)$. For $B$, the optimal strategy is to empty the largest bucket all the time. Call the buckets $1$ to $8$ with amount of water $a_1,a_2,...,a_8$, where each round ends when $A$ has added in the water. We also arrange the buckets in decreasing order, so $a_1\geq a_2\geq...\geq a_8$. The key lemma is that $\sum_{i=1}^{k} a_i < k\cdot(1+\sum_{i=k}^{7}\frac{1}{k})$, after $A$ makes the move. We prove this by downwards induction. For $k=8$ , $\sum_{i=1}^{8} a_i \leq 1 + \sum_{i=2}^{8}a'_i\leq 1+\frac{7}{8}\sum_{i=1}^{8}a'_i$, where $a'_i$ is the amount of water in the buckets in the previous round of play. So if $\sum_{i=1}^{8}a'_i<8$ then $ \sum_{i=1}^{8} a_i < 8$, and so it must be always true since initially $\sum_{i=1}^{8} a_i =1$. If for $k=m$ is true, for $k=m-1$, $\sum_{i=1}^{m-1} a_i \leq 1 + \sum_{i=2}^{m} a'_i \leq 1+\frac{m-1}{m} \sum_{i=1}^{m} a'_i <1+(m-1)(1+\sum_{i=m}^{7}\frac{1}{m})=(m-1)(1+\sum_{i=k}^{7}\frac{1}{k})$. Thus $k=m-1$ is true as well. Thus by induction the statement is true for $k=1$ as well, hence the largest bucket is less than $1+1+\frac{1}{2}+...+\frac{1}{7}$. To show that this is the best attainable bound, $A$'s strategy is to, for each round, first ensure $a_1=a_2=...=a_8$. Thus the amount of water in each bucket be the following sequence: $\frac{1}{8}$, $\frac{1}{8}\Big(1+\frac{7}{8}\Big)$, $\frac{1}{8}\Big(1+\frac{7}{8}+\Big(\frac{7}{8}\Big)^2\Big)..$ and the limit of this sequence is $1$. Thereafter, when the buckets are sufficiently close enough to $1$ as $A$ likes, for the next round $A$ will add $\frac{1}{7}$ to the $7$ largest buckets, then $\frac{1}{6}$ to the $6$ largest buckets,...,and finally $1$ to the largest bucket left. The total amount of water in that bucket can clearly be arbitrarily close to $k=1+1+\frac{1}{2}+...+\frac{1}{7}$.
14.03.2019 20:50
On second thought, the above only works if $B$ can choose any $10$ consecutive buckets. I also don't think the reduction from $H(80,10)$ to $H(8,1)$ is as easy as the result in the paper, in fact it seems to be much more challenging and maybe even untrue?
15.03.2019 21:16
We claim that the answer is all $k < 1 + \frac11 + \frac12 + \cdots + \frac17 = \frac{503}{140}.$ To see that $A$ can indeed attain these numbers, use the same strategy as what $\mathbf{61plus}$ used. Now, we will show that $A$ cannot ever have any bucket with $\geq 1 + \frac11 + \frac12 + \cdots + \frac17.$ Now for some terminology. Let $A$ be Alex and $B$ be Bethany. Let a $\mathbf{block}$ be any group of at most ten consecutive buckets (so a single bucket is a block, as are ten consecutive buckets, etc.). Call two blocks disjoint if they do not share any common buckets. Let $S_i = 1 + \frac{1}{7} + \cdots + \frac{1}{i},$ for $1 \leq i \leq 7,$ and let $S_8 = 1.$ The key lemma is the following: $\mathbf{Lemma.}$ Any $i$ pairwise disjoint blocks must have a sum of strictly less than $iS_i$ in total at any point in time. $\mathbf{Proof.}$ The proof is by downwards induction on $i.$ When $i = 8,$ notice that Bethany always reduces to sum to at most $\frac{7}{8}$ of what it was before Bethany's move, and so hence the sum of all $80$ buckets can never be $\geq 8$ by an easy induction, say. Now, suppose that the result holds for $i=k$, some $k > 1.$ When $i = k-1,$ we will show that any $k-1$ disjoint blocks have sum $<(k-1)S_{k-1}.$ Assume, for contradiction, that some $k-1$ disjoint blocks $B_1, B_2, \cdots, B_{k-1}$ had a sum of at least $(k-1)S_{k-1}.$ Clearly, we can assume WLOG that Alex has just moved, as then he can strictly increase the sum of the numbers of the $B_i$'s. Call this point in time $t = 0.$ Now, let's travel back in time to analyze the situation when we undo Alex's last move. Let this point in time be $t = -1.$ We know that since Bethany moved before this, there must exist 10 consecutive $0$'s somewhere in the circle (the $10$ consecutive numbers that she cleared). Call the block consisting of these $10$ consecutive zeroes $D.$ Notice that the sum of the numbers in $B_1, B_2, \cdots, B_{k-1}$ is now at least $(k-1) S_{k-1} - 1 = (k-1)S_k.$ Now, if any $B_i$ is not disjoint with $D,$ then remove $B_i \cap D$ from $B_i$ to create the new block $C_i$. Otherwise, simply let $C_i = B_i.$ Notice that since $B_i$ has length at most 10, $C_i$ must still be a contiguous block after this operation, and clearly also has at most $10$ buckets within it. Furthermore, since we only removed zeroes, the sum of the numbers in the $C_i$ is the same as the numbers in the $B_i$, which is $\geq (k-1)S_k.$ Hence, we've shown that at time $t = -1,$ there are pairwise disjoint blocks $D, C_1, \cdots, C_{k-1}$ such that $D$ is the block consisting of the $10$ zeroes created by Bethany on her previous move, and the $C_i$'s are all disjoint and sum to at least $(k-1)S_k.$ Now, let us travel even further back in time, and undo Bethany's move before that. We are now in time $t = -2.$ Since she selected the block $D$ with the largest sum, we know that at $t = -2,$ the block $D$ had a sum which was at least as great as all of the $C_i$'s, and in particular it must have a sum which is at least $\frac{C_1 + C_2 + \cdots + C_{k-1}}{k-1} \geq S_k.$ Therefore, we know that at time $t = -2,$ the sum of the pairwise disjoint blocks $D, C_1, C_2, \cdots, C_{k-1}$ is at least $S_k + (k-1)S_k = kS_k,$ which clearly is a contradiction to our induction hypothesis. As we've derived a contradiction, we know that the sum of any $k-1$ disjoint blocks is always $<(k-1)S_{k-1}$ at any point in time, and so the induction is complete. $\blacksquare$ The problem now follows by taking $i=1$ in the lemma above, and noting that a single bucket is a block. $\square$ Note: Used the word "bucket" in multiple places, oops
18.03.2019 08:32
Quote: $B$ can restrict himself to only emptying buckets $10k+1,10k+2,...,10k+9$, where buckets are taken mod $80$. This is obviously false hypothesis, as $B$ could only select the $10$ consecutive buckets with the largest sum, possibly the $4th-13th$ buskets, which disables him from executing such strategy.
23.02.2020 14:38
Pathological wrote: We claim that the answer is all $k < 1 + \frac11 + \frac12 + \cdots + \frac17 = \frac{503}{140}.$ To see that $A$ can indeed attain these numbers, use the same strategy as what $\mathbf{61plus}$ used. Now, we will show that $A$ cannot ever have any bucket with $\geq 1 + \frac11 + \frac12 + \cdots + \frac17.$ Now for some terminology. Let $A$ be Alex and $B$ be Bethany. Let a $\mathbf{block}$ be any group of at most ten consecutive buckets (so a single bucket is a block, as are ten consecutive buckets, etc.). Call two blocks disjoint if they do not share any common buckets. Let $S_i = 1 + \frac{1}{7} + \cdots + \frac{1}{i},$ for $1 \leq i \leq 7,$ and let $S_8 = 1.$ The key lemma is the following: $\mathbf{Lemma.}$ Any $i$ pairwise disjoint blocks must have a sum of strictly less than $iS_i$ in total at any point in time. $\mathbf{Proof.}$ The proof is by downwards induction on $i.$ When $i = 8,$ notice that Bethany always reduces to sum to at most $\frac{7}{8}$ of what it was before Bethany's move, and so hence the sum of all $80$ buckets can never be $\geq 8$ by an easy induction, say. Now, suppose that the result holds for $i=k$, some $k > 1.$ When $i = k-1,$ we will show that any $k-1$ disjoint blocks have sum $<(k-1)S_{k-1}.$ Assume, for contradiction, that some $k-1$ disjoint blocks $B_1, B_2, \cdots, B_{k-1}$ had a sum of at least $(k-1)S_{k-1}.$ Clearly, we can assume WLOG that Alex has just moved, as then he can strictly increase the sum of the numbers of the $B_i$'s. Call this point in time $t = 0.$ Now, let's travel back in time to analyze the situation when we undo Alex's last move. Let this point in time be $t = -1.$ We know that since Bethany moved before this, there must exist 10 consecutive $0$'s somewhere in the circle (the $10$ consecutive numbers that she cleared). Call the block consisting of these $10$ consecutive zeroes $D.$ Notice that the sum of the numbers in $B_1, B_2, \cdots, B_{k-1}$ is now at least $(k-1) S_{k-1} - 1 = (k-1)S_k.$ Now, if any $B_i$ is not disjoint with $D,$ then remove $B_i \cap D$ from $B_i$ to create the new block $C_i$. Otherwise, simply let $C_i = B_i.$ Notice that since $B_i$ has length at most 10, $C_i$ must still be a contiguous block after this operation, and clearly also has at most $10$ buckets within it. Furthermore, since we only removed zeroes, the sum of the numbers in the $C_i$ is the same as the numbers in the $B_i$, which is $\geq (k-1)S_k.$ Hence, we've shown that at time $t = -1,$ there are pairwise disjoint blocks $D, C_1, \cdots, C_{k-1}$ such that $D$ is the block consisting of the $10$ zeroes created by Bethany on her previous move, and the $C_i$'s are all disjoint and sum to at least $(k-1)S_k.$ Now, let us travel even further back in time, and undo Bethany's move before that. We are now in time $t = -2.$ Since she selected the block $D$ with the largest sum, we know that at $t = -2,$ the block $D$ had a sum which was at least as great as all of the $C_i$'s, and in particular it must have a sum which is at least $\frac{C_1 + C_2 + \cdots + C_{k-1}}{k-1} \geq S_k.$ Therefore, we know that at time $t = -2,$ the sum of the pairwise disjoint blocks $D, C_1, C_2, \cdots, C_{k-1}$ is at least $S_k + (k-1)S_k = kS_k,$ which clearly is a contradiction to our induction hypothesis. As we've derived a contradiction, we know that the sum of any $k-1$ disjoint blocks is always $<(k-1)S_{k-1}$ at any point in time, and so the induction is complete. $\blacksquare$ The problem now follows by taking $i=1$ in the lemma above, and noting that a single bucket is a block. $\square$ Note: Used the word "bucket" in multiple places, oops Superb solution! However I can't understand your motivation. I mean, how did you come to your claim?
09.05.2020 14:52
I didn't read any of your prooves but you are all wrong because I managed to get any k<8. This is how it works. We are working only with the 10th 20th...80th buckets. First we put 1/8 liter in each bucket. Then one of the buckets will be emptied, call this bucket the buffer, and name the other backets 1,2,3,...,7 in any order you like. Now we work this way: if all buckets (except the buffer) has the same amount of water in them call this number t. If 7t+1≥k (where k is the desired amount of water) add 1 liter to the buffer and you are done. Else you add (t+1)/2 liters to the buffer and (1-t)/2 liters to bucket 1. It is easy to see that the amount of water in the buffer and in bucket 1 is now the same so player B will empty one of these two and WLOG he will empty the buffer. Next you do the same for bucket 2, add (1+t)/2 to the buffer and (1-t)/2 to bucket 2 and the heaviest buckets are the buffer and buckets 1,2 so WLOG player B empties tbe buffer. The process continues until bucket 7 and we have buckets 1 to 7 with (1+t)/2 liters each. In every step the difference 1-t is cutten by half so eventually we will get all buckets with as close to 1 as we want to liters of water. We have 7t liters after every step so we get as close to 7 as desired and by adding 1 to the buffer whenever we wish we can get as close to 8 as desired. I am yet to prove that 8 is the superior but it is probably not the difficult part of the question