Alexey and Bogdan play a game with two piles of stones. In the beginning, one of the piles contains $2021$ stones, and the second is empty. In one move, each of the guys has to pick up an even number of stones (more than zero) from an arbitrary pile, then transfer half of the stones taken to another pile, and the other half - to remove from the game. Loses the one who cannot make a move. Who will win this game if both strive to win, and Bogdan begins? (Oleksii Masalitin)
Problem
Source: 2021 Ukraine NMO 9.1 10.1
Tags: combinatorics, game, game strategy
06.04.2021 15:54
Answer :First player will win. Proof: Claim: A player who made piles like N and N-1 , has a winning strategy. "Proof" of the claim: Just do strong induction. Back to the problem . The first player will transfer 674×2 stones to the other pile . And the piles will be this form: (673,674), by the Induction first player wins.
30.04.2021 12:28
Here's a cleaner write-up , denote the players by $A, B$ according to their names and let $(\bullet, \bullet')$ denote the sizes of boxes so that it's $(2021, 0)$ initially. Claim. B has a winning strategy. (for now, assume it's false) Subclaim. The only final position someone can possibly lose at is $(0, 1)$ Proof for the subclaim . Notice the invariance of the difference of the sizes of boxes modulo $3$. $\square$ Proof for the claim. Now, we give a strategy for B, in particular we claim that he can always leave a $(k-1, k)$ position to A starting with $$(2021, 0)\to (673, 674)$$and by playing symmetrically wrt him afterwards. It's easy to check that it can always be done as long as A can make a move . $\square$ So, since $(2, 0)\to_{A} (0, 1)$ is the only possible move A can make to win, according to Bogdan's strategy he can prevent it and win .
19.08.2021 18:48
Bogdan will win. Let $(m,n)$ denote the number of stones in the two piles. Define $W=\{(a,b)|a,b>0,|a-b|\ge 2\}, L=\{(a,b)|a,b>0,|a-b|< 2\}$. Claim. A player has a winning strategy if and only if he gets a position in set $W$. Proof. To prove the claim, (1) and (2) is needed. (1) For any element in set $W$, a player can operate so that after the operation, the position is in set $L$. (2) For any element in set $L$, after any possible operation, the position is in set $W$. (1). Assume $(a,b)\in W$,and $a-b\ge 2$. The operation $(a,b) \to (a-2[\frac{a-b+1}{3}],b+[\frac{a-b+1}{3}])$ satisfies. (2). Enumerate all the possible stiuations. So using (1) and (2), the position each player get can only be in one of the two sets, and because $(1,0),(0,1),(1,1)$ will cause losing, so the one gets a position in the set $L$ loses, and the one gets a position in the set $W$ wins. Notice $(2021,0)\in W$. Thus the first player, who is Bogdan, will win the game.