AoPS - Problem

62861

21.07.2021 00:07

In my opinion, this is one of the best olympiad combinatorics problems to ever be published, and a serious contender for my favorite olympiad problem of all time. Please give it a try. (It goes without saying, but I only have massive praise for the author(s).)

The answer is $7$. In general, with $2020$ replaced by an even $n$, the answer is $s_2(n)$, the sum of the binary bits of $n$. A's strategy (This part works for arbitrary $n$, and this generality will be required in this part.) Before anything else, observe that zeroes can simply be ignored; they simply add one to the final cookie count. Claim. Given $n$ ones on the board, A can get at least $s_2(n)$ cookies. Proof. First, we describe A's strategy. Choose $m \stackrel{\text{def}}{=} \lfloor\tfrac n2\rfloor$ pairs of ones. After this, the board will have $m$ $0$s or $2$s, along with an extra $1$ if $n$ is odd. Then, A will apply this algorithm again, but to the $2$s, then again to the $4$s, and so on. She stops when she has at most one of the next power of two. A only chooses pairs of equal numbers, so the only numbers on the board are powers of two. The algorithm ensures all the powers of two are different, so the game also ends at this stage (it cannot end earlier since there are two equal powers of two). Now, we prove this attains at least $s_2(n)$ cookies. We prove it by induction, with base cases clear. Suppose B creates $k$ $2$s, $m-k$ $0$s, and $t$ $1$s (so $t = n\%2$). By the inductive hypothesis, A can get at least $s_2(k) + (m-k) + t$ cookies. Thus she can guarantee at least \[ \min_{0 \le k \le m} [s_2(k) + (m-k) + t] \ge s_2(m) + t = s_2(n) \]cookies, as desired. $\square$ Remark. The shortlist packet mentions the following direct, simpler argument: each number on the board was produced from a number of ones equal to a power of $2$. So there are at least $s_2(n)$ numbers remaining on the board. B's strategy B keeps track of an important quantity: given the current configuration $(a_1,\ \dots,\ a_k)$, she defines \[ F = |\{\varepsilon_1, \dots, \varepsilon_k \in \{\pm 1\}: \varepsilon_1a_1 + \dots + \varepsilon_na_n = 0\}|. \] Initially, $F = \tbinom{n}{n/2}$ and so $\nu_2(F) = s_2(n)$. Key claim. For any pair of numbers A selects, let $F'$ and $F''$ be the possible values of $F$ after B's move. Then $F = F' + F''$. Proof. Suppose that A chooses $a$ and $b$. Then the four possibilities $\pm a\pm b$ exactly match $\pm(a+b)$ and $\pm|a-b|$, so the claim holds. $\square$ Now we can describe B's strategy: Ensure that $\nu_2(F) \le s_2(n)$ always. (In other words, ensure $2^{s_2(n)+1} \nmid F$.) She can always ensure this: it is initially true, and she can maintain it after A's moves by the key claim. Here's the punchline. The game must end sometime (every round decreases the quantity of numbers by $1$). Suppose there were $k$ numbers at the end of the game. If the game ended due to the first condition, then $F = 0$, which is impossible. Thus the game ended because there were $k$ zeroes. In this case $F = 2^k$, so $k \le s_2(n)$, as wanted! Remark. The shortlist packet mentions that the answer is still $s_2(n)$ for $n$ odd, and mentions that it can be proven similarly as follows. If the board has $k$ numbers $a_1,\ \dots,\ a_k$, define \[ F_i = |\{\varepsilon_1, \dots, \varepsilon_k \in \{\pm 1\}: \varepsilon_1a_1 + \dots + \varepsilon_ka_k > 0 \,\, \text{and}\,\, \varepsilon_i = 1\}|. \]for $i \in \{1, \dots, k\}$. Then, B plays to ensure that at least one $F_i$ is not a multiple of $2^{s_2(n)+1}$ after her move. Remark. The shortlist packet also mentions that a different strategy for B allows her to lose at most $\lfloor \log_2(n+2) \rfloor-1$ cookies, which is optimal if $n$ contains at most two zero bits in binary. Unfortunately, $2020$ doesn't! Remark. (On motivation) A helpful way to think about the game is by interpreting each number $x$ on the board as a superposition $\pm x$: that way, a B move corresponds to adding A's two superpositions in one of two ways. With this mindset, the key quantity $F$ may suggest itself.

TheUltimate123

21.07.2021 02:50

