There are 3 heaps with $100,101,102$ stones. Ilya and Kostya play next game. Every step they take one stone from some heap, but not from same, that was on previous step. They make his steps in turn, Ilya make first step. Player loses if can not make step. Who has winning strategy?
Problem
Source: All Russian Olympiad 2017,Day1,grade 10,P3
Tags: combinatorics
03.05.2017 19:04
17.10.2018 13:13
Generalization:There are $n$ heaps with $a_1,a_2,\dots a_n$ stones such that $a_1+a_2+\dots +a_n$ is odd. Ilya and Kostya play next game. Every step they take one stone from some heap, but not from same, that was on previous step. They make his steps in turn, Ilya make first step. Player loses if can not make step.Then Ilya has a winning strategy. Proof:We force llya to always take the heap with maximum stones we continue with a claim: Claim:It is always possible for llya to take stone from the heap with maximum stones. Proof of claim:Assume for country take the first place that it is no longer possible for llya to take stone from the heap with maximum stone.Then the last heap that llya has taken stone from it has $k-1$ stones and there is a heap with $k$ stones that Kostya has taken stone from it in the previous stage.But then before llya's last move there was a heap with $k$ stones and a heap with $k+1$ stones and llya choosed the heap with $k$ stones to take stone from it which is indeed a contradiction. Returning to the problem by the claim llya can take a stone if there exist one.Since $a_1+a_2+\dots +a_n$ is odd we are done. Comment:When the sum of stones is even things become a bit more complicated but still solvable.If the hoop with maximum stones has more stones than the sum of other hoops then the first player still has winning strategy by sticking to the maximum otherwise second player has a wining strategy by sticking to the maximum stone hoop that he(she) can take.
16.03.2022 14:32
llya has a winning strategy. Claim: If piles have $a,b,a+b$ stones (in some order) for some $a,b \in \mathbb Z_{\ge 0}$, then player to move losses. Proof: The winning strategy for the opponent is simply. Whenver the first player take a stone from one of sets $\{a,b\}\{a+b\}$, then the opponent just takes one from the other. This preserves sum condition too at each step. $\square$ Let $a_1,a_2,a_3$ denote stones in three piles, which are $100,101,102$ originally (respectively). llya will always take a stone from $a_1$. We show at some point, when its Kostya turn we have $a_1 = |a_2 - a_3|$, which would suffice by our Claim. Consider quantity $$ S = a_1 - |a_2 - a_3| $$Note after each move of llya, $S$ even while its odd after each move of Kostya. Also, $S > 0$ originally. Moreover, $S$ takes jump of at most $2$. When $a_1 = 0$, we have $S \le 0$. So $S$ is $0$ at after some move of llya, as desired. $\blacksquare$