Ann and Beto play with a two pan balance scale. They have $2023$ dumbbells labeled with their weights, which are the numbers $1, 2, \dots, 2023$, with none of them repeating themselves. Each player, in turn, chooses a dumbbell that was not yet placed on the balance scale and places it on the pan with the least weight at the moment. If the scale is balanced, the player places it on any pan. Ana starts the game, and they continue in this way alternately until all the dumbbells are placed. Ana wins if at the end the scale is balanced, otherwise Beto win. Determine which of the players has a winning strategy and describe the strategy.
Problem
Source: IberoAmerican 2023, Day 1, P3
Tags: combinatorics
14.09.2023 18:01
I was a bit disappointed with this problem, since its solution is completely local, but I will try to write my solution later. For those who haven't tried and are struggling, try looking at the last 4 moves.
14.09.2023 20:37
Yep, it was only the last 4 moves F I got the solution with the hints about minimum and last moves... though idk the motivation about thinking in the minimum, I just feel it like try random things and encounter with this promising approach Well, here's a solution (I think there was another path to solve this problem). First of all, a certain intuition leads to simply playing random and looking for the history of the movements made and maybe we can travel back in time and rearrange some moves to change the final winner. Trying small cases like instead of considering 2023, consider just 7 dumbbells may lead to thinking Beto wins (also some may say it would feel very weird if Ana has a winning strategy since it would seem very restrictive). With that in mind, we are almost ready... the trick as I said (hints to me F) was to instead of let Beto play random, let's just say that Beto always takes the lightest possible dumbbell. With that in mind let's make a trivial observation (this doesn't even need this strategy). Obs: If the scale is balanced and there are only one or two moves left... Beto wins Proof: Basically if it's the last move, then if Ana wins, the last dumbbell needs to be zero weight... absurd! If it's the last two moves, then if Ana wins, the last two dumbbells need to be of equal weight... absurd! Now let's trace back the history! We'll initially just take our basic strategy of Beto always choosing minimums, then we'll suppose that this didn't work (I mean there are already 2023 moves made and Beto was not the winner) and due to this, we can assume our observation never happens. So let's stick for now with the last two moves. WLOG $L > R$ and let's say our last two dumbbells are $b > c$. It's Beto's turn, so Beto can put $c$ in the right-hand side. If this changes the scale to $<$ then Ana will put $b$ to the left-hand side and it's over because our final state will be $L + b > R + c$. Other case is if the scale doesn't change, then Ana will put $b$ to the right-hand side and now we need to guarantee that $L = R+b+c$ never happens. Now remember that since all of our 1010 first Beto's movements were minimums, we have $b > c \geq 1011$ so $b + c \geq 2023$. And here comes another observation, we can prove that the differences between left and right sides are always at most 2023. This is done by induction or whatever, let's say our current state is WLOG $x \geq y$ and we assume $x - y \leq 2023$. If $x = y$ then our next move will be adding some number $\leq 2023$ so our difference is $\leq 2023$. If $x > y$ then our next move will be $x \,?\, y+z$ for some $1 \leq z \leq 2023$. If $x >= y+z$ then our difference is $\leq 2023-z < 2023$. On the contrary, if $x < y+z$ then the differnce is $\leq z-1 < 2023$ and that's it! And we even have something stronger, if the difference is exactly 2023, then our previous state was a balanced scale and our next move had weight of 2023. Also remember to check our base case, initially the scale is 0 on both sides so we're done with the induction. So now we can say that, if Ana wins... the last two dumbbells should be of weights 1011 and 1012. And since Ana wins, our state in that point was of something like $s + 2023 > s$ which means if we trace back one previous move (which in total means looking for the last 3 moves), we know our state was $s = s$ in the scale and Ana chose a weight of 2023. At this point (3 previous moves) we cannot do nothing else, so let's trace it back to the four moves! Let's say our previous state was WLOG $s > s-d$. We are left with our 4 dumbbells $d, 2023, 1011, 1012$ and it's Beto's turn and also we already know that $d \leq 1010$. Now, we are still assuming that Ana wins no matter what... so the only possibilities to make a balanced scale in the end are just two ways: Put just 2023 on the left and everything else in the right OR Put just 1011, 1012 on the left and everything else in the right (these two ways are just hand-checked sums to make equal scales) And now we can safely choose Beto's strategy up to this point, let Beto choose 2023 to the right. Now our state is $s < s-d+2023$ and is Ana's turn and the trick here is that no matter what, the next state will also be $<$. The reason is that if this doesn't happen, then Ana somehow got some available dumbbell in the left of weight $>= 2023-d >= 1013 > max(1011, 1012, d)$ which is absurd! So after this, we have something like $s + w < s - d + 2023$ and we're left with two dumbbells from the set $d, 1011, 1012$ and it's Beto's turn. But remember that since we already have weight of 2023 on the right, if Ana wins then the only weight added to the right should be $d$. Which means that $w \neq d$ and now Beto can put $d$ on the left. Now we're on a state where none of the two unique ways happen, so the scale at the end is never balanced. We're done! (basically we changed the past for Beto in order to change our final veredict) If there are any flaws, pls lemme know.