If $k$ is too large, Alice could color the $k$ largest numbers in the set and there's no way for Bob to replicate the sum even if he chooses all of the remaining numbers. So this is the first constraint. The sum of largest $k$ numbers is (letting $n=2023$) $kn - k(k-1)/2$ The sum of the first $n-k$ numbers is $(n-k)(n-k+1) /2$ Putting the constraint together, we must have: $$k^2 - (2n+1)k + \frac{n(n+1)}{2} \geq 0$$Letting $n=2023$ we have: $$k < \frac{4047 - \sqrt{2023^2 + 2024^2}}{2}$$Calculated with calculator, this means $k <= 592$ although I'm not sure how I would have gotten this number in a competition. Now we have to show that for this $k$, Bob can actually replicate any sum that Alice chooses. I have not done this part.

Let $n=2023$ and $t=k_{\max}$ be the required maximum. The direct part is to feel that if Ana chooses $t$ highest numbers, meaning $(n-t)+1, (n-t)+2, \dots, (n-t)+t$, their sum should be less than half of the sum of all numbers, which is $\dfrac{n(n+1)}{4}$. Otherwise Bogdan, anyhow he chooses his numbers, the sum of his numbers will be less than Ana's numbers sum. Then, $t(n-t)+\dfrac{t(t+1)}{2} \leqslant \dfrac{n(n+1)}{4}$ (0), or $t^{2}-t(2n+1)+\dfrac{n(n+1)}{2} \geqslant 0$ (1). The solutions of equation (1) are $t_{1,2} = \dfrac{(2n+1)\pm \sqrt{n^{2}+(n+1)^{2}}}{2}$, so if $t_{1}<t_{2}$, then $t_{2}>n$. From (1) we get that $t\leqslant t_{1}$ or $t\geqslant t_{2}>n$. As $t\leqslant n$, we imply that $t \leqslant t_{1}$, and as $t$ is an integer, we get $t\leqslant \left[\dfrac{(2n+1)-\sqrt{n^{2}+(n+1)^{2}}}{2} \right]=t_{0}$. We show that $t_{0}$ is the required maximum. Observe that $(n/4< t_0 <n/3)$. Assume that Ana chooses $t_0$ numbers with the sum $s$. Bogdan has to find some remaining numbers with sum $s$, or with sum $\dfrac{n(n+1)}{2}-2s$ (if we exclude these and Ana's numbers, we have some numbers left with sum $s$). Bogdan can search for numbers left with sum less than the minimum, which is $s_{0} = \min\left\{s,\dfrac{n(n+1)}{2}-2s\right\} \leqslant \dfrac{n(n+1)}{6}$ (2). Bogdan's strategy can be the following: he writes $s_{0} = a(n+1)+b$, where $0\leqslant b \leqslant n$ (3). If $a\geqslant 1$ and Bogdan searches in the remaining numbers two with sum $b$ or $n+1+b$ and colors them in blue (step 1), then he searches among remaining numbers $a$ (or $a-1$) number pairs with sum $n+1$ and colors them in blue (step 2). Let's show this is possible. The following pairs exist: $(1,b-1),(2,b-2),\dots,(\left[\dfrac{b}{2}\right],b-\left[\dfrac{b}{2}\right])$ and the sum of their components is $b$, and they are (counted as) $\left[\dfrac{b}{2}\right]$; the pairs $(n,b+1),(n-1,b+2),\dots(\left[\dfrac{n+b+1}{2}\right],n+b+1-\left[\dfrac{n+b+1}{2}\right])$ all have the sum of their components $n+b+1$ and they are $n+1-\left[\dfrac{n+b+1}{2}\right]$. These pairs are in total $n+1-\left[\dfrac{n+b+1}{2}\right]+\left[\dfrac{b}{2}\right] > n+ \dfrac{b}{2}-\dfrac{n+b+1}{2}=\dfrac{n-1}{2}$. Among these we eventualy ignore 2 (last ones) which can have equal components. As Ana chose $t_{0}<\dfrac{n-1}{2}$ numbers, one of these pairs will have no colored numbers. So, Bogdan can perform step 1. Further, at most $m=t_{0}+2$ numbers would be colored. Further, the pairs $(1,n),(2,n-1),\dots,(\left[\dfrac{n}{2}\right], n-\left[\dfrac{n}{2}\right]+1)$ which all have the sum of the components $n+1$, are (as counter) $\left[\dfrac{n}{2}\right]$. Amongst these, at least $\left[\dfrac{n}{2}\right]-m$ have all components uncolored. We show futher that $\left[\dfrac{n}{2}\right]-m \geqslant a$, assuring Bogdan he can perform step 2. From (2) and (3) we have $a \leqslant \dfrac{n}{6}$. We show that $\left[\dfrac{n}{2}\right]-m \geqslant \dfrac{n}{6}$, or $\left[\dfrac{n}{2}\right]-\dfrac{n}{6}-2 \geqslant t_{0}$. Therefore, we need to show that $\dfrac{(2n+1)-\sqrt{n^{2}+(n+1)^{2}}}{2} \leqslant \left[\dfrac{n}{2}\right]-\dfrac{n}{6}-2$, which is implyed by $\left[\dfrac{n}{2}\right] \geqslant \dfrac{n-1}{2}$ and $n\geqslant 100$. If $a=0$, then $s_{0}\leqslant n$. As $s_{0} = \min\left\{s,\dfrac{n(n+1)}{2}-2s\right\}$, we cannot have $s_{0}=s$, as anyhow Ana chooses $t_{0} > \dfrac{n}{4}$ numbers, their sum is greater than $1+2+\dots+\left[\dfrac{n}{4} \right] > n$. Then, $s_{0}=\dfrac{n(n+1)}{2}-2s \leqslant n$ and $s= \dfrac{n(n+1)}{4}-\dfrac{s_0}{2}$ (4). Let $x$ be the smallest number colored by Ana. Then $s \leqslant x + t_0(n-t_0)+\dfrac{t_0(t_0+1)}{2} - [(n-t_0)+1] \leqslant x+\dfrac{n(n+1)}{4} - [(n-t_0)+1]$, where for the last step we used (1). Combined with (4), we have $x+\dfrac{s_0}{2} \geqslant n-t_0+1 > \dfrac{2n}{3}$, and as $\dfrac{s_0}{2} \leqslant \dfrac{n}{2}$, we get $x>\dfrac{2n}{3}-\dfrac{n}{2}=\dfrac{n}{6}$. Then, Bogdan can color any of the numbers $1,2,\dots,\left[\dfrac{n}{6} \right] $, so he can achieve any sum from $1$ to $\dfrac{1}{2} \left[\dfrac{n}{6} \right]\left(\left[\dfrac{n}{6} \right]+1\right)$. Since $\dfrac{1}{2} \left[\dfrac{n}{6} \right]\left(\left[\dfrac{n}{6} \right]+1\right) > \dfrac{n(n-6)}{72}>n\geqslant s_{0}$, Bogdan can achieve his goal. Note that if $s_0=0$, Bogdan colors no number.

