\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\usepackage{tikz}
\usepackage{enumerate}
\renewcommand{\mod}[2]{\equiv#1\textup{ (mod }#2\textup{)}}
\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
Characterizing Winning Positions in the Impartial \\
\vskip .1in
Two-Player Pebbling Game on Complete Graphs
}
\vskip 1cm
Eugene Fiorini\\
DIMACS \\
Rutgers University\\
96 Frelinghuysen Road \\
Piscataway, NJ 08854 \\
USA\\
\href{mailto:efiorini@dimacs.rutgers.edu}{\tt efiorini@dimacs.rutgers.edu} \\
\ \\
Max Lind\\
University Scholars Program \\
Pennsylvania Leadership Charter School\\
1585 Paoli Pike\\
West Chester, PA 19380 \\
USA\\
\href{mailto:mlind314@icloud.com}{\tt mlind314@icloud.com} \\
\ \\
Andrew Woldar\\
Department of Mathematics \& Statistics\\
Villanova University\\
800 Lancaster Avenue\\
Villanova, PA 19085 \\
USA\\
\href{mailto:andrew.woldar@villanova.edu}{\tt andrew.woldar@villanova.edu} \\
\ \\
Tony W. H. Wong\\
Department of Mathematics\\
Kutztown University of Pennsylvania\\
15200 Kutztown Road \\
Kutztown, PA 19530\\
USA\\
\href{mailto:wong@kutztown.edu}{\tt wong@kutztown.edu}
\end{center}
\vskip .2 in
\begin{abstract}
A pebbling game on a simple graph consists of moves that remove two
pebbles from a vertex of the graph and add one pebble to an adjacent
vertex. We consider an impartial two-player pebbling game, where the
winner of the game is the last player to make an allowable pebbling
move. In this paper, we characterize the winning positions when
this game is played on a complete graph $K_n$ with at least $n+2$
pebbles if $n\geq5$ is odd and at least $n+7$ pebbles if $n\geq6$
is even. This characterization is independent of how the pebbles are
initially distributed on the vertices and depends only on the parity of
the total number of pebbles used in the game.
\end{abstract}
\section{Introduction}
In a classical \emph{graph pebbling} game played on a simple graph (i.e., an undirected graph with no loops or multiple edges) with a target vertex, a \emph{pebbling move} consists of removing two pebbles from a vertex and adding one pebble to an adjacent vertex. The goal is to conduct a sequence of pebbling moves so that eventually the target vertex has at least one pebble. In a classical two-player graph pebbling game, considered for example by Isaak and Prudente \cite{IP}, two players alternate pebbling moves on the graph, where one player aims to move a pebble to the target while the other player aims to prevent this.
In this paper, we consider the \emph{impartial two-player pebbling game},
where the graph pebbling moves are the same, but the objective of the game
has changed: instead of identifying a target vertex, the first player
having no available pebbling move loses the game. By an \emph{impartial
game}, we refer to a combinatorial game with complete information in which
allowable moves from any position are identical for both players. One of
the classical examples of an impartial game is {\em Nim}. Readers may
refer to \textit{Winning Ways for Your Mathematical Plays}, Volume 1
\cite[p.\ 15]{bcg} for more information on impartial games.
In any impartial game, every game is either \emph{first-player winning}, denoted as an $N$-game ($N$ for the next player), or \emph{second-player winning}, denoted as a $P$-game ($P$ for the previous player). It is clear that a game is an $N$-game if and only if there exists at least one available move to a $P$-game, whereas a game is a $P$-game if and only if there are no available moves (game over) or every available move results in an $N$-game.
Let $G$ be a simple graph on $n$ vertices. Following the notation by Lind et al.\ \cite{LFW}, we define a \emph{pebble assignment} on $G$ to be an $n$-tuple $(S_G)=(a_1,a_2,\dots,a_n)$, where $a_i$ denotes the number of pebbles on vertex $v_i$ of $G$ for $1\leq i\leq n$. Our focus in this paper will be restricted to complete graphs $K_n$, thus ordering of the vertices is inconsequential. Hence, we consistently relabel the vertices such that the pebble assignment satisfies $a_1\geq a_2\geq\dotsb\geq a_n\geq0$. We observe that every pebbling game on $K_n$ is equivalent to one of this type.
Let $m=a_1+a_2+\dotsb+a_n$ denote the total number of pebbles in an assignment on $K_n$. Throughout, we call a two-player pebbling game on $K_n$ with $m$ pebbles an \emph{$(n,m)$-game} and we denote a general such game by $\Gamma_{n,m}$. When a particular assignment $(a_1,a_2,\dots,a_n)$ is specified, we indicate the corresponding pebble game by $\Gamma(a_1,a_2,\dots,a_n)$.
The main result of our paper provides conditions for winning positions as follows.
\begin{theorem}\label{thm:main}\
\begin{enumerate}[\hspace{9pt}\rm(a)]
\item\label{thm:main2} Every $(2,m)$-game $\Gamma(a_1,a_2)$ is an $N$-game if and only if $a_1\not\mod{a_2}{3}$ when $m$ is even or $a_1\mod{a_2}{3}$ when $m$ is odd.\\[-7mm]
\item\label{thm:main3}
For $m\ge 7$, $\Gamma_{3,m}$ is an N-game if and only if $m$ is odd.\\[-7mm]
\item\label{thm:main4}
For $m\ge 23$, $\Gamma_{4,m}$ is an N-game if and only if $m$ is odd.\\[-7mm]
\item\label{thm:mainodd}
For odd $n\ge 5$ and $m\ge n+2$, $\Gamma_{n,m}$ is an N-game if and only if $m$ is odd.\\[-7mm]
\item\label{thm:maineven}
For even $n\ge 6$ and $m\ge n+7$, $\Gamma_{n,m}$ is an N-game if and only if $m$ is odd.
\end{enumerate}
\end{theorem}
Theorem \ref{thm:main} is obviously formulated from the perspective of Player 1 (i.e., $N$-games). However, since every $(n,m)$-game must have an eventual winner, one need only switch the parity of $m$ to reveal the strategy from Player 2's perspective ($P$-games).
For each $n\geq3$, let $p(n)$ denote the smallest positive integer $m$ such that every $\Gamma_{n,m}$ is an $N$-game. Observe that if every $\Gamma_{n,m}$ is an $N$-game, then every $\Gamma_{n,m+1}$ is a $P$-game since all available moves result in an $N$-game. In turn, every $\Gamma_{n,m+2}$ is an $N$-game, and this pattern continues. Hence, the proof of parts (\ref{thm:main3})--(\ref{thm:maineven}) of Theorem \ref{thm:main} will rely on showing that $p(3)=7$, $p(4)=23$, $p(n)=n+2$ when $n\ge 5$ is odd, and $p(n)=n+7$ when $n\ge 6$ is even. (This sequence has been published as \seqnum{A340631} in the {\sl On-Line Encyclopedia of Integer Sequences} \cite{oeis}.)
\section{Main results}
\begin{lemma}\label{lemma:congruence}
Let $\Gamma(a_1',a_2')$ result from any sequence of allowable pebbling moves applied to $\Gamma(a_1,a_2)$. Then
$a_1'\mod{a_2'}{3}$ if and only if $a_1\mod{a_2}{3}$.
\end{lemma}
\begin{proof}
If $\Gamma(a_1',a_2')$ results from a single pebbling move, then there are three possibilities:
$\Gamma(a_1',a_2')=
\Gamma(a_2+1,a_1-2)$ (provided $a_2+1\ge a_1-2$),
$\Gamma(a_1',a_2')=
\Gamma(a_1-2,a_2+1)$ (provided $a_1-2\ge a_2+1$), and
$\Gamma(a_1',a_2')=
\Gamma(a_1+1,a_2-2)$. In these respective cases, one has $a_1'-a_2'= a_2-a_1+3$,
$a_1'-a_2'=a_1-a_2- 3$ and
$a_1'-a_2'=a_1-a_2+3$. Thus in all cases,
$a_1'\mod{a_2'}{3}$ if and only if $a_1\mod{a_2}{3}$.
An easy induction on the number of pebbling moves completes the proof.
\end{proof}
\begin{proof}[Proof of Theorem~$\ref{thm:main}${\rm(\ref{thm:main2})}]
We proceed by induction on $m$. When $m=1$, the only possibility is
$\Gamma(1,0)$ which is clearly a $P$-game. When $m=2$, the only possibilities are
$\Gamma(1,1)$ and
$\Gamma(2,0)$. Clearly $\Gamma(1,1)$ is a $P$-game. Since
$\Gamma(2,0)$ transforms to the $P$-game
$\Gamma(1,0)$ after a single move, we conclude that
$\Gamma(2,0)$ is an $N$-game. Hence, the statement of Theorem~$\ref{thm:main}$(\ref{thm:main2}) holds for $m=1$ and $m=2$.
Assume now that the statement is true for all $\elln$, then let $i$ be a positive integer such that $i\leq m-n$. It is easy to see that after any sequence of $i$ pebbling moves, the resultant $(n+2,m-i)$-game has at least $(m-n+2)-i\geq2$ zeros. Notice that in both scenarios, for every sequence of pebbling moves, there is a corresponding sequence that results in an equivalent assignment for which there are no pebbles on vertices $v_{n+1}$ and $v_{n+2}$. As a result, $\Gamma(a_1,a_2,\dotsc,a_{n+2})$ and $\Gamma(a_1,a_2,\dotsc,a_n)$ share the same winning positions.
\end{proof}
\begin{lemma}\label{lem:oddn'=n+2}
For all odd integers $n\geq7$, $\mathcal{P}_{n,n}=\{\Gamma(1^{(n)})\}$ implies $\mathcal{P}_{n+2,n+2}=
\{\Gamma(1^{(n+2)})\}$.
\end{lemma}
\begin{proof}
Note that every $(n+2,n)$-game is equivalent to an $(n,n)$-game played on a subgraph $K_n$ of $K_{n+2}$ since there are always at least two vertices with $0$ pebbles. Hence, if
$\mathcal{P}_{n,n}=\{\Gamma(1^{(n)})\}$ then $\mathcal{P}_{n+2,n}=\{\Gamma(1^{(n)},0^{(2)})\}$.
If an $(n+2,n+2)$-game has at least four zeros in its assignment, then by Lemma~\ref{lem:equiv} this game is equivalent to an $(n,n+2)$-game played on a subgraph $K_n$ of $K_{n+2}$. Since $\mathcal{P}_{n,n+2}=\emptyset$ by Lemma~\ref{lem:oddm=n+2}, any $(n+2,n+2)$-game that has at least four zeros in its assignment is an $N$-game. This implies that $\mathcal{P}_{n+2,n+2}$ can only contain $(n+2,n+2)$-games that have at most three zeros in its assignment, i.e.,
\begin{align*}
\mathcal{P}_{n+2,n+2}&\subseteq\{\Gamma(4,1^{(n-2)},0^{(3)}),\Gamma(3,2,1^{(n-3)},0^{(3)}),\Gamma(2,2,2,1^{(n-4)},0^{(3)}),\\
&\hspace{22pt}\Gamma(3,1^{(n-1)},0^{(2)}),\Gamma(2,2,1^{(n-2)},0^{(2)}),\Gamma(2,1^{(n)},0),\Gamma(1^{(n+2)})\}.
\end{align*}
Four of these games $\Gamma(4,1^{(n-2)},0^{(3)})$, $\Gamma(3,2,1^{(n-3)},0^{(3)})$, $\Gamma(2,2,2,1^{(n-4)},0^{(3)})$, and \linebreak $\Gamma(2,2,1^{(n-2)},0^{(2)})$ are predecessors of $\Gamma(2,2,1^{(n-3)},0^{(3)})$. After another pebbling move, \linebreak
$\Gamma(2,2,1^{(n-3)},0^{(3)})$ can only result in $\Gamma(3,1^{(n-3)},0^{(4)})$, $\Gamma(2,2,1^{(n-4)},0^{(4)})$, or $\Gamma(2,1^{(n-2)},0^{(3)})$. Since $\mathcal{P}_{n+2,n}=\{\Gamma(1^{(n)},0^{(2)})\}$, the last three $(n+2,n)$-games are all $N$-games. Hence, $\Gamma(2,2,1^{(n-3)},0^{(3)})$ is a $P$-game, and the four games $\Gamma(4,1^{(n-2)},0^{(3)})$, $\Gamma(3,2,1^{(n-3)},0^{(3)})$,\linebreak $\Gamma(2,2,2,1^{(n-4)},0^{(3)})$, and $\Gamma(2,2,1^{(n-2)},0^{(2)})$ are $N$-games. Furthermore, the two games $\Gamma(3,1^{(n-1)},0^{(2)})$ and $\Gamma(2,1^{(n)},0)$ are predecessors of the $P$-game $\Gamma(1^{(n+1)},0)$ after a pebbling move, so they are also $N$-games. As a result, $\mathcal{P}_{n+2,n+2}=\{\Gamma(1^{(n+2)})\}$.
\end{proof}
Now we are prepared to prove Theorem~$\ref{thm:main}$(\ref{thm:mainodd}).
\begin{proof}[Proof of Theorem~$\ref{thm:main}${\rm(\ref{thm:mainodd})}]
As previously mentioned, $p(5)=7$ has been proved by hand. For odd $n\geq7$, we induct on $n$. The case that $\mathcal{P}_{7,7}=\{\Gamma(1^{(7)})\}$ has been verified both by hand and by computer. Verification of the inductive step now follows from Lemmas~\ref{lem:oddm=n+2} and \ref{lem:oddn'=n+2}.
\end{proof}
Prefatory to proving
Theorem~$\ref{thm:main}$(\ref{thm:maineven}), we will require a couple more lemmas.
\begin{lemma}\label{lem:evenm=n+7}
For all even integers $n\geq6$, $\mathcal{P}_{n,n+1}=\{\Gamma(2,1^{(n-1)})\}$ implies that each of the following holds:
\begin{enumerate}[\hspace{9pt}\rm(i)]
\item\label{item:n+3}
$\mathcal{P}_{n,n+3}=\{\Gamma(5,1^{(n-2)},0),\Gamma(3,3,1^{(n-3)},0)\}$,
\item\label{item:n+5} $\mathcal{P}_{n,n+5}=\{\Gamma(6,1^{(n-1)})\}$, and
\item\label{item:n+7} $\mathcal{P}_{n,n+7}=\emptyset$.
\end{enumerate}
\end{lemma}
\begin{proof} \rm(\ref{item:n+3})
Let $n\geq6$ be an even integer for which $\mathcal{P}_{n,n+1}=\{\Gamma(2,1^{(n-1)})\}$. Observe that
$\mathcal{N}_{n,n+2}=\{\Gamma(4,1^{(n-2)},0),\Gamma(3,2,1^{(n-3)},0),\Gamma(3,1^{(n-1)})\}$ since
$\Gamma(4,1^{(n-2)},0)$,
$\Gamma(3,2,1^{(n-3)},0)$, and
$\Gamma(3,1^{(n-1)})$ are the only possible predecessors of
$\Gamma(2,1^{(n-1)})$.
Continuing in this manner, the only
games $\Gamma_{n,n+3}$ that can be predecessors of some $\Gamma_{n,n+2}\in
\mathcal{N}_{n,n+2}$ are the following:
\begin{equation*}\label{eqn:Nn,n+2}\begin{gathered}
\Gamma(6,1^{(n-3)},0^{(2)}),\,\Gamma(4,3,1^{(n-4)},0^{(2)}),\,\Gamma(4,2,1^{(n-3)},0),\,\Gamma(3,3,1^{(n-3)},0),\,\Gamma(3,2,1^{(n-2)}),\\
\Gamma(5,2,1^{(n-4)},0^{(2)}),\,\Gamma(5,1^{(n-2)},0),\,\Gamma(3,3,2,1^{(n-5)},0^{(2)}),\,\Gamma(3,2,2,1^{(n-4)},0),\,\Gamma(2,2,2,1^{(n-3)}).
\end{gathered}\end{equation*}
Clearly, these are the only possible candidates for inclusion in $\mathcal P_{n,n+3}$.
However,
we observe that
\begin{itemize}
\item[$\diamond$] each of
$\Gamma(6,1^{(n-3)},0^{(2)})$, $\Gamma(4,3,1^{(n-4)},0^{(2)})$, $\Gamma(4,2,1^{(n-3)},0)$, $\Gamma(3,3,2,1^{(n-5)},0^{(2)})$ and \\
$\Gamma(3,2,2,1^{(n-4)},0)$ is a predecessor of $\Gamma(4,2,1^{(n-4)},0^{(2)})$;
\item[$\diamond$] $\Gamma(3,2,1^{(n-2)})$ is a predecessor of $\Gamma(2,2,1^{(n-2)})$;
\item[$\diamond$] $\Gamma(5,2,1^{(n-4)},0^{(2)})$ is a predecessor of
$\Gamma(5,2,1^{(n-5)},0^{(3)})$;
\item[$\diamond$] $\Gamma(2,2,2,1^{(n-3)})$ is a predecessor of
$\Gamma(2,2,2,1^{(n-4)},0)$.
\end{itemize}The four indicated resultant games are $P$-games since they are not in $\mathcal{N}_{n,n+2}$. As a result, each of the eight indicated predecessor games is in $\mathcal N_{n,n+3}$.
This leaves only two of the 10 aforementioned candidates, yielding
$\mathcal{P}_{n,n+3}=\{\Gamma(5,1^{(n-2)},0),\Gamma(3,3,1^{(n-3)},0)\}$ as
desired.
\medskip
\rm(\ref{item:n+5}) We next observe that $\mathcal{N}_{n,n+4}$ is comprised of all games $\Gamma_{n,n+4}$ that can result in some $\Gamma_{n,n+3}\in\mathcal{P}_{n,n+3}$ after a single pebbling move.
It is straightforward to see that
$\mathcal{N}_{n,n+4}$ consists of the following eight games: $\Gamma(7,1^{(n-3)},0^{(2)})$, $\Gamma(5,3,1^{(n-4)},0^{(2)})$, $\Gamma(5,2,1^{(n-3)},0)$, $\Gamma(4,3,1^{(n-3)},0)$, $\Gamma(4,2,1^{(n-2)})$, $\Gamma(3,3,3,1^{(n-5)},0^{(2)})$, $\Gamma(3,3,2,1^{(n-4)},0)$ and $\Gamma(3,2,2,1^{(n-3)})$.
Below we list all games $\Gamma_{n,n+5}$ that can result in some
$\Gamma_{n,n+4}\in\mathcal{N}_{n,n+4}$ after a single pebbling move:
{\small\begin{equation*}\label{eqn:Nn,n+4}\begin{gathered}
\Gamma(9,1^{(n-4)},0^{(3)}),\,\Gamma(7,3,1^{(n-5)},0^{(3)}),\,\Gamma(7,2,1^{(n-4)},0^{(2)}),\,\Gamma(6,3,1^{(n-4)},0^{(2)}),\,\Gamma(6,2,1^{(n-3)},0),\\
\Gamma(5,5,1^{(n-5)},0^{(3)}),\,\Gamma(5,4,1^{(n-4)},0^{(2)}),\,\Gamma(5,3,3,1^{(n-6)},0^{(3)}),\,\Gamma(5,3,2,1^{(n-5)},0^{(2)}),\\
\Gamma(5,2,2,1^{(n-4)},0),\,\Gamma(4,3,3,1^{(n-5)},0^{(2)}),\,\Gamma(4,3,2,1^{(n-4)},0),\,\Gamma(7,1^{(n-2)},0),\,\Gamma(5,3,1^{(n-3)},0),\\
\Gamma(5,2,1^{(n-2)}),\,\Gamma(4,4,1^{(n-3)},0),\,\Gamma(4,2,2,1^{(n-3)}),\,\Gamma(3,3,3,1^{(n-4)},0),\,\Gamma(3,3,2,1^{(n-3)}),\,\Gamma(6,1^{(n-1)}),\\
\Gamma(4,3,1^{(n-2)}),\,\Gamma(3,3,3,3,1^{(n-7)},0^{(3)}),\,\Gamma(3,3,3,2,1^{(n-6)},0^{(2)}),\,\Gamma(3,3,2,2,1^{(n-5)},0),\\
\Gamma(3,2,2,2,1^{(n-4)}).
\end{gathered}\end{equation*}}
Note that these are the only candidates for inclusion in $\mathcal P_{n,n+5}$.
However, we see that
\begin{itemize}
\item[$\diamond$] each of $\Gamma(9,1^{(n-4)},0^{(3)})$, $\Gamma(7,3,1^{(n-5)},0^{(3)})$ and $\Gamma(7,2,1^{(n-4)},0^{(2)})$ is a predecessor of\\ $\Gamma(7,2,1^{(n-5)},0^{(3)})$;
\item[$\diamond$] each of $\Gamma(6,3,1^{(n-4)},0^{(2)})$, $\Gamma(6,2,1^{(n-3)},0)$, $\Gamma(5,4,1^{(n-4)},0^{(2)})$, $\Gamma(5,3,2,1^{(n-5)},0^{(2)})$\\ and
$\Gamma(5,2,2,1^{(n-4)},0)$ is a predecessor of $\Gamma(6,2,1^{(n-4)},0^{(2)})$;
\item[$\diamond$] each of $\Gamma(5,5,1^{(n-5)},0^{(3)})$ and $\Gamma(5,3,3,1^{(n-6)},0^{(3)})$ is a predecessor of \\ $\Gamma(5,3,2,1^{(n-6)},0^{(3)})$;
\item[$\diamond$] each of $\Gamma(4,3,3,1^{(n-5)},0^{(2)})$, $\Gamma(4,3,2,1^{(n-4)},0)$, $\Gamma(3,3,3,2,1^{(n-6)},0^{(2)})$ and \\
$\Gamma(3,3,2,2,1^{(n-5)},0)$ is a predecessor of $\Gamma(4,3,2,1^{(n-5)},0^{(2)})$;
\item[$\diamond$] each of $\Gamma(7,1^{(n-2)},0)$, $\Gamma(5,3,1^{(n-3)},0)$, and $\Gamma(4,3,1^{(n-2)})$ is a predecessor of $\Gamma(5,1^{(n-1)})$;
\item[$\diamond$] each of $\Gamma(5,2,1^{(n-2)})$, $\Gamma(3,3,3,1^{(n-4)},0)$ and $\Gamma(3,3,2,1^{(n-3)})$ is a predecessor of \\ $\Gamma(3,3,1^{(n-2)})$;
\item[$\diamond$] each of $\Gamma(4,4,1^{(n-3)},0)$, $\Gamma(4,2,2,1^{(n-3)})$ and $\Gamma(3,2,2,2,1^{(n-4)})$ is a predecessor of\\
$\Gamma(4,2,2,1^{(n-4)},0)$;
\item[$\diamond$] $\Gamma(3,3,3,3,1^{(n-7)},0^{(3)})$ is a predecessor of $\Gamma(4,3,3,1^{(n-6)},0^{(3)})$.
\end{itemize}
The eight indicated resultant games are $P$-games since they are not in $\mathcal{N}_{n,n+4}$. Hence, the 24 indicated predecessors of these games must be in $\mathcal N_{n,n+5}$. This leaves only
$\Gamma(6,1^{(n-1)})$ as the surviving candidate, i.e., $\mathcal{P}_{n,n+5}=\{\Gamma(6,1^{(n-1)})\}$.
\medskip
\rm(\ref{item:n+7}) Note that \rm(\ref{item:n+5}) implies $\mathcal{N}_{n,n+6}=\{\Gamma(8,1^{(n-2)},0),\Gamma(6,3,1^{(n-3)},0),\Gamma(5,3,1^{(n-2)})\}$, since
$\Gamma(8,1^{(n-2)},0)$,
$\Gamma(6,3,1^{(n-3)},0)$ and
$\Gamma(5,3,1^{(n-2)})$ are the only predecessors of
$\Gamma(6,1^{(n-1)})$.
A further computation now reveals that
the only possible predecessors of a game in $\mathcal{N}_{n,n+6}$ are the following:
\begin{equation*}\label{eqn:Nn,n+6}\begin{gathered}
\Gamma(10,1^{(n-3)},0^{(2)}),\,\Gamma(8,3,1^{(n-4)},0^{(2)}),\,\Gamma(8,2,1^{(n-3)},0),\,\Gamma(7,2,1^{(n-2)}),\,\Gamma(6,5,1^{(n-4)},0^{(2)}),\\
\Gamma(6,3,3,1^{(n-5)},0^{(2)}),\,\Gamma(6,3,2,1^{(n-4)},0),\,\Gamma(6,2,2,1^{(n-3)}),\,\Gamma(5,5,1^{(n-3)},0),\,\Gamma(5,3,3,1^{(n-4)},0),\\
\Gamma(5,3,2,1^{(n-3)}),\,\Gamma(7,3,1^{(n-3)},0),\,\Gamma(5,4,1^{(n-2)}),\,\Gamma(4,3,3,1^{(n-3)}).
\end{gathered}\end{equation*}
Once again, the games listed above are the only candidates for inclusion in
$\mathcal P_{n,n+7}$.
However,
\begin{itemize}
\item[$\diamond$] each of $\Gamma(10,1^{(n-3)},0^{(2)})$, $\Gamma(8,3,1^{(n-4)},0^{(2)})$ and $\Gamma(8,2,1^{(n-3)},0)$ is a predecessor of
$\Gamma(8,2,1^{(n-4)},0^{(2)})$;
\item[$\diamond$] each of $\Gamma(7,2,1^{(n-2)})$ and $\Gamma(6,2,2,1^{(n-3)})$ is a predecessor of
$\Gamma(7,2,1^{(n-3)},0)$;
\item[$\diamond$] each of $\Gamma(6,5,1^{(n-4)},0^{(2)})$, $\Gamma(6,3,3,1^{(n-5)},0^{(2)})$ and $\Gamma(6,3,2,1^{(n-4)},0)$ is a predecessor of $\Gamma(6,3,2,1^{(n-5)},0^{(2)})$;
\item[$\diamond$] each of $\Gamma(5,5,1^{(n-3)},0)$, $\Gamma(5,3,3,1^{(n-4)},0)$, $\Gamma(5,3,2,1^{(n-3)})$ and $\Gamma(7,3,1^{(n-3)},0)$ is a predecessor of $\Gamma(5,3,2,1^{(n-4)},0)$;
\item[$\diamond$] each of $\Gamma(5,4,1^{(n-2)})$ and $\Gamma(4,3,3,1^{(n-3)})$ is a predecessor of $\Gamma(4,3,2,1^{(n-3)})$.
\end{itemize}
The five indicated resultant games are $P$-games since they are not in $\mathcal{N}_{n,n+6}$. Thus the 14 indicated predecessors are all $N$-games, which means there are no surviving candidates for inclusion in $\mathcal{P}_{n,n+7}$. We conclude that
$\mathcal{P}_{n,n+7}=\emptyset$ as claimed.
\end{proof}
\begin{lemma}\label{lem:evenn'=n+2}
For all even integers $n\geq6$, $\mathcal{P}_{n,n+1}=\{\Gamma(2,1^{(n-1)})\}$ implies $\mathcal{P}_{n+2,n+3}=\{\Gamma(2,1^{(n+1)})\}$.
\end{lemma}
\begin{proof}
If $\Gamma_{n+2,n+1}$ has at least three zeros in its assignment, then by Lemma~\ref{lem:equiv}, this $\Gamma_{n+2,n+1}$ shares the same winning positions as a $\Gamma_{n,n+1}$ with at least one zero. Since $\mathcal{P}_{n,n+1}=\{\Gamma(2,1^{(n-1)})\}$, it follows that any game $\Gamma_{n+2,n+1}$ with at least three zeros in its assignment is an $N$-game.
In other words,
$\Gamma_{n+2,n+1}\in \mathcal{P}_{n+2,n+1}$ only if $\Gamma_{n+2,n+1}$ has at most two zeros in its assignment, i.e.,
$$\mathcal{P}_{n+2,n+1}\subseteq\{\Gamma(2,1^{(n-1)},0^{(2)}),\Gamma(1^{(n+1)},0)\}.$$
However,
$\Gamma(2,1^{(n-1)},0^{(2)})$ is an $N$-game since it is a predecessor of the $P$-game $\Gamma(1^{(n)},0^{(2)})$, thus $\mathcal{P}_{n+2,n+1}=\{\Gamma(1^{(n+1)},0)\}$.
Moreover, $\mathcal{N}_{n+2,n+2}=\{\Gamma(3,1^{(n-1)},0^{(2)}),\Gamma(2,1^{(n)},0)\}$ since
$\Gamma(3,1^{(n-1)},0^{(2)})$ and $\Gamma(2,1^{(n)},0)$ are the only
predecessors of
$\Gamma(1^{(n+1)},0)$.
We are up to the point of determining
$\mathcal P_{n+2,n+3}$. Here, the candidates are precisely those $\Gamma_{n+2,n+3}$ that are predecessors of a game from $\mathcal{N}_{n+2,n+2}$. We list all such candidates below:
\begin{equation*}\label{eqn:Nn+2,n+2}\begin{gathered}
\Gamma(5,1^{(n-2)},0^{(3)}),\,\Gamma(3,3,1^{(n-3)},0^{(3)}),\,\Gamma(3,2,1^{(n-2)},0^{(2)}),\,\Gamma(2,2,1^{(n-1)},0),\,\Gamma(4,1^{(n-1)},0^{(2)}),\\
\Gamma(3,1^{(n)},0),\, \Gamma(2,1^{(n+1)}).
\end{gathered}\end{equation*}
However, we observe that
\begin{itemize}
\item[$\diamond$] each of $\Gamma(5,1^{(n-2)},0^{(3)})$, $\Gamma(3,3,1^{(n-3)},0^{(3)})$ and $\Gamma(3,2,1^{(n-2)},0^{(2)})$ is a predecessor of $\Gamma(3,2,1^{(n-3)},0^{(3)})$;
\item[$\diamond$] each of $\Gamma(2,2,1^{(n-1)},0)$ and $\Gamma(4,1^{(n-1)},0^{(2)})$ is a predecessor of $\Gamma(2,2,1^{(n-2)},0^{(2)})$;
\item[$\diamond$] $\Gamma(3,1^{(n)},0)$ is a predecessor of $\Gamma(1^{(n+2)})$.
\end{itemize}
The three indicated resultant games are $P$-games since they are not in $\mathcal{N}_{n+2,n+2}$. It follows that the six indicated predecessors are all $N$-games. As a result,
$\Gamma(2,1^{(n+1)})$ is the only surviving candidate, whence $\mathcal{P}_{n+2,n+3}=\{\Gamma(2,1^{(n+1)})\}$ as desired.
\end{proof}
We are now prepared to prove Theorem~$\ref{thm:main}$(\ref{thm:maineven}).
\begin{proof}[Proof of Theorem~$\ref{thm:main}${\rm(\ref{thm:maineven})}]
We leave verification that $\mathcal{P}_{6,7}=\{\Gamma(2,1^{(5)})\}$ as an exercise for the reader. By Lemma \ref{lem:evenn'=n+2}, we have $\mathcal{P}_{n,n+1}=\{\Gamma(2,1^{(n-1)})\}$ for all even $n\ge 6$. It now follows from Lemma \ref{lem:evenm=n+7} that $\mathcal{P}_{n,n+7}=\emptyset$ for all even $n\ge 6$. Thus, every $\Gamma_{n,n+7}$ is an $N$-game, from which it follows that every $\Gamma_{n,m}$ is an $N$-game if and only if $m$ is odd, $m\ge n+7$.
\end{proof}
\appendix
\section{Appendix: Mathematica Program}\label{Appendix}
\begin{verbatim}
(*Given n and m, list all possible assignments.*)
alltuples[n_, m_] := IntegerPartitions[m + n, {n}] - 1;
(*Given an assignment, list all resultant assignments after one pebbling
move; only work for n>=3.*)
pebblemoves[config_] :=
Block[{n, temp}, n = Length[config];
temp = Table[config, {i, n (n - 1)}] +
Permutations[Join[{-2, 1}, Table[0, {i, n - 2}]]];
temp = Select[temp, Min[#] >= 0 &];
temp = ReverseSort[DeleteDuplicates[ReverseSort /@ temp]]];
(*Given n and m, list all assignments that are P-games.*)
Plist = {};
plist[n_, m_] :=
Block[{index, tuples},
While[Length[Plist] < n, index = Length[Plist];
AppendTo[Plist, {{Join[{1}, Table[0, {i, index}]]}}]];
Do[AppendTo[Plist[[n]], {}]; tuples = alltuples[n, i];
Do[If[Not[
IntersectingQ[pebblemoves[tuples[[j]]], Plist[[n, i - 1]]]],
AppendTo[Plist[[n, i]], tuples[[j]]]], {j, Length[tuples]}],
{i, Length[Plist[[n]]] + 1, m}]; Plist[[n, m]]];
(*Given n, print out the minimum m such that there are no P-games with m
pebbles*)
Do[m = 1; While[plist[n, m] != {}, m++];
Print["n=", n, " m=", m], {n, 3, 20}]
\end{verbatim}
\begin{thebibliography}{9}
\bibitem{bcg}
E.~R.~Berlekamp, J.~H.~Conway, and R.~K.~Guy, \textit{Winning Ways for
Your Mathematical Plays}, Vol.~1, CRC Press, 2001.
\bibitem{LFW}
M.~Lind, E.~Fiorini, and A.~Woldar, On properties of pebble assignment graphs, submitted, 2020.
\bibitem{IP}
G.~Isaak and M.~Prudente, Two-player pebbling on diameter 2 graphs, \emph{Int.\ J. Game Theory} (2021), \url{https://doi.org/10.1007/s00182-021-00766-0}.
\bibitem{oeis}
N.~J.~A.~Sloane et al., \textit{The On-Line Encyclopedia of Integer Sequences}, \url{https://oeis.org}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary 91A46; Secondary 91A43, 91A05.
\noindent \emph{Keywords:} pebbling game, impartial game, pebble assignment, $N$-game, $P$-game.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence
\seqnum{A340631}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received March 25 2021;
revised version received May 4 2021.
Published in {\it Journal of Integer Sequences},
May 18 2021.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}