Dynamic single-pile Nim using multiple bases

Arthur Holshouser ; Harold Reiter

The electronic journal of combinatorics, Tome 13 (2006)

Résumé

In the game $G_{0}$ two players alternate removing positive numbers of counters from a single pile and the winner is the player who removes the last counter. On the first move of the game, the player moving first can remove a maximum of $k$ counters, $k$ being specified in advance. On each subsequent move, a player can remove a maximum of $f(n,t) $ counters where $t$ was the number of counters removed by his opponent on the preceding move and $n$ is the preceding pile size, where $f:N\times N\rightarrow N$ is an arbitrary function satisfying the condition (1): $\exists t\in N$ such that for all $n,x\in N$, $f(n,x) =f(n+t,x) $. This note extends our earlier paper [E-JC, Vol 10, 2003, N7]. We first solve the game for functions $f:N\times N\rightarrow N$ that also satisfy the condition (2): $\forall n,x\in N$, $f(n,x+1) -f(n,x) \geq -1$. Then we state the solution when $f:N\times N\rightarrow N$ is restricted only by condition (1) and point out that the more general proof is almost the same as the simpler proof. The solutions when $t\geq 2$ use multiple bases.

Détail

DOI : 10.37236/1145

Classification : 91A46
Mots-clés : Nim type game, combinatorics, two-player games, extensive form games