CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Sequences and games generalizing the combinatorial game of Wythoff Nim

Urban Larsson (Institutionen för matematiska vetenskaper, matematik)
Göteborg : Chalmers University of Technology, 2009.
[Licentiatavhandling]

One single Queen is placed on an arbitrary starting position of a (large) Chess board. Two players alternate in moving the Queen as in a game of Chess but with the restriction that the $L^1$ distance to the lower left corner, position $(0,0)$, must decrease. The player who moves there wins. Let $\phi =\frac{1+\sqrt{5}}{2}$, the golden ratio. In 1907 W. A. Wythoff proved that the second player wins if and only if the coordinates of the starting position are of the form $\{a_n,b_n\}$, where $a_n=\left\lfloor n\phi \right\rfloor, b_n=a_n+n$ for some non-negative integer $n$. Here, we introduce the game of \emph{Imitation Nim}, a \emph{move-size dynamic} restriction on the classical game of (2-pile) Nim. We prove that this game is a 'dual' of \emph{Wythoff Nim} in the sense that the latter has the same solution/$P$-positions as the former. On the one hand we define extensions and restrictions to Wythoff Nim---including the classical generalizations by I.G. Connell (1959) and A.S. Fraenkel (1982)---and Imitation Nim. All our games are purely combinatorial, so there are no 'hidden cards' and no 'chance device'. In fact we only study so-called \emph{Impartial games} where the set of options does not depend on whose turn it is. In particular we introduce rook-type and bishop-type \emph{blocking manoeuvres/Muller twists} to Wythoff Nim: For each move, the previous player may 'block off' a predetermined number of next player options. We study the solutions of the new games and for each blocking manoeuvre give non-blocking dual game rules. On the other hand, observing that the pair of sequences $(a_n)$ and $(b_n)$---viewed as a permutation of the natural numbers which takes $a_n$ to $b_n$ and $b_n$ to $a_n$---may be generated by a 'greedy' algorithm, we study extensive generalizations to these. We also give interpretations of our sequences as so-called \emph{Interspersion arrays} and/or \emph{Beatty sequences}.

Nyckelord: Blocking manoeuvre, Beatty sequence, Combinatorial game, Complementary sequences, Impartial game, Interspersion array, Muller twist, Nim, Permutation of the natural numbers, Stolarsky array, Wythoff Nim


The thesis consists of three papers: Permutations of the natural numbers with prescribed difference multisets, published in Integers, Volume 6 (2006), article A3. 2-pile Nim with a restricted number of move-size dynamic imitations, accepted for publication in Integers, Volume 9 (2009), article G4. Restrictions of $m$-Wythoff Nim and $p$-complementary Beatty sequences, accepted for publication in Games of no Chance 2008.



Denna post skapades 2009-11-17. Senast ändrad 2009-11-24.
CPL Pubid: 101771

 

Läs direkt!

Lokal fulltext (fritt tillgänglig)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)

Ämnesområden

Diskret matematik

Chalmers infrastruktur

Relaterade publikationer

Inkluderade delarbeten:


Permutations of the Natural Numbers with Prescribed Difference Multisets


Examination

Datum: 2009-12-08
Tid: 13:15
Lokal: Euler
Opponent: Prof. Aviezri S. Fraenkel, Department of Computer Science & Applied Mathematics, Weizmann Institute of Science, Israel

Ingår i serie

Preprint - Department of Mathematical Sciences, Chalmers University of Technology and Göteborg University 2009:42