The answer is 7; for general $n$, the answer is $s_2(n)$, the sum of the digits of $n$ in binary. Anastasia's strategy: We will show Ana can guarantee $s_2(n)$ numbers remain for all $n$. To this end, we induct on $n$, letting $f(n)$ denote the answer for $n$. Pair up the 1's (potentially leaving a 1), and ask Banana to combine them. In the end, there are $m$ twos, $\lfloor n/2\rfloor-m$ zeros, and $n\bmod2$ ones. Then Ana focuses on the $m$ twos, repeating her strategy. It can be seen that when the game on the $m$ twos terminates, the original game is also over. Hence the number of terms remaining is \begin{align*} f(n)&\ge(n\bmod2)+\min_m(f(m)+\lfloor n/2\rfloor-m)\\ &\ge(n\bmod2)+\min_m(s_2(m)+\lfloor n/2\rfloor-m)\\ &=(n\bmod2)+s_2(\lfloor n/2\rfloor) =s_2(n). \end{align*} Bananastasia's strategy: Let $n$ be even. In essence, a strategy for Ana is a binary tree of possibilities for Banana, given the current configuration of the board. For each node corresponding to position $a_1$, \ldots, $a_n$, consider the multiset \[S=\{\pm a_1\pm a_2\pm\cdots\pm a_n\}\]of size $2^n$. Claim: [Black magic] For each node of the binary tree with corresponding multiset $S$, if its children have multisets $S_1$ and $S_2$ then $S=S_1\sqcup S_2$. Proof. If Ana's strategy chooses $a$ and $b$, then the four values of $\pm a\pm b$ match the two values of $\pm(a+b)$ and the two values of $\pm(a-b)$. $\blacksquare$ For such a binary tree, by taking the disjoint union of the multisets of all the leaves, you get the original multiset. There are $\binom n{n/2}$ zeroes in the root's multiset. If we consider the leaves that correspond to terminated configurations, the multisets of those in which one number is larger than the sum of the rest have no zeroes, and the multisets (with size $m$) of those in which all numbers are zeroes have $2^m$ zeroes. It follows that \[\binom n{n/2}=\sum2^m,\]implying $\min m\le\nu_2(\binom n{n/2})=s_2(n)$.

USJL

21.07.2021 03:39

CantonMathGuy wrote: In my opinion, this is one of the best olympiad combinatorics problems to ever be published, and a serious contender for my favorite olympiad problem of all time. Please give it a try. (It goes without saying, but I only have massive praise for the author(s).)

The answer is $7$. In general, with $2020$ replaced by an even $n$, the answer is $s_2(n)$, the sum of the binary bits of $n$. A's strategy (This part works for arbitrary $n$, and this generality will be required in this part.) Before anything else, observe that zeroes can simply be ignored; they simply add one to the final cookie count. Claim. Given $n$ ones on the board, A can get at least $s_2(n)$ cookies. Proof. First, we describe A's strategy. Choose $m \stackrel{\text{def}}{=} \lfloor\tfrac n2\rfloor$ pairs of ones. After this, the board will have $m$ $0$s or $2$s, along with an extra $1$ if $n$ is odd. Then, A will apply this algorithm again, but to the $2$s, then again to the $4$s, and so on. She stops when she has at most one of the next power of two. A only chooses pairs of equal numbers, so the only numbers on the board are powers of two. The algorithm ensures all the powers of two are different, so the game also ends at this stage (it cannot end earlier since there are two equal powers of two). Now, we prove this attains at least $s_2(n)$ cookies. We prove it by induction, with base cases clear. Suppose B creates $k$ $2$s, $m-k$ $0$s, and $t$ $1$s (so $t = n\%2$). By the inductive hypothesis, A can get at least $s_2(k) + (m-k) + t$ cookies. Thus she can guarantee at least \[ \min_{0 \le k \le m} [s_2(k) + (m-k) + t] \ge s_2(m) + t = s_2(n) \]cookies, as desired. $\square$ Remark. The shortlist packet mentions the following direct, simpler argument: each number on the board was produced from a number of ones equal to a power of $2$. So there are at least $s_2(n)$ numbers remaining on the board. B's strategy B keeps track of an important quantity: given the current configuration $(a_1,\ \dots,\ a_k)$, she defines \[ F = |\{\varepsilon_1, \dots, \varepsilon_k \in \{\pm 1\}: \varepsilon_1a_1 + \dots + \varepsilon_na_n = 0\}|. \] Initially, $F = \tbinom{n}{n/2}$ and so $\nu_2(F) = s_2(n)$. Key claim. For any pair of numbers A selects, let $F'$ and $F''$ be the possible values of $F$ after B's move. Then $F = F' + F''$. Proof. Suppose that A chooses $a$ and $b$. Then the four possibilities $\pm a\pm b$ exactly match $\pm(a+b)$ and $\pm|a-b|$, so the claim holds. $\square$ Now we can describe B's strategy: Ensure that $\nu_2(F) \le s_2(n)$ always. (In other words, ensure $2^{s_2(n)+1} \nmid F$.) She can always ensure this: it is initially true, and she can maintain it after A's moves by the key claim. Here's the punchline. The game must end sometime (every round decreases the quantity of numbers by $1$). Suppose there were $k$ numbers at the end of the game. If the game ended due to the first condition, then $F = 0$, which is impossible. Thus the game ended because there were $k$ zeroes. In this case $F = 2^k$, so $k \le s_2(n)$, as wanted! Remark. The shortlist packet mentions that the answer is still $s_2(n)$ for $n$ odd, and mentions that it can be proven similarly as follows. If the board has $k$ numbers $a_1,\ \dots,\ a_k$, define \[ F_i = |\{\varepsilon_1, \dots, \varepsilon_k \in \{\pm 1\}: \varepsilon_1a_1 + \dots + \varepsilon_ka_k > 0 \,\, \text{and}\,\, \varepsilon_i = 1\}|. \]for $i \in \{1, \dots, k\}$. Then, B plays to ensure that at least one $F_i$ is not a multiple of $2^{s_2(n)+1}$ after her move. Remark. The shortlist packet also mentions that a different strategy for B allows her to lose at most $\lfloor \log_2(n+2) \rfloor-1$ cookies, which is optimal if $n$ contains at most two zero bits in binary. Unfortunately, $2020$ doesn't! Remark. (On motivation) A helpful way to think about the game is by interpreting each number $x$ on the board as a superposition $\pm x$: that way, a B move corresponds to adding A's two superpositions in one of two ways. With this mindset, the key quantity $F$ may suggest itself.