Someone please post a local solution.

Too easy for Q4, solved in 15 minutes.

Attachments:
BaMO23_UNK2_Q4.pdf (106kb)

MPrime wrote: Too easy for Q4, solved in 15 minutes. It's a shame Q3 wasn't so trivial, I guess.

This BMO was so messed up. P4 that was solved only by one contestant and P1 was solved by more than 100 contestants, not good selection of problems

cretanman wrote: Find the greatest integer $k\leqslant 2023$ for which the following holds: whenever Alice colours exactly $k{}$ numbers of the set $\{1,2,\dots, 2023\}$ in red, Bob can colour some of the remaining uncoloured numbers in blue, such that the sum of the red numbers is the same as the sum of the blue numbers. This problem was proposed by Cristi Săvescu. I'm so happy to see that we finally have a Romanian problem in a major contest! Congratulations to the proposer! I found a really interesting solution (only half of it during the contest, oops). I will provide the motivation and the main claim. I might post it fully later. Of course, it can easily be noticed that if $k{}$ satisfies the given condition, then \[2023+2022+\cdots+2023-(k-1)\leqslant\frac{1+2+\cdots+2023}{2},\]as otherwise Alice can colour the $k{}$ largest numbers and Bob cannot do anything. Indeed, the largest $k{}$ which satisfies this condition is the answer. In what follows, all $k{}$-tuples are followed from smallest to largest. We define a lexicographical order on the $k{}$-tuples by comparing the entries from right to left. For instance, we have $(1,3,4)> (2,2,4)$. Here's the main claim: Claim. Suppose that Bob has a colouring for some $k{}$-tuple $(a_1,a_2,\ldots,a_k)$ chose by Alice. Then, unless this $k{}$-tuple corresponds with that of the $k{}$ largest numbers, there exists another $k{}$-tuple $(b_1,b_2,\ldots,b_k)$ for which Bob has a colouring, which satisfies \[(b_1,b_2,\ldots,b_k)>(a_1,a_2,\ldots,a_k).\]What this claim essentially states is that if Bob has a colouring for a given $k{}$-tuple, then he also has a colouring for a $k{}$-tuple which has a greater lexicographical order, until we reach the "maximal" one, which is the $k{}$-tuple of the $k{}$ largest numbers. Hence, through several transformations (which are to be defined in the proof of the claim), we derive a colouring for the "maximal" $k{}$-tuple starting from any other $k{}$-tuple. Reversing all these transformations, we may start from a colouring of the "maximal" $k{}$-tuple (which we know exists, by the bound discussed above) and we thus get a colouring for any other $k{}$-tuple.

