Two players play a game. They have $n > 2$ piles containing $n^{10}+1$ stones each. A move consists of removing all the piles but one and dividing the remaining pile into $n$ nonempty piles. The player that cannot move loses. Who has a winning strategy, the player that moves first or his adversary?
Problem
Source: 2023 Tuymaada Junior P4
Tags: combinatorics, Game Theory, combinatorial game theory, Tuymaada
30.12.2023 15:25
We will solve the general form of the problem and determine for what starting piles ($a_1,a_2, \cdots , a_n$) first player has winning strategy. We label an integer $k$ with "win" if there exist positive integers $a_1 , a_2 , \cdots , a_n$ such that $k = a_1 + a_2 + \cdots + a_n$ and if game starts with piles ($a_1,a_2, \cdots , a_n$) second player has winning strategy and label $k$ with "loose" otherwise. It's obvious that first player has winning strategy for ($a_1,a_2, \cdots , a_n$) iff at least one of $a_1,a_2, \cdots , a_n$ is a win integer. lemma 1 : $k$ is win iff exist positive integers $a_1,a_2, \cdots , a_n$ such that $ k = a_1 + a_2+ \cdots + a_n $ and all $a_i$'s are loose integers. Now we show that the set \[L(n) = \{ k \in \mathbb{N} : (k\mod n(n-1)) \in \{1,2,3,\cdots , n-1 \} \} \] is the set of all loose integers. Obviously $1,2,3, \cdots , n-1$ are all loose integers .We complete the proof by induction on $k$ Now suppose for a natural $k$ we proved $m \leq kn(n-1)$ , $m$ is loose iff $m \in L(n)$.Let $kn(n-1)+1\leq m \leq kn(n-1)+(n-1)$ and suppose by contradiction that $m$ is win which is equivalent that exist $a_1,a_2, \cdots , a_n$ such that $m$ = $a_1+a_2+ \cdots + a_n$ and all $a_i$'s are loose. By inductive hypothesis $a_i \in L(n) \Longrightarrow a_i \mod n(n-1) \in \{1,2, \cdots n-1 \} \Longrightarrow n \leq (a_1 + a_2 + \cdots + a_n \mod n(n-1)) \leq n(n-1) \Longrightarrow n \leq (m \mod n(n-1)) \leq n(n-1)$ that is contradiction. So $kn(n-1)+1 \cdots kn(n-1) + (n-1)$ are all loose. Now by lemma 1 easily could check that all numbers from $kn(n-1) + n$ to $(k+1)n(n-1)$ are win so inductive step is complete and we are done. $\Longrightarrow$ Second player has winning strategy for starting piles ($a_1,a_2, \cdots , a_n$) iff all of $a_i$'s are in $L(n)$ and first player has strategy otherwise.