I thought 2019 C9 was probably the best recent combo, and this problem just completely changed my mind. Sadly didn't solve it though...

naman12

21.07.2021 06:48

I was told to solve this problem by some random person from Canton. Don't know who he is, he just told me (when I asked him what ISL problem I should solve) "c8, though thats probably not the answer you want". Two hours later, after describing my solution to him, he simply vanished after uttering "sounds like the 2020 c8 experience" and "sounds good". If anyone could put me in contact with him, it would be great We claim the answer is 7, i.e. Ana will not make it to the next IMO (yay, no more combo?) In general for some random $n=2020$, we claim the answer is $s(n)$, which is the sum of the digits of $n$ in base 2. To show this for Ana, we go strong in duck. In particular, in duck shun bay's cays is for $n=1$, which is clear. Now, to show the in duck shun state mint holds, we look if $n$ is awed or event. We will provide the clause that Ana only uses paw wars of too and zeroes. If $n=2m$ is event, then we can just gather up pairs of 1s to make twos. This results in $x$ zeroes and $m-x$ twos. However, by the inequality \[s(n)=s(m)\leq s(x)+s(m-x)\leq s(m-x)+x\]we get that Ana gets at least $s(n)$ cookies. If $n=2m+1$ is awed, the exact same idea holds, except we get an extra cookie for Ana, so the inequality holds. Now, Banana will just stare Ana down to force this measly amount of cookies. Consider all possible values of \[\left\vert\sum_{k=1}^n\varepsilon_ka_k\right\vert\]over all possible values of $\varepsilon_k\in\{-1,1\}$. Call this the Cookie Monster set. The Cookie Monster set of Banana choosing $|x-y|$ and $x+y$ have union of the original Cookie Monster set, and clearly this means when the process ends, the size of the Cookie Monster set is what we're interested in. Clearly, game ends by the second rule, but in this case, we get at most as many zeroes as in the original Cookie Monster set - which is $\nu_2\left(\binom n{n/2}\right)$. Thus, we get at most $s_2(n)$ zeroes, and thus Ana will be very hungry.

CANBANKAN

02.01.2022 02:36

Replace $2020$ with $n$. The answer is $s_2(n)$. Strategy for A is simple pairing + recursion. I will discuss how I was able to motivate the strategy for B. Useful motivation is analyzing the case when $n=8$. In this case, you will run into the scenario where you have $3,2,2,1$ on the board. I put $2,2$ in one group and $1,3$ in the other group. Now, if A selects two numbers in the same group, B adds them. If A selects two numbers in two different groups, B subtracts them, putting the new number in the group with the bigger number. In the end, the sum of numbers in one group is equal to the sum of the numbers in the other group. If there are two ways to form groups (well if $A,B$ work then so must $B,A$) then in the end we get one 0. Now the operation can be rephrased as follows: we have $n$ 1's. Every turn, A picks two numbers and B puts them in the same group or two different groups. Based on the previous analysis it's intuitive to consider the number of possible groupings because the two cases are mutually exclusive but the only possibilities (like a junction in a grid path). Furthermore, it is perfect because $\nu_2(\binom{n}{n/2})=s_2(n)$ if $n$ is even. Considering the ending state gives the desired result. For $n$ odd we just put the first number in a fixed group and repeat the same argument.

