\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\def\N{\mathbb{N}}
\def\n{\mathbb{N}_0}
\def\G{\text{-GDWN}}
\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{decorations.pathmorphing}
\usetikzlibrary{backgrounds}
\usetikzlibrary{fit}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Wythoff Nim Extensions and Splitting \\
\vskip .10in
Sequences
}
\vskip 1cm
\large
Urban Larsson\\
Mathematical Sciences \\
Chalmers University of Technology\\
and University of Gothenburg\\
G\"oteborg \\
Sweden\\
\href{mailto:urban.larsson@yahoo.se}{\tt urban.larsson@yahoo.se}
\end{center}
\vskip .2 in
\begin{abstract}
We study extensions of the classical impartial combinatorial game of
Wythoff Nim. The games are played on two heaps of tokens, and have
\emph{symmetric} move options, so that, for any integers $0\le x\le y$,
the outcome of the \emph{upper} position $(x, y)$ is identical to that
of $(y, x)$. First we prove that $\phi^{-1}=\frac{2}{1+\sqrt{5}}$ is a
lower bound for the lower asymptotic density of the $x$-coordinates of
a given game's \emph{upper} P-positions. The second result concerns a
subfamily, called a Generalized Diagonal Wythoff Nim, recently
introduced by Larsson. A certain \emph{split} of P-positions,
distributed in a number of so-called P-beams, was conjectured for many
such games. The term \emph{split} here means that an infinite sector of
upper positions is void of P-positions, but with infinitely many upper
P-positions above and below it. By using the first result, we prove
this conjecture for one of these games, called $(1,2)$-GDWN, where a
player moves as in Wythoff Nim, or instead chooses to remove a positive
number of tokens from one heap and twice that number from the other.
\end{abstract}
\section{Introduction}
We study generalizations of the 2-player impartial take-away games \emph{2-pile Nim} \cite{Bou02}, and \emph{Wythoff Nim} \cite{Wyt07}. A background on impartial (take-away) games can be found in the books \cite{BCG82, Con76}. The literature on variations of Wythoff Nim is steadily increasing; for some further background, we refer to the papers \cite{DFNR10, Fra82, Lar09, Lar11, Lar12, Lar, LW}. We use standard terminology for the outcomes of such games without ties. A position is a previous-player win, a \emph{P-position}, if none of its options is a P-position; otherwise it is a next-player win, an \emph{N-position}. We follow the conventions of \emph{normal play}, that is, a player who is not able to move loses. Thus, given an impartial game, we get a recursive characterization of the set of all P-positions beginning with the terminal position(s).
We let $\N$ denote the positive integers and $\n$ the non-negative integers.
The game of 2-pile Nim is played on two piles of a finite number of tokens. A legal move consists of removing any positive number of tokens from exactly one pile, at most a whole pile.
We represent a position by an ordered pair $(x,y)\in \n\times \n$, denoting the number of tokens in the respective heaps. That is, the set of options from any position $(x,y)$ is $$\text{Nim}(x,y)=\{(x-t,y)\mid x-t\ge 0\}\cup \{(x,y-t)\mid y-t\ge 0\}.$$ It is easy to see that the P-positions of this game are those where the pile heights are equal; the positions $(x, x)$, for $x\in \n$, Bouton \cite{Bou02}. We regard these positions as an infinite P-\emph{beam} of slope 1, with its source at the origin. See Figures \ref{F0} and \ref{F1}.
In the game of Wythoff Nim a player moves as in Nim or instead removes the same number of tokens from both piles, at most the number in the smaller pile. Thus the set of options from any position $(x,y)$ is $$\text{WN}(x,y)=\text{Nim}(x,y)\cup \{(x-t,y-t)\mid x-t\ge 0, y-t\ge 0\}.$$ Let $$\phi = \frac{\sqrt{5}+1}{2}$$ denote the \emph{golden ratio}. It is known, Wythoff \cite{Wyt07}, that a position of this game is P if and only if it belongs to the set $$\{(\lfloor \phi n\rfloor ,\lfloor\phi^2n\rfloor ), (\lfloor \phi^2 n\rfloor ,\lfloor\phi n\rfloor )\mid n\in \n\};$$ see also Table \ref{F:1}. Thus, in the transformation from 2-pile Nim to Wythoff Nim, the single Nim-beam of P-positions has \emph{split} into two distinct beams, with sources in the origin, and slopes $1/\phi$ and $\phi$ respectively. The intuitive meaning of the term \emph{split} is that there is an infinite sector, between two infinite regions of P-positions, which contains only N-positions. More formally, a sequence of pairs of natural numbers $(x_i,y_i)$ \emph{splits}, or $(\alpha,\epsilon)$-\emph{splits}, if there are positive real numbers $\alpha$ and $\epsilon$ such that the set $$\left\{i>n\mid \alpha\le \frac{y_i}{x_i}\le \alpha +\epsilon\right\}$$ is empty, for $n$ sufficiently large, and such that both $$\left\{(x_i,y_i)\mid \alpha > \frac{y_i}{x_i}\right\},$$ and $$\left\{(x_i,y_i)\mid \alpha +\epsilon < \frac{y_i}{x_i}\right\}$$ are infinite.
Let $p, q\in \N$ (with $p < q$). The game of Generalized Diagonal Wythoff Nim, $(p,q)$-GDWN \cite{Lar12}, extends the rules of Wythoff Nim such that a player may instead remove $pt$ tokens from either pile and $qt$ tokens from the other, where $t\in \N$, provided that both heap sizes remain non-negative. (For given $p$ and $q$ we sometimes simply denote this game by GDWN.) That is, the set of options from any position $(x,y)$ is
\begin{align*}
(p,q)\G(x,y)=\text{WN}(x,y)&\cup\{(x-pt,y-qt)\mid x-pt\ge 0,y-qt\ge 0\}\\&\cup\{(x-qt,y-pt)\mid x-qt\ge 0,y-pt\ge 0\}.
\end{align*}
See also Figure \ref{F0} for the rules of $(1,2)$-GDWN and its first few P-positions. In Figure~\ref{F1} we view the initial behavior of their respective P-beams.
\begin{figure}[ht!]
\begin{center}
\vspace{0.1 cm}
{\includegraphics[width=0.85\textwidth]{gdwn300.eps}}
\end{center}\caption{The pictures illustrate typical move
options (in gray) and initial P-positions of Nim, Wythoff Nim, and $(1, 2)$-GDWN respectively. The black square is a given game position. The white P's represent the winning options from this position for the respective games. Hence the given position is N for each game. The lower left corner represents the terminal position $(0,0)$.}\label{F0}
\end{figure}
\begin{figure}[ht!]
\begin{center}
\vspace{0.5 cm}
{\includegraphics[width=0.19\textwidth]{NimP_L.eps}\hspace{0.4 cm}
{\includegraphics[width=0.19\textwidth]{WythP_L.eps}}
\includegraphics[width=0.31\textwidth]{1_2boardNEW.eps}}
\end{center}\caption{These figures give the initial P-positions of the games Nim, Wythoff Nim and $(1,2)\G$. The left most figure illustrates 2-pile Nim's single P-beam of slope 1. Then, in the middle we find Wythoff Nim's pair of P-beams with slopes $\phi^{-1}$ and $\phi$ respectively and, at last, the initial P-positions of $(1,2)\G$, for all $x$-coordinates $\le 50000$. Experimental results from \cite{Lar12} indicate that the split of the upper P-positions ``accumulate" on two lines of slope $1.477\cdots$ and $2.247\cdots$ respectively.}\label{F1}
\end{figure}
The motivation for this paper considers the splitting of Wythoff Nim's P-beams for the case $(1,2)\G$; Section \ref{S:3}. In Section \ref{S:4} we indicate why an analogous result holds also for $(2,3)\G$. Before this, in Section \ref{S:2}, we demonstrate a general result for certain \emph{extensions} of Wythoff Nim. We show that the density $\phi^{-1}$, obtained by projecting the upper P-positions of Wythoff Nim on the $x$-axis, suffices as a lower bound for the lower asymptotic density of similar projections, for any extension of Wythoff Nim. Let us begin by defining this general class of games.
\section{A density bound for Wythoff Nim extensions}\label{S:2}
An \emph{extension} of Wythoff Nim, say $G$, has a set of options $G(x,y)\supseteq$ WN$(x,y)$, from each given position $(x,y)\in \n\times\n$. The options are of the form $(x-m_1, y-m_2)\in G(x,y)$, $x\ge x-m_1\ge 0$ and $y\ge y-m_2\ge 0$; not both $m_1 = m_2 = 0$, to disallow ties. We require that all options be \emph{symmetric}, that is, $(m_1, m_2)$ is a move from $(x,y)$ if and only if $(m_2, m_1)$ is a move from $(y,x)$. Note that this is a relaxation of the traditional form of symmetric move options for variations of Wythoff Nim in the literature. We have chosen our symmetric variant, because it appears to be the weakest general form that guaranties symmetric P-positions; that is $(x,y)$ is P if and only if $(y,x)$ is P. We also require that at most finitely many moves of the form $(m_1, m_2)$, $m_1>0$ and $m_2>0$, have the same $m_1$-coordinate ($m_2$-coordinate) whenever moving from a fixed column (row). That is, given a column $x>0$, the total number of non-Nim type options, from all positions of the form $(x, y)$, is finite (and by symmetry, given a row $y>0$, the total number of non-Nim type options, from all positions of the form $(x, y)$, is finite). As we will see, in this way the new game will have so-called \emph{complementary} sets (sequences) defining the P-positions.
Two sets of positive integers are \emph{complementary} if each positive integer occurs in precisely one of these sets. A pair of sequences are \emph{complementary} if they are complementary regarded as sets, and if there is no repetition within each sequence. The P-positions of Wythoff Nim are very well structured, in particular, the differences of coordinates are $\Delta_n := B_n-A_n=n$, where $A_n:=\lfloor\phi n\rfloor \text{ and } B_n:=\lfloor\phi^2 n\rfloor$, for all $n\in \n$. We obviously get the density for the $A$-sequence as $\lim_{n\in \N} \frac{n}{A_n} =\phi^{-1}$. It is well known that the sequences defining Wythoff Nim's non-terminal P-positions are complementary; see also Table~\ref{F:1}. We will use this notation for Wythoff's sequences throughout the paper.
\begin{table} [ht!]
\vspace{0.5 cm}
\begin{center}
\begin{tikzpicture} [scale = 0.56]
\foreach \x/\y in {0/2, 1/2, 2/2, 3/2, 4/2, 5/2, 6/2}
\draw[thick,brown] (\x, \y) rectangle (\x+1, \y+1);
\foreach \x/\y in {0/0, 1/0, 2/0, 3/0, 4/0, 5/0, 6/0, 0/1, 1/1, 2/1, 3/1, 4/1, 5/1, 6/1}
\draw[thick,blue] (\x, \y) rectangle (\x+1, \y+1);
\draw (-0.5 , 1.5) node {$B_n$};
\draw (-0.5 , 0.5) node {$A_n$};
\draw (-0.5 , -0.5) node {$n$};
\draw (-0.5 , 2.5) node {$\Delta_n$};
\draw (0.5, -0.5) node {$0$};
\draw (1.5, -0.5) node {$1$};
\draw (2.5, -0.5) node {$2$};
\draw (3.5, -0.5) node {$3$};
\draw (4.5, -0.5) node {$4$};
\draw (5.5, -0.5) node {$5$};
\draw (6.5, -0.5) node {$6$};
\draw (7.5, -0.5) node {$\ldots$};
\draw (7.5, 0.5) node {$\ldots$};
\draw (7.5, 1.5) node {$\ldots$};
\draw (7.5, 2.5) node {$\ldots$};
\draw (0.5, 0.5) node {$0$};
\draw (1.5, 0.5) node {$1$};
\draw (2.5, 0.5) node {$3$};
\draw (3.5, 0.5) node {$4$};
\draw (4.5, 0.5) node {$6$};
\draw (5.5, 0.5) node {$8$};
\draw (6.5, 0.5) node {$9$};
\draw (0.5, 1.5) node {$0$};
\draw (1.5, 1.5) node {$2$};
\draw (2.5, 1.5) node {$5$};
\draw (3.5, 1.5) node {$7$};
\draw (4.5, 1.5) node {$10$};
\draw (5.5, 1.5) node {$13$};
\draw (6.5, 1.5) node {$15$};
\draw (0.5, 2.5) node {$0$};
\draw (1.5, 2.5) node {$1$};
\draw (2.5, 2.5) node {$2$};
\draw (3.5, 2.5) node {$3$};
\draw (4.5, 2.5) node {$4$};
\draw (5.5, 2.5) node {$5$};
\draw (6.5, 2.5) node {$6$};
\end{tikzpicture}
\end{center}
\caption{Wythoff Nim's unique terminal position is $(A_0,B_0)=(0,0)$. Its upper P-positions are $(1,2),\ldots, (A_n,B_n),\ldots$ and $\Delta_n = B_n-A_n= n$ for all~$n$.}\label{F:1}
\end{table}
We code the \emph{upper P-positions} of a given Wythoff Nim extension $G$ by $(a_n, b_n)$ where $0 < a_n < b_n$, for all $n > 0$, and where the $a$-sequence is strictly increasing. By symmetry, $G$'s complete set of P-positions will be $\{(a_i, b_i),(b_i, a_i)\mid i\in \N\}\cup\{(0,0)\}$. We let $\delta_i := b_i - a_i$, for all $i$. For convenience we denote the unique terminal position by $ (a_0, b_0) := (0,0)$. That this is indeed the unique terminal position follows since all Nim-type moves are legal for any Wythoff extension.
\begin{table} [ht!]
\vspace{.5 cm}
\begin{center}
\begin{tikzpicture} [scale = 0.56]
\foreach \x/\y in {0/2, 1/2, 2/2, 3/2, 4/2, 5/2, 6/2}
\draw[thick,brown] (\x, \y) rectangle (\x+1, \y+1);
\foreach \x/\y in {0/0, 1/0, 2/0, 3/0, 4/0, 5/0, 6/0, 0/1, 1/1, 2/1, 3/1, 4/1, 5/1, 6/1}
\draw[thick,blue] (\x, \y) rectangle (\x+1, \y+1);
\draw (-0.5 , 1.5) node {$b_n$};
\draw (-0.5 , 0.5) node {$a_n$};
\draw (-0.5 , -0.5) node {$n$};
\draw (-0.5 , 2.5) node {$\delta_n$};
\draw (0.5, -0.5) node {$0$};
\draw (1.5, -0.5) node {$1$};
\draw (2.5, -0.5) node {$2$};
\draw (3.5, -0.5) node {$3$};
\draw (4.5, -0.5) node {$4$};
\draw (5.5, -0.5) node {$5$};
\draw (6.5, -0.5) node {$6$};
\draw (7.5, -0.5) node {$\ldots$};
\draw (7.5, 0.5) node {$\ldots$};
\draw (7.5, 1.5) node {$\ldots$};
\draw (7.5, 2.5) node {$\ldots$};
\draw (0.5, 0.5) node {$0$};
\draw (1.5, 0.5) node {$1$};
\draw (2.5, 0.5) node {$2$};
\draw (3.5, 0.5) node {$4$};
\draw (4.5, 0.5) node {$7$};
\draw (5.5, 0.5) node {$8$};
\draw (6.5, 0.5) node {$9$};
\draw (0.5, 1.5) node {$0$};
\draw (1.5, 1.5) node {$3$};
\draw (2.5, 1.5) node {$6$};
\draw (3.5, 1.5) node {$5$};
\draw (4.5, 1.5) node {$10$};
\draw (5.5, 1.5) node {$14$};
\draw (6.5, 1.5) node {$17$};
\draw (0.5, 2.5) node {$0$};
\draw (1.5, 2.5) node {$2$};
\draw (2.5, 2.5) node {$4$};
\draw (3.5, 2.5) node {$1$};
\draw (4.5, 2.5) node {$3$};
\draw (5.5, 2.5) node {$6$};
\draw (6.5, 2.5) node {$8$};
\end{tikzpicture}
\end{center}
\caption{These sequences constitute the first few P-positions of the Wythoff Nim extension $(1,2)\G$ and $\delta_i=b_i-a_i$, for all $i$. Note that the $b$-sequence is not increasing and hence neither the $\delta$-sequence. It is not known whether all positive integers are represented in the latter sequence.}\label{F:2}
\end{table}
\begin{proposition}\label{prop}
The P-positions of any Wythoff Nim extension satisfy the following \emph{Property~W}: for all $n \in \N$, $a_{n-1} < a_n$ and $a_n < b_n$; for all $i\ne j$, $\delta_i\ne \delta_j$, and the sequences $a = (a_i)_{i\in \N}$ and $b = (b_i)_{i\in \N}$ are complementary.
\end{proposition}
\begin{proof} The inclusion $G(x,y)\supseteq$ WN$(x,y)$ implies that we can choose the $a$ and $b$ sequences such that $a_{n-1} < a_n$, $a_n < b_n$ for all $n > 0$: the Nim-type moves give the first inequality and the diagonal type moves give the latter. Indeed, if there were $a_i, a_j$ such that $a_i = a_j$ and where $b_i < b_j$, then a Nim-type move would take $(a_j,b_j)$ to $(a_i, b_i)$, which is impossible, so all $a_i$'s have to be distinct. Neither can there be any index such that $b_n = a_n$, because then a diagonal type move would connect $(0,0)$ with $(a_n, b_n)$. Hence it is clear that $a_n < b_n$, for all $n$, where we let positions of the form $(a_n, b_n)$ represent the upper P-positions (and by symmetric rules of game, it follows that positions of the form $(b_n, a_n)$ represent the lower P-positions). Further, we cannot have repetitions in the $\delta$-sequence because this would connect two P-positions via a diagonal Wythoff type move. It remains to demonstrate that the sequences $a$ and $b$ are complementary. Symmetry and the inclusion of all Nim-type moves guarantee that there can be no repetitions of entries. That is, for each positive integer $x$, there is at most one index $i$ such that $a_i=x$ or $b_i=x$, but not both. Thus it suffices to demonstrate that, for each $x$, there is an index $i$ such that either $a_i=x$ or $b_i=x$. Let $x$ be an arbitrary column. By the previous argument, there are at most $x$ P-positions in the lower $x-1$ columns (starting with $x=1$ and the terminal P-position $(0,0)$). Each such P-position is an option for at most finitely many game positions in the $x$th column, by the definition of a Wythoff extension. Hence, there is a least row $y$ for which $(x,y)$ does not have any P-position as an option. Then $(x,y)$ is P. Hence there is at least one P-position in each column and so, by symmetry, $a$ and $b$ must be complementary.
\end{proof}
\begin{table} [ht!]
\vspace{.2 cm}
\begin{center}
\begin{tikzpicture} [scale = 0.56]
\foreach \x/\y in {0/2, 1/2, 2/2, 3/2, 4/2, 5/2, 6/2}
\draw[thick,brown] (\x, \y) rectangle (\x+1, \y+1);
\foreach \x/\y in {0/0, 1/0, 2/0, 3/0, 4/0, 5/0, 6/0, 0/1, 1/1, 2/1, 3/1, 4/1, 5/1, 6/1}
\draw[thick,blue] (\x, \y) rectangle (\x+1, \y+1);
\draw (-0.5 , 1.5) node {$b_n$};
\draw (-0.5 , 0.5) node {$a_n$};
\draw (-0.5 , -0.5) node {$n$};
\draw (-0.5 , 2.5) node {$\delta_n$};
\draw (0.5, -0.5) node {$0$};
\draw (1.5, -0.5) node {$1$};
\draw (2.5, -0.5) node {$2$};
\draw (3.5, -0.5) node {$3$};
\draw (4.5, -0.5) node {$4$};
\draw (5.5, -0.5) node {$5$};
\draw (6.5, -0.5) node {$6$};
\draw (7.5, -0.5) node {$\ldots$};
\draw (7.5, 0.5) node {$\ldots$};
\draw (7.5, 1.5) node {$\ldots$};
\draw (7.5, 2.5) node {$\ldots$};
\draw (0.5, 0.5) node {$0$};
\draw (1.5, 0.5) node {$1$};
\draw (2.5, 0.5) node {$3$};
\draw (3.5, 0.5) node {$4$};
\draw[red] (4.5, 0.5) node {\bf{7}};
\draw (5.5, 0.5) node {$8$};
\draw (6.5, 0.5) node {$9$};
\draw (0.5, 1.5) node {$0$};
\draw (1.5, 1.5) node {$2$};
\draw (2.5, 1.5) node {$5$};
\draw (3.5, 1.5) node {$6$};
\draw (4.5, 1.5) node {$10$};
\draw (5.5, 1.5) node {$13$};
\draw (6.5, 1.5) node {$15$};
\draw (0.5, 2.5) node {$0$};
\draw (1.5, 2.5) node {$1$};
\draw[red] (2.5, 2.5) node {\bf{2}};
\draw[red] (3.5, 2.5) node {\bf{2}};
\draw (4.5, 2.5) node {$3$};
\draw (5.5, 2.5) node {$5$};
\draw (6.5, 2.5) node {$6$};
\end{tikzpicture}
\end{center}
\caption{These sequences do not correspond to the initial P-positions of any Wythoff Nim extension. Although the sequences do not contain any repetitions, they cannot correspond to such P-positions since $\delta_2=\delta_3=2$. The table indicates the consequences of a given lower sequence growing too fast. The ``7" in column 4 forces both ``5" and ``6" to reside in a lower column in the upper sequence. We study this type of behavior in our asymptotic result in Theorem \ref{L:2}.}\label{F:3}
\end{table}
For the other direction, one can see that any pair of sequences satisfying Property W constitute the P-positions of some Wythoff Nim extension. Namely, for each $i$, there are only finitely many positions of the form $(a_i,y)$, with $y 0\mid a_i < n\}}{n} \ge \phi^{-1}-o(1)
\end{align}
and
\begin{align}\label{bin}
\frac{\#\{i> 0\mid b_i < n\}}{n} \le \phi^{-2}+o(1).
\end{align}
In particular the result holds for $\{(a_i, b_i)\}$ representing the upper P-positions of any Wythoff Nim extension.
\end{theorem}
\begin{proof} For any given Wythoff Nim Extension, define the $y$-sequence as the unique permutation of the $b$-sequence with entries in increasing order. That is $y_n < y_{n+1}$ for all $n$ and $\{y_n\} = \{b_n\}$. Define the unique surjective function $j: \N\rightarrow \N$, $j=j(n)$ such that, for all $n$, $a_j \le n < a_{j+1}$. (This is well defined by $(a_i)$ strictly increasing and $a_1 = 1$.) Suppose that (\ref{ain}) does not hold. Then, by $(a_i)$ increasing, there is an $\epsilon' > 0$ such that, for all sufficiently large $n$, $\frac{j(n)}{a_{j(n)}} < \phi^{-1} - \epsilon'$. By inverting this equation, we obviously get $\frac{1}{\phi^{-1} - \epsilon'} < \frac{a_{j(n)}}{j(n)}$, which implies that there is an $\epsilon > 0$ such that, for all sufficiently large $n$, $\phi n + \frac{\epsilon n}{2} < a_n$. By complementarity this implies, for all sufficiently large $n$, $\phi^2n - \gamma(\epsilon) \ge y_n$, where $\gamma (\epsilon) > \frac{\epsilon n}{2}$ is a function of $\epsilon$ only.
Thus
\begin{align}\label{incr}
\delta'_n &:= y_n - a_n\notag\\
&< (\phi^2-\phi)n-\epsilon n\notag \\
&= (1-\epsilon)n,
\end{align}
for all sufficiently large $n$. Hence, since all entries in the sequence $(\delta'_n)_{n\le N}$ are positive integers, it must contain at least $\epsilon N$ (pairwise) repetitions, for all sufficiently large $N$.
Given $C\in \N$, define the finite set $S_b = S_b(C)$, by $x\in S_b$ if and only if $b_x \le C$. That is $S_b$ contains the indices of all $b$-entries smaller than $C$. For a given $C$, let $(n_i)$ be the unique increasing sequence of the numbers in $S_b$. Then, clearly $n_i\ge i$, for all $i$, and therefore also, by $(a_i)$ increasing, $a_{n_i}\ge a_i$, for all $i$. Suppose now that $N$ is sufficiently large, so that $(\delta'_n)_{n\le N}$ contains $\epsilon N$ repetitions, as defined in the previous paragraph, and study the unique set $S_b$ of size $N$. It contains the indices of the $N$ smallest entries in the $b$-sequence, $(n_i)_{i=1}^N$. Thus, since $\sum_{S_b} a_{i} \ge \sum_{i=1}^N a_i$ and $\sum_{S_b} b_{i} = \sum_{i=1}^N y_i$, we get $\sum_{S_b} \delta_{i} \le \sum_{i=1}^N \delta'_i$, and so the sequence $(\delta_i)_{i=1}^N$ must also contain at least $\epsilon N$ repetitions for all sufficiently large $N$. This contradicts property W, and so (\ref{ain}) must hold and thus, by complementarity also (\ref{bin}).
\end{proof}
\section{Splitting P-positions for $(1,2)\G$}\label{S:3}
In this section we analyze the game $(1,2)\G$ from paper \cite{Lar12} and prove that its upper P-positions $(2,0.05)$-split.
The following lemma shows that it suffices to establish a positive lower asymptotic density for $x$-coordinates of P-positions above the line $y=2x$.
\begin{lemma}\label{L:3}
Suppose that there is a positive lower asymptotic density of $x$-coordinates of P-positions above the line $y=2x$. Then, the upper P-positions $\{(a_n,b_n)\mid n\in \n\}$, of $(1,2)\G$, split.
\end{lemma}
\begin{proof}
Let $(k_i)$ denote the unique increasing sequence of indices such that, for all $i\in\N $, $2 < b_{k_i}/a_{k_i}$ and if $k_i < j < k_{i+1}$ then $b_j/a_j < 2$ (put $k_0=0$).
Already in paper \cite{Lar12} we proved that $(k_i)$ is infinite. Further it was demonstrated that, by a `greedy' choice, the $b$-sequence satisfies, for all $i$,
\begin{align}\label{+1}
b_{k_{i+1}} = 2(a_{k_{i+1}} - a_{k_{i}})+b_{k_{i}}+1.
\end{align}
The assumption is that there is an $\epsilon >0$ such that, for all sufficiently large $N$,
\begin{align}\label{iN}
\#\{i\mid a_{k_i} \phi^{-1}-o(1)$.
By Theorem~\ref{L:2}, for all sufficiently large $N$, the number of N-beams of slope 1, which intersect the (red) dashed line in Figure \ref{fig5} between $y=N$ and $y=\frac{3N}{2}$, and originating from P-positions in region
\begin{itemize}
\item [(I)] is at least $\tau\frac{N}{2}$,
\item [(II)] is at least $c\tau\frac{N}{2}$, where $01.05N$, which contradicts the definition of N and P, namely it implies that either there are two P-positions on the same line of slope 2 or there are two P-positions on the same line of slope 1.
\end{proof}
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale = 3]
\draw [<->,thick] (0,4) node (yaxis) [above] {$y$}
|- (3,0) node (xaxis) [right] {$x$};
\draw[blue, thick] (0,0) coordinate (a_1) -- (3,3) coordinate (a_2);
\draw[green, thick] (0,0) -- (2,4);
\draw[green, thick] (2/3,1/3) -- (2,3);
\draw (0,0) -- (3,3/2);
\draw[blue, thick] (1,2) -- (2,3);
\draw[dashed,red,thick] (2,2) -- (2,4);
\draw[dotted] (1,0) -- (1,.18);
\draw[dotted] (1,0.36) -- (1,1);
\draw[dotted] (.666,0) -- (.666,.333);
\draw[dashed,thick] (1,1) -- (1,2);
\draw[dotted] (2,0) -- (2,2);
\draw (0.75, 1.05) node {I};
\draw (1.75, 2.1) node {II};
\draw (1.25, 1.9) node {II};
\draw (1.75, 3.1) node {III};
\draw (0.61, .43) node {IV};
\draw (2,-0.12) node {$N$};
\draw (1,-0.12) node {$N/2$};
\draw (.67,-0.12) node {$N/3$};
\draw (2.3,2) node {$(N,N)$};
\draw (2.35,3) node {$(N,3N/2)$};
\draw (2.3,4) node {$(N,2N)$};
\draw (1.4,1) node {$(N/2,N/2)$};
\draw (1.06,.26) node {$(N/3,N/6)$};
\fill[red] (2/3,1/3) circle (.7pt);
\fill[red] (2,2) circle (.7pt);
\fill[red] (1,1) circle (.7pt);
\fill[red] (2,3) circle (.7pt);
\fill[red] (2,4) circle (.7pt);
\end{tikzpicture}\caption{We consider P-positions in four regions sending N-positions to lattice points with $x$-coordinate $N$. The ones from region I and II have slope 1 and the ones from region I, III and IV have slope 2. The $y$-coordinate $3N/2$ is pivotal in our argument. Below it we count the beams of slope 1 and above it the beams of slope 2.}\label{fig5}
\end{center}
\end{figure}
%\clearpage
\section{The game $(2,3)\G$}\label{S:4}
By an analogous method one can also prove that the upper P-positions of $(2,3)\G$ split. Some extra care is needed for the treatment of the P-positions above the line of slope 3/2, but one can see that the packing of the N-beams originating from P-positions above this line will be dense also for this game; within an $O(N)$ distance to the $y$-coordinate $3N/2$ (with $N$ even), although they will not be strictly ``greedy" as for $(1,2)\G$. Another slight complication is that one needs to regard two columns, $N, N+1$ for this game, rather than the single $N$-column in $(1,2)\G$. However this still implies that the number of positions to check for its N-status, between this line and the one of slope 1, is $N$. Further, the contribution from analogues of regions I, II and III in Figure \ref{fig5} gives the same estimate as for $(1,2)\G$. By Theorem~\ref{L:2} and by inspection, for this case the contribution from region IV gives an additional number of P-positions below $x$-coordinate $3N/10$; there are at least $3(1-\tau)N/10$ of them. Hence the total number is at least $(\frac{6\tau}{5} + \frac{3}{10})N>1.04N$.
\begin{theorem}
The upper P-positions $\{(a_n,b_n)\mid n\in \n\}$ of $(2,3)\G$ split.
\end{theorem}
For other variations of GDWN the analysis seems more technical and new ideas may be needed. In particular, for such games, various log-period behaviors of diverging P-beams are observed in the paper \cite{Lar12}, as does not appear to be the case for (1,2)-GDWN and (2,3)-GDWN.
\section{Discussion and questions} The final question in the thesis \cite{KnLa04} concerns an analog to Property W (as defined in Proposition \ref{prop}) for general permutations. Let us restate it: is there any permutation $g$ on the natural numbers such that $g(x)-x\ne g(y)-y$ whenever $x\ne y$ and such that $$ \limsup_{i\rightarrow \infty} \frac{g(i)}{i} -\liminf_{i\rightarrow \infty}\frac{g(i)}{i}<1?$$ In this paper we have provided a negative answer in case $g$ is an involution. The question remains open for general permutations.
Via Theorem \ref{L:2}, Property W in fact implies a property for a given set $S$ of positive integers as follows. Let $\{s_i\} = S\subset \N$, with the $s_i$'s distinct (and in increasing order). We have demonstrated that, if there is an ordering $(t_i)$ of the numbers in $\N\setminus S$ such that $t_i - s_i = t_j - s_j > 0$ implies $i = j$, then the lower asymptotic density of $S$ must be greater than or equal to $\phi^{-1}$.
The converse does not hold in general. For example any set $S$ beginning as the $a$-sequence in Table \ref{F:3} does not have this property, but it can easily be constructed to have lower density greater than or equal to $\phi^{-1}$, for example, by letting it converge to Wythoff's $A$-sequence. This converse question is more meaningful in the game's setting. For example, one would like to classify those \emph{restrictions} of Wythoff Nim that satisfy (\ref{ain}). Does the removal of finitely many diagonal moves from Wythoff Nim change this property? Then there will be repetitions in the $\delta$-sequence, even occurrences $a_i=b_i$, so we have to relax property W as appropriate.
A sequence $(x_i,y_i)$ \emph{density-splits} if it $(\alpha,\epsilon)$-splits and each of the sets $\{x_i\mid \alpha\ge \frac{y_i}{x_i}\}$ and $\{x_i\mid \alpha +\epsilon \le \frac{y_i}{x_i}\}$ has a positive lower asymptotic density. Do our results hold if we exchange split for density-split everywhere? We conjecture a positive answer, but some details are still missing for the upper P-positions' lower P-beam, see paper \cite{Lar12}.
\section{Acknowledgements}
I would like to thank the anonymous referee for many helpful comments.
\begin{thebibliography}{99}
\bibitem{BCG82} E. R. Berlekamp, J. H. Conway, and R. K. Guy,
\emph{Winning Ways}, Vols.~1--2, Academic Press, 1982.
Second edition, Vols.~1--4, A. K. Peters, 2001--2004.
\bibitem{Bou02} C. L. Bouton, Nim, A game with a complete mathematical theory, \emph{Ann. of Math.} \textbf{3} (1901/02), 35--39.
\bibitem{Con76} J. H. Conway, \emph{On Numbers and Games}, Academic Press,
1976. Second edition, A. K.Peters, 2001.
\bibitem{DFNR10} E. Duch\^ene, A. S. Fraenkel, R. J. Nowakowski, and M. Rigo, Extensions and restrictions of Wythoff's game preserving its P-positions. \emph{J. Combinat. Theory Ser. A} \textbf{117} (2010), 545--567.
\bibitem{Fra82} A. S. Fraenkel, How to beat your Wythoff games' opponent on three fronts, \emph{Amer. Math. Monthly} {\bf 89} (1982) 353--361.
\bibitem{HeLa06} P. Hegarty and U. Larsson, Permutations of the natural numbers with prescribed difference multisets, \emph{Integers} \textbf{6} (2006), \#A3.
\bibitem{KnLa04} J. Knape and U. Larsson, \emph{Sets of integers and permutations avoiding solutions to linear equations}, Master's thesis, University of G\"oteborg, 2004.
\bibitem{Lar09} U. Larsson, 2-pile Nim with a restricted number of move-size imitations. With an appendix by Peter Hegarty. \emph{Integers} \textbf{9} (2009), \#G04, 671--690.
\bibitem{Lar11} U. Larsson, Blocking Wythoff Nim, \emph{Electron. J. Combin.} \textbf{18} (2011), Paper 120.
\bibitem{Lar12} U. Larsson, A Generalized Diagonal Wythoff Nim, \emph{Integers} \textbf{12} (2012), \#G02.
\bibitem{Lar} U. Larsson, Restrictions of $m$-Wythoff Nim and $p$-complementary Beatty sequences, to appear in \emph{Games of No Chance 4}.
\bibitem{LW} U. Larsson and J. W\"astlund, Maharaja Nim: when Wythoff's Queen meets the Knight, preprint submitted to \emph{Integers}.
\bibitem{Wyt07} W. A. Wythoff, A modification of the game of Nim, \emph{Nieuw Arch. Wisk.} \textbf{7} (1907) 199--202.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 91A46; Secondary 11B75.
\noindent \emph{Keywords: }
combinatorial game, complementary sequence, golden ratio,
impartial game, integer sequence, lower asymptotic density, splitting
sequence, Wythoff Nim.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received September 18 2012;
revised versions received November 22 2013; January 6 2014; February 18 2014;
March 10 2014; April 3 2014.
Published in {\it Journal of Integer Sequences}, April 4 2014.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}