Author: | Ihor Barenblat, Vladyslav Zavodnyk |
Prepared by: | Konstantinos Anemozalis |
Solved by: | |
First to solve: | Sigma-=-1 |
First, we observe two sufficient conditions for Bob to win from a given state:
If there is any pile with a_i = 1, Bob can simply save this pile for the end. Ana must eventually remove stones from other piles or run out of moves, leaving Bob to remove the 1.
If there are two or more piles with a_i = 2, Bob wins. Ana is forced to clear one of them (2 \to 0), then Bob removes 1 stone from the other (2 \to 1), creating a pile of 1 (reverting to the previous winning case).
Thus, for Ana to have any chance of winning, the initial array must contain no s and at most one .
Now let’s consider the cases for each :
Case k = 2 In this variation, every pair of moves reduces the total stone sum by .
If there exists a pile with a_i \equiv 1 \pmod 3, Bob wins. If Ana touches it, Bob can also move on it to maintain the invariant; eventually, the pile will be reduced to 1 stone.
If there are two piles with a_i \equiv 2 \pmod 3, Bob wins. He can reduce one of them to 1 \pmod 3 on his turn, forcing the previous condition.
Ana wins if and only if she can make the last move. This requires the initial total sum S \equiv 2 \pmod 3, and the configuration must not allow Bob to force a win. Therefore, Ana wins if and only if there is exactly one pile with a_i \equiv 2 \pmod 3 and all other piles satisfy a_i \equiv 0 \pmod 3.
Case k = 3 We classify the pile sizes based on their strategic advantage:
3: If Ana sees a 3, she removes it (3 \to 0), effectively passing the turn while removing a pile. If Bob sees a 3, he plays 3 \to 2, forcing Ana to respond with 2 \to 0. The pile is removed, and it remains Bob’s turn (neutral for Bob).
4: Neutral, similar to 0. Ana cannot touch a 4 (leaves 1 or 2, leading to a loss), so she must wait for Bob to reduce it to 3, then she clears it.
5: Acts as a 1 move advantage to the player who uses it: If Ana uses it: (\text{A}: 5 - 2 = 3) \to (\text{B}: 3 - 1 = 2) \to (\text{A}: 2 - 2 = 0) \to \text{Bob's turn.}
If Bob uses it: (\text{B}: 5 - 1 = 4) \to 4 \text{ (neutral)} \to \text{Ana's turn.}
Note that two 5s are neutral as they cancel each other out.
6: Advantage for Ana. She plays 6 \to 3, creating a pile of 3.
: Winning for Ana. She can always manipulate these large piles to gain a move advantage.
Subcase 1: No pile of 2 stones Ana moves first. She wins if she can claim an advantage, i.e., if any of the following are true:
There is at least one pile of 3.
The count of piles with 5 stones is odd.
There is any number (she converts 6 \to 3 or 7 \to 4, etc.).
Otherwise, the board is neutral (i.e., only 4s and an even number of 5s), and Bob wins.
Subcase 2: Exactly one pile of 2 stones Ana is forced to play 2 \to 0 immediately to prevent Bob from creating a 1. It is now Bob’s turn to move on the remaining piles. Any existing 3s are neutralized by Bob, so they provide no advantage to Ana. Bob wins if and only if he has a strict advantage in the remaining configuration:
The count of piles with 5 stones is odd (giving Bob the parity advantage).
AND there is at most one pile of 6 stones (if there are two 6s, Ana can use one to regain the advantage).
AND there are no piles .
Case k \ge 4 If the initial Bob winning conditions (a pile of 1 or piles of 2) are not met, Ana wins. Since k \ge 4, Ana has enough freedom to choose such that she maintains the invariant that all a_i \ge 3 after her turn, or she can simply mimic the winning strategies from k=3 with even more flexibility.