Sökning: WFRF:(Larsson Åsa Bharathi)
> (2015-2019) >
Sequences and games...
Sequences and games generalizing the combinatorial game of Wythoff Nim
-
- Larsson, Urban, 1965 (författare)
- Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper, matematik,Department of Mathematical Sciences, Mathematics,University of Gothenburg,Chalmers tekniska högskola,Chalmers University of Technology
-
(creator_code:org_t)
- Göteborg : Chalmers University of Technology, 2009
- Engelska.
- Relaterad länk:
-
http://publications.... (primary) (free)
-
visa fler...
-
https://gup.ub.gu.se...
-
https://research.cha...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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}.
Ämnesord
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
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
- Beatty sequence
Publikations- och innehållstyp
- vet (ämneskategori)
- lic (ämneskategori)
Hitta via bibliotek
Till lärosätets databas