MarkBcc168

19.07.2022 07:26

Here is another motivation to arrive at the magical strategy for B. After finding the answer, the most interesting case to look at is when $n$ is the power of two, in which case the game must end at a single number. Tracing back, we get the following. The previous turn must have two equal numbers. The previous turn must have three numbers $x,y,z$ such that $x=y+z$. Then, the key observation is that whatever pair A chooses among these three, B can make two equal numbers. This already suggests looking at $\pm a_1 \pm a_2 \pm \dots \pm a_k$. Therefore, I realized that if we replace $n/2$ of the ones with $-1$ and perform only $x,y\to x+y$, then it maintains the condition that you can assign signs so that the sum is zero. Still, we have to control the number of zeroes that occur along the way. This led me to look at all possible ways to assign $n/2$ ones and determine the assignment that works for A's strategy. After some experiments, the final idea of looking at $\nu_2$ arises, owing to the fact that $\tbinom{2n}{n}$ is even. What a magical problem!

Leo.Euler

06.09.2023 20:07

Let $A$ be Ash and $B$ be Bash. The answer is $7$. In general, when $2020$ is replaced with arbitrary $n$, then the answer is $s_2(n)$, the sum of the digits of $n$ in binary. Ash's strategy: We claim that Ash receives at least $s_2(n)$ cookies, which we prove by strong induction on $n$. Ash's strategy is to pair the 1s, resulting in $\lfloor n/2 \rfloor - k$ 2s, $n \bmod{2}$ 1s, and $k$ 0s, where $k<\lfloor n/2 \rfloor$. The inductive step holds because \[ s_2(n) = s_2(\lfloor n/2 \rfloor)+n \bmod{2} \le s_2(k) + s_2(\lfloor n/2 \rfloor - k) + n \bmod{2} \le s_2(\lfloor n/2 \rfloor - k) + n \bmod{2} + k. \] Bash's strategy: We consider the Bashing set of the board, which is the multiset $S=\{ \pm a_1\pm a_2\pm\cdots\pm a_n\}$. For a multiset $X$, denote $f(X)$ by the number of 0s in $X$. Let the set of numbers on the board after $|x-y|$ is appended have Bashing set $S_0$, and let the set of numbers on the board after $x+y$ is appended have Bashing set $S_1$. Draw a binary tree with root $S$, and given a node $A$ its children are $A_0$ and $A_1$, if they exist. The key idea is that $A=A_0 \sqcup A_1$ for each parent node $A$. In particular, this means that $f(A)=f(A_0)+f(A_1)$. Note that $\nu_2(f(S))=\nu_2(\tbinom{n}{\lfloor n/2 \rfloor}) = s_2(n)$. Bash's strategy is to choose a path down the binary tree such that the $f$-value of each node on the path has $\nu_2$ of at most $s_2(n)$. This is always possible since $f(A)=f(A_0)+f(A_1)$ for each parent node $A$. The game must eventually end as $|S|$ decreases by $1$ after each round. Clearly the first condition for the game ending is not possible as $|S| \neq 0$. So the second condition for the game ending holds, and let $S_{\text{final}}$ be the final Bashing set (which consists entirely of 0s); then \[s_2(n) \ge \nu_2(f(S_{\text{final}})) = |S_{\text{final}}|,\]as desired.

math_comb01

15.01.2024 19:38

Short Sketch: The answer is $s_2(n)$ A's strategy: Divide into pairs, make things divisible by powers of $2$ in each step, so you get the desired bound. B's stategy: The set $\mathbb{S}$ of no's, notice the binary tree when breaked into two $S',S"$, then $S$ "reachability" is same as its node, ensure $v_2 \leq 2^{s_2(n)+1}$. (by using previous claim)

mathloverwww

08.05.2024 20:11

does anyone know who is the author?

Randomization

08.05.2024 21:05

math_comb01 wrote: Short Sketch: The answer is $s_2(n)$ A's strategy: Divide into pairs, make things divisible by powers of $2$ in each step, so you get the desired bound. B's stategy: The set $\mathbb{S}$ of no's, notice the binary tree when breaked into two $S',S"$, then $S$ "reachability" is same as its node, ensure $v_2 \leq 2^{s_2(n)+1}$. (by using previous claim)

Hi, you must be a genius to not find it magical at all .... can you share with me the other 2-3 problems.... I would like to try them... thank you!