Elmo has 2023 cookie jars, all initially empty. Every day, he chooses two distinct jars and places a cookie in each. Every night, Cookie Monster finds a jar with the most cookies and eats all of them. If this process continues indefinitely, what is the maximum possible number of cookies that the Cookie Monster could eat in one night? Proposed by Espen Slettnes
Problem
Source: ELMO Shortlist 2023 C1
Tags: Elmo, combinatorics
29.06.2023 08:07
I'm pretty sure the answer is $12$... I've thought about defining the function \[ \begin{cases} f(n) = 0 & \text{ if } n = 0 \\ f(n) = 2^{n-1} & \text{ if } n > 0. \end{cases} \]and considering the value $f(\text{\# cookies})$ summed over each of the $2023$ jars - this is almost a monovariant, but it can increase when Elmo puts two cookies in both empty jars. There's probably some messy argument that patches this - is this the intended solution?
29.06.2023 19:53
Answer: $\lceil \log_2n \rceil +1$ in the general case, here the value is $12$. Define $f(n)=2^n$ if $n\neq 0, f(0)=0$ , suppose that at a moment the jars contain $a_1,..,a_{2023}$ cookies Let $d=\max a_i$ and set $L=\sum f(a_i)$, I'll show that whenever $d\geq 2$ the the next value of $L$ (after both players play) is at most $L$. First, suppose that ELMO putt cookies into two non-empy jars, say $i,j$. If $a_i=a_j=d$ then the cookie Monster is going to eat all the cookies of some of the $i,j$ jars. Hence $L'=L+2^{d+1}-2^d-2^d=L$. If $a_i=d, a_j<d$ then $L'=L+2^{a_j+1}-2^{a_j}-2^{d+1}<L$ . If $a_i,a_j<d$ then $L=L+2^{a_i+1}+2^{a_j+1}-2^n-2^{a_i}-2^{a_j}\leq L $ Now assume that the jar $i$ was empty but $j$ not, if $a_j=d$ then $L'=L-2^{d+1}+2<L$ If $a_j<d$ then again $L'=L+2^{a_j+1}-2^{a_j}-2^d+2\leq L$. Now suppose that both jars $i,j$ were empty, then $L'=L+2+2-2^d\leq L $ since $d\geq 2$. Claim : $L<2^{12}$ every morning (before ELMO plays and after monster's turn) Proof: Suppose that at some moment, for first time we have $L<2^{12}, L'\geq 2^{12}$, since $L'>L$ we have $d=1$ so $L\leq 2^1+2^1+...+2^1=2\cdot 2023=4046$ and thus $L'\leq L+2<2^{12}$ a contradiction $\blacksquare$ Since $L<2^12$ we have that $a_i\leq 11$ every morning, and so $a_i\geq 12$ at each time and so Cookie Monster can eat at most $12$ cookies on a single night. The construction is the following for $n=5$ (it can be easily extended to each positive integer) $ (0,0,0,0,0) \to (1,1,0,0,0)\to (0,1,0,0,0)\to (0,1,1,1,0)\to(0,0,1,1,0)\to (1,1,1,1,0) \to $ $(1,1,1,0,0)\to (1,1,1,1,1)\to (1,1,1,1,0)\to (2,2,1,1,0)\to (0,2,1,1,0)\to (0,2,2,2,0)\to(0,0,2,2,0)\to $ $\to (0,0,0,3,3)\to (0,0,0,0,3)\to (0,0,0,1,4)\to (0,0,0,1,0)$ where at the last step cookie monster eats $4$ cookies.
01.07.2023 13:45
Answer : $12$ let the number of the cookies in the $i$-th jar be $f(i)$ in every turn . let S = $ \sum_{k=1}^{2023} 2^{f(k)}$ . it ' s easy too see that $S$ non-descending after the both Elmo's and Cookie monster's turn . at first $S = 2023$ . so if coockie monster eat $13$ cookies in a turn , in the previous turn there is a jar with at least $12$ cookies .contradition because $2^{12} > 2023$ . so he can eat at most $12$ cookies. and it's east to show that $12$ works.
19.09.2024 09:24
The answer is $\lfloor \log_2 2023 \rfloor+2=12$. To achieve $12$, let Elmo initially put cookies into empty jars until there are $1024$ jars with exactly one cookie after Cookie Monster's turn. For $i=1,2,\ldots,10$, let Elmo divide the $2^{11-i}$ jars with $i$ cookies into pairs and put two cookies into the two jars of each pair over $2^{11-(i+1)}$ days. Cookie Monster will eat $2^{11-(i+1)}$ of these jars with $i+1$ cookies, leaving $2^{11-(i+1)}$ jars with $i+1$ cookies. At the end of this process, there will be one jar with $11$ cookies. Elmo can put a cookie into this jar, leaving $12$ cookies for Cookie Monster to eat. Now, we show that Cookie Monster cannot eat more than $12$ cookies in one night. Suppose a day is during crunch time if there exists a jar with more than one cookie after Elmo's turn. For an integer $n$, let $f(n)$ be the number of jars with $n$ cookies, and let the weight of a configuration of jars be \[\sum_{k=1}^\infty 2^kf(k).\] Claim: During crunch time, the weight cannot increase. Proof: Suppose Elmo puts cookies into jars that already had $i$ and $j$ cookies, with $i \ge j$. Since the maximum number of cookies in a jar after Elmo's turn is at least $i+1$, the weight changes by at most \[2^{i+1}-2^i+2^{j+1}-2^j-2^{i+1}=2^j-2^i \le 0,\]as desired. $\square$ Assume FTSOC that Cookie Monster can eat more than $12$ cookies in one night, and consider the first day in the series of days of crunch time leading up to Cookie Monster's considerable consumption. Before Elmo's turn, the weight is at most $2 \cdot 2023=4046$, so the weight must be at most $4046$ during all of crunch time. Hence, there cannot be a jar with more than $\lfloor \log_2 4046 \rfloor=11$ cookies before Elmo's turn. This means no jar has more than $12$ cookies when the Cookie Monster arrives, a contradiction. $\blacksquare$