A new heap game (Q1589501): Difference between revisions

The following game with two players is considered. There are \(k\geq 3\) heaps with finitely many tokens. At his turn each player has two strategies: (1) remove a positive number of tokens from up to \(k-1\) heaps, possibly \(k-1\) entire heaps, (2) remove the same positive number of tokens from all the \(k\) heaps. The player making the last move wins. This game is a generalization of Wythoff's game [\textit{W. A. Wythoff}, A modification of the game of Nim. Nieuw Arch. Wisk. 7, 199-202 (1907; JFM 37.0261.03)] to more than two heaps. The authors formulate and prove a theorem together with an algorithm, which decides in polynomial time for a given state of the heaps whether a player can win or not win the game.