oVlad wrote: cretanman wrote: Find the greatest integer $k\leqslant 2023$ for which the following holds: whenever Alice colours exactly $k{}$ numbers of the set $\{1,2,\dots, 2023\}$ in red, Bob can colour some of the remaining uncoloured numbers in blue, such that the sum of the red numbers is the same as the sum of the blue numbers. This problem was proposed by Cristi Săvescu. I'm so happy to see that we finally have a Romanian problem in a major contest! Congratulations to the proposer! I found a really interesting solution (only half of it during the contest, oops). I will provide the motivation and the main claim. I might post it fully later. Of course, it can easily be noticed that if $k{}$ satisfies the given condition, then \[2023+2022+\cdots+2023-(k-1)\leqslant\frac{1+2+\cdots+2023}{2},\]as otherwise Alice can colour the $k{}$ largest numbers and Bob cannot do anything. Indeed, the largest $k{}$ which satisfies this condition is the answer. In what follows, all $k{}$-tuples are followed from smallest to largest. We define a lexicographical order on the $k{}$-tuples by comparing the entries from right to left. For instance, we have $(1,3,4)> (2,2,4)$. Here's the main claim: Claim. Suppose that Bob has a colouring for some $k{}$-tuple $(a_1,a_2,\ldots,a_k)$ chose by Alice. Then, unless this $k{}$-tuple corresponds with that of the $k{}$ largest numbers, there exists another $k{}$-tuple $(b_1,b_2,\ldots,b_k)$ for which Bob has a colouring, which satisfies \[(b_1,b_2,\ldots,b_k)>(a_1,a_2,\ldots,a_k).\]What this claim essentially states is that if Bob has a colouring for a given $k{}$-tuple, then he also has a colouring for a $k{}$-tuple which has a greater lexicographical order, until we reach the "maximal" one, which is the $k{}$-tuple of the $k{}$ largest numbers. Hence, through several transformations (which are to be defined in the proof of the claim), we derive a colouring for the "maximal" $k{}$-tuple starting from any other $k{}$-tuple. Reversing all these transformations, we may start from a colouring of the "maximal" $k{}$-tuple (which we know exists, by the bound discussed above) and we thus get a colouring for any other $k{}$-tuple. Can you please post the proof of the claim? Me and my teammate spent a lot of time on contest trying to prove it, and got nowhere, no partials either. It seems like it's hard to control what's available unless you use a global pairing argument.

oVlad wrote: This problem was proposed by Cristi Săvescu. I'm so happy to see that we finally have a Romanian problem in a major contest! Congratulations to the proposer! Thank you Vlad and congrats for the gold medal !

gvole wrote: Can you please post the proof of the claim? I believe the proof can only be understood by reading the handwritten solution, so he cannot post it here.

Different approach. It needs additional work and calculations, but I hope it could be carried out. So, you have a set $X$ of $1431$ integers in the interval $[1,2023]$. For any subset $A\subset X$ denote $S_A:=\sum_{a\in A}a.$ The main idea is to show that as $A$ runs through all subsets of $X,$ $S_A$ covers all integers in $[L,S_X-L]$ for some not too large integer $L.$ For example $L:=14000$ will do the job, but it can be optimized a lot! In some sense, this is a stronger claim. This claim almost solves the original problem, so let us sketch the proof. Since $S_{X\setminus A}$ = $S_X$-$S_A,$ it is enough to prove $S_A$ can cover the interval $[L,S_X/2].$ Consider the set $X'\subset X$ that consists of the last $715$ largest numbers in $X.$ Apparently, $S_{X'}\ge S_X/2.$ Let $X'':=X\setminus X'.$ Since $|X'|= 715, $ it follows $X''\subset [1..1310].$ (we can optimize the sets $X''$ and $X'$ here, $715$ is a very rough estimate). 1) For each $k\in [1200, 1403],$ there exists $A\subset X'', |A|=2$ with $S_{A''}=k.$ Indeed, assume the opposite and consider the the appropriate pairs $(k-i,i).$ If both numbers in a pair belong to $X''$ we are done. But it's impossible all of these pairs to have at most one number in $X''$ since the density of $X''$ prevents it. 2) For any $k_i \in [1200, 1403],i=1,2,\dots 10$ there exist distinct $x_i,y_i\in X'',i=1,\dots,10$ such that $x_i+y_i=k_i.$ We can prove it using 1) subsequently for $i=1,2,\dots,10$ and removing the pair $x_i,y_i.$ 3) Thus, when the set $A\subset X'', |A|=20$ varies, $S_A$ covers all integers in $[10\cdot 1400, 10\cdot 1400 + 2030].$ Then, for any fixed $A'\subset X'$ the value $S_{A'}+S_{A}$ as $A\subset X''$ varies will contain interval with length $2030$ and since each offset $x\in X'$ is less than $2030$ it means we can cover the interval $[L,S_X/2]$ where $L=14000.$ It remains some small cases. In case $S_X-14000\ge 2023\cdot 1012 -S_X$ we are done. Consider now the case $2S_X<2023\cdot 1012+14000$. In this case $X$ slightly differs from the first $1431$ natural numbers, so it can be checked directly?