On Fraenkel’s N-Heap Wythoff’s Conjectures
2004; Birkhäuser; Volume: 8; Issue: 2 Linguagem: Inglês
10.1007/s00026-004-0217-3
ISSN0219-3094
Autores Tópico(s)Sports Analytics and Performance
ResumoThe N-heap Wythoff’s game is a two-player impartial game with N piles of tokens of sizes $$ A^1, \ldots , A^N, A^1 \leq \ldots \leq A^N $$ Players take turns removing any number of tokens from a single pile, or removing (a1,..., a N ) from all piles - ai tokens from the i-th pile, providing that $$ 0 \leq a_i \leq A^i, \sum^{N}_{i=1} a-i > = \quad \mathrm{and} \quad a_1 \bigotimes \ldots \bigotimes a_N = 0 $$ where ⊕ is the nim addition. The first player that cannot make a move loses. Denote all the P-positions (i.e., losing positions) by $$ (A^1, \ldots , A^{N-2}, A^{N-1}_n , A^{N}_{n}), A^{N-2} \leq A^{N-1}_{n} \leq A^{N}_{n} \quad \mathrm{and} \quad A^{N-1}_{n} < A^{N-1}_{n+1} \quad \mathrm{for all} \quad N \geq 1 $$ Two conjectures were proposed on the game by Fraenkel [7]. When $$ A^1, \ldots, A^{N-2} $$ are fixed, i) there exists an integer N1 such that when $$ n > N_1, A^{N}_{n} = A^{N-1}_{n} + n $$ . ii) there exist integers N2 and α_2 such that when $$ n > N_2, A^{N-1}_{n} = \lfloor n \Phi \rfloor + \epsilon_n + \alpha_2 \quad \mathrm{and} \quad A^{N}_{n} = A^{N-1}_{n} + n, \quad \mathrm{where} \quad -1 \leq \epsilon_n \leq 1 \quad \mathrm{and}\quad \Phi = (1 + \sqrt{5})/2$$ , the golden section. In this paper, we provide a sufficient condition for the conjectures to hold, and subsequently prove them for the three-heap Wythoff’s game with the first piles having up to 10 tokens.
Referência(s)