<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath,amsthm,amsfonts,amssymb,amscd}
\usepackage{tikz}
\usepackage{enumerate}
\usepackage{multirow}
\usepackage{diagbox}
\usepackage{hhline}
\usepackage{graphicx}
\usepackage{mathtools}

\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}

\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}
\newtheorem{identity}[theorem]{Identity}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\PP}{\mathcal{P}}
\newcommand{\NN}{\mathcal{N}}

\renewcommand{\mod}[2]{\equiv#1\textup{ (mod }#2\textup{)}}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\newcommand{\bmbar}[1]{\mbox{\boldmath $\overline #1$}}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\Large\bf Generalized Impartial Two-player \\
\vskip .1in
Pebbling Games on $K_3$ and $C_4$}
\end{center}

\vskip .1in

\begin{minipage}{3in}
\begin{center}
Kayla Barker\\
Mathematics Program\\
Stockton University\\
101 Vera King Ferris Dr\\
Galloway, NJ 08205\\
USA\\
\href{mailto:kaylaabarker5@gmail.com}{\texttt{kaylaabarker5@gmail.com}} \\
\end{center}
\end{minipage}
\ \quad \ 
\begin{minipage}{3in}
\begin{center}
Mia DeStefano\\
Dept.\ of Mathematics and Statistics\\
Vassar College\\
124 Raymond Ave\\
Poughkeepsie, NY 12604\\
USA\\
\href{mailto:mdestefano@vassar.edu}{\texttt{mdestefano@vassar.edu}} \\
\end{center}
\end{minipage}
\vskip .15in
\begin{minipage}{3in}
\begin{center}
Eugene Fiorini\\
DIMACS\\
Rutgers University\\ 
96 Frelinghuysen Road\\
Piscataway, NJ 08854\\
USA\\
\href{mailto:efiorini@dimacs.rutgers.edu}{\texttt{efiorini@dimacs.rutgers.edu}}\\
\end{center}
\end{minipage}
\ \quad \ 
\begin{minipage}{3in}
\begin{center}
Michael Gohn\\ 
Dept.\ of Mathematics and Computer Sci.\\
DeSales University\\
2755 Station Avenue\\
Center Valley, PA 18034\\ 
USA\\
\href{mailto:mg7785@desales.edu}{\texttt{mg7785@desales.edu}}\\
\end{center}
\end{minipage}
\vskip .15in
\begin{minipage}{3in}
\begin{center}
Joe Miller\\ 
Department of Mathematics\\
Iowa State University\\ 
411 Morrill Rd\\
Ames, IA 50011\\ 
USA\\
\href{mailto:jmiller0@iastate.edu}{\texttt{jmiller0@iastate.edu}} \\
\end{center}
\end{minipage}
\ \quad \ 
\begin{minipage}{3in}
\begin{center}
Jacob Roeder\\ 
Dept.\ of Mathematics and Physics\\
Trine University\\
1 University Ave\\
Angola, IN 46703\\ 
USA\\
\href{mailto:jwroeder19@my.trine.edu}{\texttt{jwroeder19@my.trine.edu}} \\
\end{center}
\end{minipage}

\begin{center}
Tony W. H. Wong\\
Department of Mathematics\\
Kutztown University of Pennsylvania\\
15200 Kutztown Road\\ 
Kutztown, PA 19530\\ 
USA\\
\href{mailto:wong@kutztown.edu}{\texttt{wong@kutztown.edu}}
\end{center}

\newpage

\begin{abstract}
In a variation on the pebbling game played on a simple graph, a $(k+1:k)$-pebbling move comprises removing $k+1$ pebbles from a vertex and adding $k$ pebbles to an adjacent vertex. We consider an impartial two-player game, where the winner of the game is the last player to make an allowable $(k+1:k)$-pebbling move. In this paper, we characterize the winning positions when the $(k+1:k)$-pebbling game is played on the complete graph $K_3$ and when the $(2:1)$-pebbling game is played on the cycle $C_4$.
\end{abstract}

\section{Introduction}\label{sec:intro}

Given a simple graph $G$ on vertices $v_1,v_2,\dotsc,v_n$, every vertex $v_i$ is assigned with a number of pebbles, specified by a nonnegative integer $a_i$ for each $1\leq i\leq n$. Fiorini et al.\ \cite{flww} describe an \emph{impartial two-player $(2:1)$-pebbling game}, denoted by $\Gamma^{(2:1)}_G(a_1,a_2,\dotsc,a_n)$, where players $A$ and $B$ take turns (player $A$ taking the first turn) to make a \emph{$(2:1)$-pebbling move}, which consists of removing two pebbles from a vertex and adding one pebble to an adjacent vertex. The first player having no available pebbling move loses the game. In this paper, we generalize this concept and consider a \emph{impartial two-player $(k+1:k)$-pebbling game} $\Gamma^{(k+1:k)}_G(a_1,a_2,\dotsc,a_n)$ for some positive integer $k$, where a $(k+1:k)$-pebbling move consists of removing $k+1$ pebbles from a vertex and adding $k$ pebbles to an adjacent vertex.

In general, a two-player impartial game refers to a game with perfect information, no probabilistic moves, and finite number of moves before the game ends. Furthermore, at any point of the game, both players have exactly the same set of moves. Under the normal play condition where the first player without a legal move loses the game, the Sprague-Grundy theorem implies that in every impartial game, either the first player has a winning strategy, denoted as an $N$-game ($N$ for the next player), or the second player has a winning strategy, 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 that results in a $P$-game, whereas a game is a $P$-game if and only if there are no available moves, i.e., a \emph{terminating game}, or every available move results in an $N$-game. Interested readers may refer to Berlekamp, Conway, and Guy \cite{bcg} for more information on two-player impartial games.

Let $\mathcal{G}_{G,m}^{(k+1:k)}$ be the collection of all impartial two-player $(k+1:k)$-pebbling games with $m$ initial pebbles in total on the underlying graph $G$. Due to the observation given in the previous paragraph, $\mathcal{G}_{G,m}^{(k+1:k)}$ can be partitioned into  $\mathcal{P}_{G,m}^{(k+1:k)}$ and $\mathcal{N}_{G,m}^{(k+1:k)}$, the sets of all $P$-games and $N$-games in $\mathcal{G}_{G,m}^{(k+1:k)}$, respectively. Furthermore, if there exists a positive integer $m$ such that $\mathcal{G}_{G,m}^{(k+1:k)}=\mathcal{N}_{G,m}^{(k+1:k)}$, then $\mathcal{G}_{G,m+2r}^{(k+1:k)}=\mathcal{N}_{G,m+2r}^{(k+1:k)}$ and $\mathcal{G}_{G,m+2r+1}^{(k+1:k)}=\mathcal{P}_{G,m+2r+1}^{(k+1:k)}$ for all nonnegative integers $r$. When such an $m$ exists, this suggests there is a minimum $m$ value where $\mathcal{G}_{G,m}^{(k+1:k)}=\mathcal{N}_{G,m}^{(k+1:k)}$, which we denote by $m^{(k+1:k)}(G)$. Fiorini et al.\ \cite{flww} established the 
following result when $k=1$ and $G=K_n$.
\newpage

\begin{theorem}\label{thm:old}\  
\begin{enumerate}[\hspace{9pt}\rm(a)]
\item\label{thm:oldK2}
If $m$ is even, then $\mathcal{N}^{(2:1)}_{K_2,m}=\{\Gamma^{(2:1)}_{K_2}(a_1,a_2):a_1+a_2=m\text{ and }a_1\not\mod{a_2}{3}\}$; if $m$ is odd, then $\mathcal{N}^{(2:1)}_{K_2,m}=\{\Gamma^{(2:1)}_{K_2}(a_1,a_2):a_1+a_2=m\text{ and }a_1\mod{a_2}{3}\}$. Hence, $m^{(2:1)}(K_2)$ does not exist.
\item\label{thm:oldK3} $m^{(2:1)}(K_3)=7$.
\item\label{thm:oldK4} $m^{(2:1)}(K_4)=23$.
\item\label{thm:oldK5} For all odd integers $n\geq5$, we have $m^{(2:1)}(K_n)=n+2$.
\item\label{thm:oldK6} For all even integers $n\geq6$, we have $m^{(2:1)}(K_n)=n+7$.
\end{enumerate}
\end{theorem}

In this paper, we expand our investigation on $m^{(k+1:k)}(K_n)$ when $k&gt;1$. Through computation using Mathematica (see Appendix~\ref{Appendix} for the code), we obtain the values of $m^{(k+1:k)}(K_n)$ for some small $k$ and $n$, excerpted in the table below.

\begin{table}[H] \centering
\begin{tabular}{ |p{1cm}||p{1cm}|p{1cm}|p{1cm}|p{1cm}|p{1cm}|p{1cm}|  }

 \hline
 \backslashbox{$n$}{$k$} &amp; $1$&amp; $2$ &amp; $3$ &amp; $4$ &amp; $5$ &amp; $6$\\
 \hhline{|=||=|=|=|=|=|=|}
 $3$ &amp; $7$ &amp; $13$ &amp; $19$ &amp; $25$ &amp; $31$ &amp; $37$\\
 \hline
 $4$ &amp; $23$ &amp; $21$ &amp; &amp; $35$ &amp; &amp; $49$\\
 \hline
 $5$ &amp; $7$ &amp; $15$ &amp; $21$ &amp; $27$ &amp; $33$ &amp; $39$\\
 \hline
 $6$ &amp; $13$ &amp; $21$ &amp; $35$ &amp; $37$ &amp; $59$ &amp; $53$\\
 \hline
 $7$ &amp; $9$ &amp; $17$ &amp; $25$ &amp; $33$ &amp; $41$ &amp; $51$\\
 \hline
 $8$ &amp; $15$ &amp; $25$ &amp; $41$ &amp; $45$ &amp; $61$ &amp; $65$\\
 \hline
 $9$ &amp; $11$ &amp; $21$ &amp; $31$ &amp; $41$ &amp; $51$ &amp; $61$\\
 \hline
 $10$ &amp; $17$ &amp; $29$ &amp; $45$ &amp; $53$ &amp; $71$ &amp; $77$\\
 \hline
\end{tabular}
\caption{Values of $m^{(k+1:k)}(K_n)$ for $1\leq k\leq 6$ and $3\leq n\leq10$.}
\label{tbl:m(Kn)}
\end{table}

The first column of Table~\ref{tbl:m(Kn)} corresponds to the result given in Theorem~\ref{thm:old}. This sequence appears in the On-Line Encyclopedia of Integer Sequences (OEIS) as \seqnum{A340631} \cite{oeis}. On the other hand, the sequence given by the first row appears in the OEIS as \seqnum{A016921} \cite{oeis}. This sequence is a result of the following theorem, which will be proved in Section~\ref{sec:K3}.

\begin{theorem}\label{thm:K3}
For all positive integers $k$, we have $m^{(k+1:k)}(K_3)=6k+1$.
\end{theorem}

The empty cells in the row corresponding to $n=4$ are due to the following conjecture, suggested by our computational data.
 
\begin{conjecture}\label{conj:K4}
For all odd integers $k\geq3$, the value $m^{(k+1:k)}(K_4)$ does not exist.
\end{conjecture}

Since $m^{(k+1:k)}(K_4)$ is conjectured to be nonexistent for odd $k\geq3$, only the data corresponding to $n\geq5$ in Table~\ref{tbl:m(Kn)} appears in the OEIS (see \seqnum{A346197} and \seqnum{A347637} \cite{oeis}).

We also study $m^{(k+1:k)}(G)$ when $G$ is not a complete graph. In particular, we prove in Section~\ref{sec:C4} that $m^{(2:1)}(C_4)$ does not exist. In fact, we fully determine how $\mathcal{G}_{C_4,m}^{(2:1)}$ is partitioned into $\mathcal{P}_{C_4,m}^{(2:1)}$ and $\mathcal{N}_{C_4,m}^{(2:1)}$ for all positive integers $m$.

Before we proceed, we give several definitions that are useful for our discussions. After a player makes a $(k+1:k)$-pebbling move from vertex $v_i$ to vertex $v_j$, if their opponent immediately makes a move from $v_j$ to $v_i$, then we call this move an \emph{echo pebbling move}. Next, for all $\gamma=\Gamma^{(k+1:k)}_G(a_1,a_2,\dotsc,a_n)$, we let $|\gamma|=a_1+a_2+\dotsb+a_n$ denote the total number of pebbles in this game. Furthermore, the game $\gamma_{i+1}$ is called a \emph{successor} of $\gamma_i=\Gamma^{(k+1:k)}_G(a_1,a_2,\dotsc,a_n)$ if $\gamma_{i+1}$ is a resultant game by performing one $(k+1:k)$-pebbling move on $\gamma_i$, and $\gamma_i$ is called a \emph{predecessor} of $\gamma_{i+1}$.

\section{The investigation on $m^{(k+1:k)}(K_3)$}\label{sec:K3}

In this section, since the focus is $G=K_3$ with $(k+1:k)$-pebbling moves, we will abbreviate the notation $\mathcal{G}_{K_3,m}^{(k+1:k)}$, $\mathcal{P}_{K_3,m}^{(k+1:k)}$, $\mathcal{N}_{K_3,m}^{(k+1:k)}$, and $\Gamma_{K_3}^{(k+1:k)}(a_1,a_2,a_3)$ as $\mathcal{G}_m$, $\mathcal{P}_m$, $\mathcal{N}_m$, and $\Gamma(a_1,a_2,a_3)$, respectively. Furthermore, due to the symmetry of $K_3$, the game $\Gamma(a_1,a_2,a_3)$ is equivalent to games given by every permutation of $a_1$, $a_2$, and $a_3$. We denote this equivalence class of games as $\Gamma\{a_1,a_2,a_3\}$. For convenience, we always assume $a_1\geq a_2\geq a_3$.

The technique we utilize to prove Theorem~\ref{thm:K3} is to show that $\PP_{3,6k-1}=\Gamma\{4k+1,k-1,k-1\}$. We demonstrate this via a sequence of lemmas. The first three lemmas prove that every game in $\Gamma\{4k+1,k-1,k-1\}$ is a $P$-game.

\begin{lemma}\label{lem: (2k+3,0,0) P-game}
Every game in $\Gamma\{2k+3,0,0\}$ is a $P$-game.
\end{lemma}
\begin{proof}
Consider $\gamma_0\in\Gamma\{2k+3,0,0\}$. Every successor $\gamma_1$ of $\gamma_0$ is in $\Gamma\{k+2,k,0\}$, and player $B$ can make one pebbling move on $\gamma_1$ to obtain $\gamma_2\in\Gamma\{k,k,1\}$. Clearly $\gamma_2$ is a $P$-game, so $\gamma_0$ is also a $P$-game.
\end{proof}

\begin{lemma}\label{lem: general (2k-1,k,k) P-game}
Let $0\leq\ell\leq k-1$ and $\ell_1\leq\ell_2$ be nonnegative integers such that $\ell_1 + \ell_2 = \ell$. Then every game in  $\Gamma\{2k-1-\ell,k-\ell_1,k-\ell_2\}$ is a $P$-game.
\end{lemma}
\begin{proof}
Consider $\gamma_0\in\Gamma\{2k-1,k,k\}$. Every successor of $\gamma_0$ is in $\Gamma\{2k,k,k-2\}$, and the subsequent echo pebbling move by player $B$ leads to $\gamma_2\in\Gamma\{2k-2,k,k-1\}$. If player $B$ repeats the strategy of echoing player $A$'s every move, then for every $0\leq\ell\leq k-1$, we have $\gamma_{2\ell}\in\Gamma\{2k-1-\ell, k-\ell_1,k-\ell_2\}$, where $\ell_1\leq\ell_2$ and $\ell_1+\ell_2=\ell$. Note that all vertices in $\gamma_{2(k-1)}$ have at most $k$ pebbles, which implies that $\gamma_{2(k-1)}$ is a $P$-game. Since player $B$ has a strategy to bring every $\gamma_{2\ell}\in\Gamma\{2k-1-\ell, k-\ell_1,k-\ell_2\}$ to a $P$-game, the game $\gamma_{2\ell}$ is also a $P$-game. 
\end{proof}

\begin{lemma}\label{lem: (4k+1,k-1,k-1) P-game}
Every game in $\Gamma\{4k+1,k-1,k-1\}$ is a $P$-game.
\end{lemma}
\begin{proof}
Consider $\gamma_0\in\Gamma\{4k+1,k-1,k-1\}$. Regardless of the moves by player $A$, player $B$ is going to perform the echo pebbling move every time when possible. The only scenario where player $B$ does not have an echo pebbling move is when player $B$ obtains a descendant $\gamma_{2k-2+2\ell}\in\Gamma\{3k+2-\ell,k-1-\ell,0\}$ for some $0\leq\ell\leq k-1$ and player $A$ makes one pebbling move to obtain $\gamma_{2k-1+2\ell}\in\Gamma\{2k+1-\ell,k,k-1-\ell\}$. In this situation, player $B$ can make one pebbling move to obtain $\gamma_{2k+2\ell}\in\Gamma\{2k-1-\ell,k,k-\ell\}$, which is a $P$-game by Lemma~\ref{lem: general (2k-1,k,k) P-game}.
\end{proof}

The next two lemmas together show that $\gamma\in\mathcal{G}_m$ is a $P$ game if $m\leq6k$ is even and no vertex contains more than $m/2$ pebbles.

\begin{lemma}\label{lem: 3k-l pattern}
Consider $\gamma_{2\ell}\in\Gamma\{a_1,a_2,a_3\}$, where $|\gamma_{2\ell}|=a_1+a_2+a_3=6k-2\ell$ for some $0\leq\ell\leq2k-1$ and $k+1\leq a_1\leq3k-\ell$. Then regardless of the move by player $A$, player $B$ can obtain $\gamma_{2\ell+2}\in\Gamma\{a_1'',a_2'',a_3''\}$, where $a_1''\leq3k-\ell-1$.
\end{lemma}
\begin{proof}
If $a_3=0$, then $\gamma_{2\ell}\in\Gamma\{3k-\ell,3k-\ell,0\}$. In this case, the game $\gamma_{2\ell+1}$ is in $\Gamma\{4k-\ell,2k-\ell-1,0\}$ or
$$\begin{cases}
\Gamma\{3k-\ell,2k-\ell-1,k\},&amp;\text{if }0\leq\ell\leq k-1;\\
\Gamma\{3k-\ell,k,2k-\ell-1\},&amp;\text{if }k\leq\ell\leq2k-1,
\end{cases}$$
and player $B$ can make one pebbling move to obtain $\gamma_{2\ell+2}$ in
$$\begin{cases}
\Gamma\{3k-\ell-1,2k-\ell-1,k\},&amp;\text{if }0\leq\ell\leq k-1;\\
\Gamma\{3k-\ell-1,k,2k-\ell-1\},&amp;\text{if }k\leq\ell\leq2k-1,
\end{cases}$$
thus establishing our assertion.

Now suppose $a_3\geq1$. If $a_1\leq3k-\ell-1$, then regardless of the move by player $A$, player $B$ is going to perform an echo pebbling move to obtain $\gamma_{2\ell+2}\in\Gamma\{a_1'',a_2'',a_3''\}$. Note that the resultant number of pebbles at every vertex does not increase after these two moves. Hence, we have $a_1''\leq a_1\leq3k-\ell-1$.

It remains to consider the case where $a_1=3k-\ell$ and $a_2\leq3k-\ell-1$. If player $A$ makes one pebbling move that involves the vertex with $3k-\ell$ pebbles, then player $B$ is going to perform an echo pebbling move to obtain $\gamma_{2\ell+2}$. Otherwise, player $A$ obtains $\gamma_{2\ell+1}\in\Gamma\{3k-\ell,a_2',a_3'\}$ with $a_2'+a_3'=3k-\ell-1$. Since one of the vertices with $a_2$ and $a_3$ pebbles receives $k$ pebbles in this pebbling move by player $A$, we have $a_2'\geq k$. This implies that $a_3'\leq2k-\ell-1$. Hence, player $B$ can make one pebbling move to obtain $\gamma_{2\ell+2}\in\Gamma\{a_1'',a_2'',a_3''\}$ such that $\{a_1'',a_2'',a_3''\}=\{2k-\ell-1,a_2',a_3'+k\}$. In both scenarios, the resultant $\gamma_{2\ell+2}$ satisfies the desired condition.
\end{proof}

\begin{lemma}\label{lem: 3k-l P-game}
Consider $\gamma_{2\ell}\in\Gamma\{a_1,a_2,a_3\}$, where $|\gamma_{2\ell}|=6k-2\ell$ for some $0\leq\ell\leq2k-1$ and $a_1\leq3k-\ell$. Then $\gamma_{2\ell}$ is a $P$-game.
\end{lemma}
\begin{proof}
Suppose player $B$ inductively applies the strategy described in Lemma~\ref{lem: 3k-l pattern}. Under this strategy, if player $A$ obtains $\gamma_{2\ell+1}$ for some $0\leq\ell\leq2k-1$, then player $B$ always has an available pebbling move to obtain $\gamma_{2\ell+2}$. Hence, player $B$ can ensure that the game either terminates at $\gamma_{2\ell}$ for some $0\leq\ell\leq2k-1$ or does not terminate at $\gamma_{4k-2}$. If $\gamma_{4k-2}$ is not a terminating game, then according to Lemma~\ref{lem: 3k-l pattern}, player $B$ can obtain $\gamma_{4k}\in\Gamma\{a_1^*,a_2^*,a_3^*\}$ with $a_1^*\leq3k-(2k-1)-1=k$. This implies that $\gamma_{4k}$ is a terminating game. Therefore, player $B$ has a winning strategy, meaning that $\gamma_{2\ell}$ is a $P$-game.
\end{proof}

The remaining preliminary results before the proof of Theorem~\ref{thm:K3} show that every $\gamma\in\mathcal{G}_{6k-1}\setminus\Gamma\{4k+1,k-1,k-1\}$ is an $N$-game.

\begin{lemma}\label{lem: N-game if pebbles&lt;4k-l+1 K3}
Consider $\gamma_{2\ell-1}\in\Gamma\{a_1,a_2,a_3\}$, where $|\gamma_{2\ell-1}|=6k-2\ell+1$ for some $1\leq\ell\leq2k-1$, $a_1\leq4k-\ell+1$, and $a_3\leq2k-\ell$. Then $\gamma_{2\ell-1}$ is an $N$-game.   
\end{lemma}
\begin{proof}
Note that $a_2\leq\lfloor(6k-2\ell+1)/2\rfloor=3k-\ell$. If player $A$ makes a pebbling move from the vertex with $a_1$ pebbles to the vertex with $a_3$ pebbles, then $\gamma_{2\ell}$ is in $\Gamma\{a_1',a_2',a_3'\}$ such that $\{a_1',a_2',a_3'\}=\{a_1-k-1,a_2,a_3+k\}$, where $a_1-k-1\leq4k-\ell+1-(k+1)=3k-\ell$ and $a_3+k\leq2k-\ell+k=3k-\ell$. By Lemma~\ref{lem: 3k-l P-game}, the game $\gamma_{2\ell}$ is a $P$-game, so $\gamma_{2\ell-1}$ is an $N$-game.
\end{proof}

\begin{corollary}\label{cor: K3 N-games pt 1}
Consider $\gamma_1\in\Gamma\{a_1,a_2,a_3\}$, where $|\gamma_1|=6k-1$ and $a_1\leq4k$. Then $\gamma_1$ is an $N$-game.
\end{corollary}
\begin{proof}
Note that $a_3\leq\lfloor(6k-1)/3\rfloor=2k-1$. Hence, the conditions in Lemma~\ref{lem: N-game if pebbles&lt;4k-l+1 K3} are satisfied with $\ell=1$.
\end{proof}

\begin{lemma}\label{lem: k,0 N-game}
Consider $\gamma_{2\ell-1}\in\Gamma\{a_1,a_2,0\}$, where $|\gamma_{2\ell-1}|=6k-2\ell+1$ for some $1\leq\ell\leq k-1$ and $a_2\leq k$. Then $\gamma_{2\ell-1}$ is an $N$-game.
\end{lemma}
\begin{proof}
Player $A$ can make a pebbling move to obtain $\gamma_{2\ell}\in\Gamma\{a_1-k-1,k,a_2\}$, and player $B$ can only obtain $\gamma_{2\ell+1}$ in $\Gamma\{a_1-2k-2,2k,a_2\}$ or $\Gamma\{a_1-2k-2,a_2+k,k\}$. Since $$a_1-2k-2\leq(6k-2\ell+1)-2k-2=4k-2\ell-1\leq4k-(\ell+1)+1$$ and $a_2\leq k\leq 2k-(\ell+1)$, Lemma~\ref{lem: N-game if pebbles&lt;4k-l+1 K3} applies and $\gamma_{2\ell+1}$ is an $N$-game, which implies our assertion.
\end{proof}

\begin{lemma}\label{lem: K3 N-games pt 2}
Consider $\gamma_1\in\Gamma\{a_1,a_2,a_3\}$, where $|\gamma_1|=6k-1$ and $a_1\geq4k+1$. If $\gamma_1\not\in\Gamma\{4k+1,k-1,k-1\}$, then $\gamma_1$ is an $N$-game.
\end{lemma}

\begin{proof}
Without loss of generality, let $\gamma_1=\Gamma(a_1,a_2,a_3)$. Note that
$$a_3\leq((6k-1)-(4k+1))/2=k-1.$$ However, if $a_3=k-1$, then $(a_1,a_2,a_3)=(4k+1,k-1,k-1)$, which is a contradiction. Hence, we have $a_3\leq k-2$.

Suppose that $a_2\leq k$. If $a_3=0$, then $\gamma_1$ is an $N$-game by Lemma~\ref{lem: k,0 N-game}, so we may assume that $a_3\geq1$. To start the game, player $A$ can make a pebbling move to obtain $\gamma_2=\Gamma(a_1-k-1,a_2,a_3+k)$. Then player $B$ can only make a pebbling move from either $v_1$ or $v_3$. Let $\ell$ be the maximum nonnegative integer such that for each positive integer $\widetilde{\ell}\leq\ell$, player $B$ makes a pebbling move from $v_3$ at the game $\gamma_{2\widetilde{\ell}}$ to obtain $\gamma_{2\widetilde{\ell}+1}$. Note that if $\ell=0$, then player $B$ must have made a pebbling move from $v_1$ at the game $\gamma_2$ to obtain $\gamma_3$. After each pebbling move by player $B$ to obtain $\gamma_{2\widetilde{\ell}+1}$, player $A$ can always perform an echo pebbling move to obtain $\gamma_{2\widetilde{\ell}+2}$ since $a_1-k-1&gt; a_2\geq a_3$. With this strategy, player $A$ can obtain $\gamma_{2\ell+2}=\Gamma(a_1-k-1-\ell_1,a_2-\ell_2,a_3+k-\ell)$ for some nonnegative integers $\ell_1$ and $\ell_2$ such that $\ell_1+\ell_2=\ell$. Note that $a_3+k-\ell\geq k$, so $\ell\leq a_3$. Now by the definition of $\ell$, the next pebbling move by player $B$ is from $v_1$, so $\gamma_{2\ell+3}$ is either $\Gamma(a_1-2k-2-\ell_1,a_2+k-\ell_2,a_3+k-\ell)$ or $\Gamma(a_1-2k-2-\ell_1,a_2-\ell_2,a_3+2k-\ell)$. Since
\begin{itemize}
\item $a_1-2k-2-\ell_1=(6k-1-a_2-a_3)-2k-2-\ell_1\leq4k-a_3-3\leq4k-\ell-3&lt;4k-(\ell+2)+1$,
\item $a_3+k-\ell\leq k-2+k-\ell=2k-(\ell+2)$, and
\item $a_2-\ell_2=(6k-1-a_1-a_3)-\ell_2\leq(6k-1-(4k+1)-\ell)-\ell_2\leq2k-(\ell+2)$,
\end{itemize}
Lemma~\ref{lem: N-game if pebbles&lt;4k-l+1 K3} implies that $\gamma_{2\ell+3}=\gamma_{2(\ell+2)-1}$ is an $N$-game. Therefore, player $A$ has a winning strategy and $\gamma_1$ is an $N$-game.

Next, suppose that $a_2\geq k+1$. To start the game, player $A$ can make a pebbling move to obtain $\gamma_2=\Gamma(a_1+k,a_2-k-1,a_3)$. Since $(a_2-k-1)+a_3\leq(6k-1)-(4k+1)-k-1=k-3$, player $B$ can only make a pebbling move from $v_1$ to obtain $\gamma_3$. From here, we can inductively define $\gamma_{2\widetilde{t}+1}$ for each positive integer $\widetilde{t}$ as follows. Let $\gamma_i=\Gamma(a_1^{(i)},a_2^{(i)},a_3^{(i)})$ for positive integers $i$. If either $a_2^{(2\widetilde{t}+1)}$ or $a_3^{(2\widetilde{t}+1)}$ is at least $k+1$, then player $A$ can perform an echo pebbling move to obtain $\gamma_{2\widetilde{t}+2}$. After that, player $B$ can only make a pebbling move from $v_1$ to obtain $\gamma_{2\widetilde{t}+3}$. Let $t$ be the smallest positive integer such that both $a_2^{(2t+1)}$ and $a_3^{(2t+1)}$ are at most $k$. Let $i\in\{2,3\}$ be such that $a_i^{(2t+1)}\leq a_{5-i}^{(2t+1)}$. Note that $a_{5-i}^{(2t+1)}=k$ and $a_i^{(2t+1)}\leq(6k-1)-(4k+1)-k-t=k-2-t$, thus $t\leq k-2$. At this stage, player $A$ can make a pebbling move from $v_1$ to $v_i$ to obtain $\gamma_{2t+2}$, where $a_1^{(2t+2)}=a_1-t-(k+1)$, $a_i^{(2t+2)}\leq2k-2-t$, and $a_{5-i}^{(2t+2)}=k$.

Now we can inductively define $\gamma_{2t+2\widetilde{\tau}}$ for each positive integer $\widetilde{\tau}$ as follows. At the game $\gamma_{2t+2\widetilde{\tau}}$, if player $B$ makes a pebbling move from $v_i$ to obtain $\gamma_{2t+2\widetilde{\tau}+1}$, then player $A$ can always perform an echo pebbling move to obtain $\gamma_{2t+2\widetilde{\tau}+2}$ since $a_1-t-(k+1)&gt;k&gt;k-2-t$. Let $\tau$ be the smallest positive integer such that at $\gamma_{2t+2\tau}$, player $B$ makes a pebbling move from $v_1$ to obtain $\gamma_{2t+2\tau+1}$. Note that $a_i^{(2t+2\tau-1)}=a_i^{(2t+1)}-(\tau-1)\leq k-2-t-(\tau-1)$, and thus $t+\tau+1\leq k$. Then
\begin{align*}
    a_1^{(2t+2\tau+1)} &amp; \leq a_1^{(2t+2)}-(k+1)\\ 
    &amp; =(6k-1)-a_2-a_3-t-2(k+1)\\
&amp; \leq(6k-1)-(k+1)-t-2(k+1)\\
&amp;=3k-4-t &lt;4k-(t+\tau+1)-1,\\
\end{align*}
and 
\begin{equation*}
\min\big(a_2^{(2t+2\tau+1)},a_3^{(2t+2\tau+1)}\big)\leq\max(2k-1-t-\tau,k)=2k-(t+\tau+1).
\end{equation*}
As a result, $\gamma_{2t+2\tau+1}$ is an $N$-game by Lemma~\ref{lem: N-game if pebbles&lt;4k-l+1 K3}.
\end{proof}

We are now ready to prove Theorem~\ref{thm:K3}.
\begin{proof}[Proof of Theorem~$\ref{thm:K3}$]
Note that $\mathcal{P}_{6k-1}=\Gamma\{4k+1,k-1,k-1\}$ by Lemma~\ref{lem: (4k+1,k-1,k-1) P-game}, Corollary~\ref{cor: K3 N-games pt 1}, and Lemma~\ref{lem: K3 N-games pt 2}. Hence, $\mathcal{N}_{6k}=\Gamma\{3k+1,2k,k-1\}$ since they are the only predecessors of the games in $\Gamma\{4k+1,k-1,k-1\}$. The predecessors of the games in $\Gamma\{3k+1,2k,k-1\}$ are given by
\begin{equation}\label{eqn:candidatesP6k+1}
\Gamma\{4k+2,k,k-1\}\cup\Gamma\{3k+1,2k+1,k-1\}\cup\Gamma\{2k+1,2k,2k\}\cup\Gamma\{3k+1,2k,k\}.
\end{equation}
The set of games in \eqref{eqn:candidatesP6k+1} contains the only candidates for inclusion in $\mathcal{P}_{6k+1}$. However,
\begin{itemize}
\item the games in $\Gamma\{4k+2,k,k-1\}\cup\Gamma\{3k+1,2k+1,k-1\}$ are predecessors of the games in $\Gamma\{3k+1,2k-1,k\}$, which are $P$-games since they are not in $\mathcal{N}_{6k}$;
\item the games in $\Gamma\{2k+1,2k,2k\}\cup\Gamma\{3k+1,2k,k\}$ are predecessors of the games in $\Gamma\{3k,2k,k\}$, which are also $P$-games.
\end{itemize}
Therefore, all the games in \eqref{eqn:candidatesP6k+1} are not in $\mathcal{P}_{6k+1}$. This implies that $\mathcal{P}_{6k+1}=\emptyset$, and $m=6k+1$ is the minimum integer such that $\mathcal{G}_m=\mathcal{N}_m$.
\end{proof}







\section{Classifying the $(2:1)$-pebbling games on $C_4$}\label{sec:C4}

The focus of this section is $G=C_4$ with $(2:1)$-pebbling moves, so we will abbreviate the notation $\mathcal{G}_{C_4,m}^{(2:1)}$, $\mathcal{P}_{C_4,m}^{(2:1)}$, $\mathcal{N}_{C_4,m}^{(2:1)}$, and $\Gamma_{C_4}^{(2:1)}(a_0,a_1,a_2,a_3)$ as $\mathcal{G}_m$, $\mathcal{P}_m$, $\mathcal{N}_m$, and $\Gamma(a_0,a_1,a_2,a_3)$, respectively. We will fully determine the sets $\mathcal{P}_m$ and $\mathcal{N}_m$, thus proving that $m^{(2:1)}(C_4)$ does not exist.

Let the vertices of $C_4$ be $v_0,v_1,v_2,v_3$, where $v_i$ is adjacent to $v_{i+1}$ for all $i\in\{0,1,2,3\}$. Note that in this section, the addition in the indices is always performed modulo $4$. Additionally, we define some specialty moves to facilitate the discussions. Suppose that one player makes a pebbling move from $v_j$ to $v_{j+\epsilon}$ for some $j\in\{0,1,2,3\}$ and $\epsilon\in\{-1,1\}$. Then several response moves by their opponent are as follows. A \emph{reverse rotational move} is a pebbling move by the opponent from $v_j$ to $v_{j-\epsilon}$ (Figure~\ref{fig:reverserotational}), a \emph{rotational symmetric move} is from $v_{j+2}$ to $v_{j-\epsilon}$ (Figure~\ref{fig:rotationalsymmetric}), and a \emph{reflectional move} is from $v_{j-\epsilon}$ to $v_{j+2}$ (Figure~\ref{reflectional}).

\begin{figure}[htb]
\centering
\begin{minipage}{0.31\textwidth}
\centering
\begin{tikzpicture}
\draw(0,0)--(2,0)--(2,2)--(0,2)--cycle;
\filldraw(0,0)circle(0.12);
\filldraw(2,0)circle(0.12);
\filldraw(2,2)circle(0.12);
\filldraw(0,2)circle(0.12);
\node[below left]at(0,0){$v_j$};
\node[below right]at(2,0){$v_{j+\epsilon}$};
\node[above right]at(2,2){$v_{j+2}$};
\node[above left]at(0,2){$v_{j-\epsilon}$};
\path[-latex](0.2,-0.2) edge[bend right=50] node [left] {} (1.8,-0.2);
\path[-latex](-0.2,0.2) edge[bend left=50] node [right] {} (-0.2,1.8);
\node at(1,-1){Initial move};
\node[rotate=90]at(-1.2,1){Response move};
\end{tikzpicture}
\caption{Reverse rotational move.}\label{fig:reverserotational}
\end{minipage}\qquad
\begin{minipage}{0.25\textwidth}
\centering
\begin{tikzpicture}
\draw(0,0)--(2,0)--(2,2)--(0,2)--cycle;
\filldraw(0,0)circle(0.12);
\filldraw(2,0)circle(0.12);
\filldraw(2,2)circle(0.12);
\filldraw(0,2)circle(0.12);
\node[below left]at(0,0){$v_j$};
\node[below right]at(2,0){$v_{j+\epsilon}$};
\node[above right]at(2,2){$v_{j+2}$};
\node[above left]at(0,2){$v_{j-\epsilon}$};
\path[-latex](0.2,-0.2) edge[bend right=50] node [left] {} (1.8,-0.2);
\path[-latex](1.8,2.2) edge[bend right=50] node [right] {} (0.2,2.2);
\node at(1,-1){Initial move};
\node at(1,3){Response move};
\end{tikzpicture}
\caption{Rotational symmetric move.}\label{fig:rotationalsymmetric}
\end{minipage}\qquad
\begin{minipage}{0.25\textwidth}
\centering
\begin{tikzpicture}
\draw(0,0)--(2,0)--(2,2)--(0,2)--cycle;
\filldraw(0,0)circle(0.12);
\filldraw(2,0)circle(0.12);
\filldraw(2,2)circle(0.12);
\filldraw(0,2)circle(0.12);
\node[below left]at(0,0){$v_j$};
\node[below right]at(2,0){$v_{j+\epsilon}$};
\node[above right]at(2,2){$v_{j+2}$};
\node[above left]at(0,2){$v_{j-\epsilon}$};
\path[-latex](0.2,-0.2) edge[bend right=50] node [left] {} (1.8,-0.2);
\path[-latex](0.2,2.2) edge[bend left=50] node [right] {} (1.8,2.2);
\node at(1,-1){Initial move};
\node at(1,3){Response move};
\end{tikzpicture}
\caption{Reflectional move.}\label{reflectional}
\end{minipage}
\end{figure}

Next, we define five subsets of $\bigcup_{m\in\Z^+}\mathcal{G}_m$ based on the number pebbles modulo $3$ on each vertex.
\begin{itemize}
    \item $X_{aaab}=\{\Gamma(a_0,a_1,a_2,a_3):a_i\equiv a_{i+1}\equiv a_{i+2}\not\equiv a_{i-1}\pmod3\text{ for some }i\in\{0,1,2,3\}\}$,
    \item $X_{abab}=\{\Gamma(a_0,a_1,a_2,a_3):(a_0\equiv a_2)\not\equiv(a_1\equiv a_3)\pmod3\}$,
    \item $X_{aabc}=\{\Gamma(a_0,a_1,a_2,a_3):a_i \equiv a_{i+1}\pmod3 \text{ and } a_i,a_{i+2},a_{i-1}\text{ are distinct modulo }3\linebreak\text{for some }i\in\{0,1,2,3\}\}$,
    \item $X_{abac}=\{\Gamma(a_0,a_1,a_2,a_3):a_i\equiv a_{i+2}\pmod3\text{ and }a_i,a_{i+1},a_{i-1}\text{ are distinct modulo }3\linebreak\text{for some }i\in\{0,1\}\}$, and
    \item $\hat{X}_{aabb}=\{\Gamma(a_0,a_1,a_2,a_3):a_i\equiv a_{i+1}\pmod3\text{ and }a_{i+2}\equiv a_{i-1}\pmod3\text{ for some }\linebreak i\in\{0,1\}\}$. The hat notation indicates $\hat{X}_{aabb}$ includes games with $a_i\equiv a_{i+2} \pmod 3$ and those with $a_i\not\equiv a_{i+2}\pmod3$.
\end{itemize}
We further define four subsets of $\bigcup_{m\in\Z^+}\mathcal{G}_m$ based on the number pebbles modulo $4$ on each vertex.
\begin{itemize}
    \item $Y_{aabc}=\{\Gamma(a_0,a_1,a_2,a_3):a_{i+2}\equiv a_i+2\pmod4\text{ and }a_{i+1}\equiv a_{i-1}+1\pmod4\text{ for some}\linebreak i\in\{0,1,2,3\}\}$.
    \item $\hat{Y}_{abac}=\{\Gamma(a_0,a_1,a_2,a_3):a_i\equiv a_{i+2}\pmod4\text{ and }a_{i+1}\equiv a_{i-1}+1\pmod4\text{ for some }\linebreak i\in\{0,1,2,3\}\}$. The hat indicates $\hat{Y}_{abac}$ includes games with $a_i\equiv a_{i+1}\pmod4$, those with $a_i\equiv a_{i-1}\pmod4$, and those with distinct $a_i,a_{i+1},a_{i-1}$ modulo $4$.
    \item $\hat{Y}_{abab}=\{\Gamma(a_0,a_1,a_2,a_3):a_0\equiv a_2\pmod4\text{ and }a_1\equiv a_3\pmod4\}$. The hat indicates $\hat{Y}_{abab}$ includes games with  $a_0\equiv a_1\pmod4$ and those with $a_0\not\equiv a_1\pmod4$.
    \item $(\hat{Y}_{abab})^c=\{\Gamma(a_0,a_1,a_2,a_3):a_0+a_1+a_2+a_3\text{ is even and }\Gamma(a_0,a_1,a_2,a_3)\notin\hat{Y}_{abab}\}$.
\end{itemize}


\begin{remark}\label{rmk:XY}
Here are some quick observations on the sets defined above.
\begin{enumerate}[$(a)$]
\item\label{item:partition} The sets $X_{aaab},X_{abab},X_{aabc},X_{abac},\hat{X}_{aabb}$ form a partition of $\bigcup_{m\in\Z^+}\mathcal{G}_m$.
\item\label{item:odd} The sets $Y_{aabc}$ and $\hat{Y}_{abac}$ form a partition of $\bigcup_{m\in\Z^+}\mathcal{G}_{2m-1}$, while $\hat{Y}_{abab}$ and $(\hat{Y}_{abab})^c$ form a partition of $\bigcup_{m\in\Z^+}\mathcal{G}_{2m}$.
\end{enumerate}
\end{remark}

The next two lemmas together show that $\hat{X}_{aabb}\cup X_{abac}$ and $X_{aaab}\cup X_{abab}\cup X_{aabc}$ are closed under pebbling moves.

\begin{lemma}\label{RotSymRefl}
Each of $X_{aaab}$, $X_{abab}$, $X_{aabc}$, $X_{abac}$, and $\hat{X}_{aabb}$ is invariant after a pebbling move by one player followed by a rotational symmetric or reflectional move by their opponent.
\end{lemma}
\begin{proof}
Suppose one player makes a pebbling move on $\Gamma(a_0,a_1,a_2,a_3)$ to obtain $a_j-2$ and $a_{j+\epsilon}+1$ pebbles on vertices $v_j$ and $v_{j+\epsilon}$, respectively, for some $j\in\{0,1,2,3\}$ and $\epsilon\in\{-1,1\}$. A subsequent rotational symmetric move by their opponent results in $a_{j+2}-2$ and $a_{j-\epsilon}+1$ pebbles on vertices $v_{j+2}$ and $v_{j-\epsilon}$, respectively, and a reflectional move results in $a_{j+2}+1$ and $a_{j-\epsilon}-2$ pebbles on vertices $v_{j+2}$ and $v_{j-\epsilon}$, respectively. After either move by the opponent, the number of pebbles on $v_j$ is congruent to $a_j+1$ modulo $3$ for all $0\leq j\leq 3$. Therefore, each of $X_{aaab}$, $X_{abab}$, $X_{aabc}$, $X_{abac}$, and $\hat{X}_{aabb}$ is invariant after the specified response move by the opponent.
\end{proof}

\begin{lemma}\label{lem:XaabbXabac}
Both sets $\hat{X}_{aabb}\cup X_{abac}$ and $X_{aaab}\cup X_{abab}\cup X_{aabc}$ are closed under pebbling moves.
\end{lemma}
\begin{proof}
We first show that $\hat{X}_{aabb}\cup X_{abac}$ is closed under pebbling moves. Consider a pebbling game $\Gamma(a_0,a_1,a_2,a_3)\in\hat{X}_{aabb}\cup X_{abac}$ with one pebbling move from $v_j$ to $v_{j+\epsilon}$ for some $j\in\{0,1,2,3\}$ and $\epsilon\in\{-1,1\}$, and let the resultant pebbling game be $\Gamma(a_0',a_1',a_2',a_3')$. Suppose that $\Gamma(a_0,a_1,a_2,a_3)\in\hat{X}_{aabb}$ with $a_i\equiv a_{i+1}\pmod3$ and $a_{i+2}\equiv a_{i-1}\pmod3$ for some $i\in\{0,1\}$. If $a_j\mod {a_{j+\epsilon}}{3}$, then $a_j'\equiv a_j+1\equiv a_{j+\epsilon}+1\mod{a_{j+\epsilon}'}{3}$ and $a_{j+2}'\equiv a_{j+2}\equiv a_{j-\epsilon}\mod{a_{j-\epsilon}'}{3}$, thus $\Gamma(a_0',a_1',a_2',a_3')\in\hat{X}_{aabb}$. If $a_j\not\mod{a_{j+\epsilon}}{3}$, then Table~\ref{tab:Xaabb} gives the remaining possible outcomes of $\Gamma(a_0',a_1',a_2',a_3')$ after one pebbling move.
\begin{table}[H]
\centering
\begin{tabular}{c|c|c|c}
$\{a_i,a_{i+2}\}\pmod3$&amp;$(a_j,a_{j+\epsilon})\pmod3$&amp;$(a_j',a_{j+\epsilon}',a_{j+2}',a_{j-\epsilon}')\pmod3$&amp; $\Gamma(a_0',a_1',a_2',a_3')$\\
\hline\hline
\multirow{2}{*}{$\{0,1\}$}&amp; $(0,1)$&amp; $(1,2,1,0)$&amp; \multirow{6}{*}{$X_{abac}$}\\
&amp; $(1,0)$&amp; $(2,1,0,1)$\\
\cline{1-3}
\multirow{2}{*}{$\{0,2\}$}&amp; $(0,2)$&amp; $(1,0,2,0)$&amp;\\
&amp; $(2,0)$&amp; $(0,1,0,2)$\\
\cline{1-3}
\multirow{2}{*}{$\{1,2\}$}&amp; $(1,2)$&amp; $(2,0,2,1)$&amp;\\
&amp; $(2,1)$&amp; $(0,2,1,2)$
\end{tabular}
\caption{Resultant games after one pebbling move from $\hat{X}_{aabb}$ if $a_j\not\mod{a_{j+\epsilon}}{3}$.}
\label{tab:Xaabb}
\end{table}
Next, suppose that $\Gamma(a_0,a_1,a_2,a_3)\in X_{abac}$ with $a_i\equiv a_{i+2}\pmod3$ and $a_i,a_{i+1},a_{i-1}$ being distinct modulo $3$ for some $i\in\{0,1\}$. Table~\ref{tab:Xabac} gives all possible outcomes of $\Gamma(a_0',a_1',a_2',a_3')$ after one pebbling move. By exhausting all possible resultant games $\Gamma(a_0',a_1',a_2',a_3')$, we see that $\hat{X}_{aabb}\cup X_{abac}$ is closed under pebbling moves.
\begin{table}[H]
\centering
\begin{tabular}{c|c|c|c}
$a_i\pmod3$&amp;$(a_j,a_{j+\epsilon})\pmod3$&amp;$(a_j',a_{j+\epsilon}',a_{j+2}',a_{j-\epsilon}')\pmod3$&amp; $\Gamma(a_0',a_1',a_2',a_3')$\\
\hline\hline
\multirow{4}{*}{$0$}&amp; $(0,1)$&amp; $(1,2,0,2)$&amp; \multirow{2}{*}{$X_{abac}$}\\
&amp; $(1,0)$&amp; $(2,1,2,0)$&amp;\\
\cline{2-4}
&amp; $(0,2)$&amp; $(1,0,0,1)$&amp; \multirow{2}{*}{$\hat{X}_{aabb}$}\\
&amp; $(2,0)$&amp; $(0,1,1,0)$&amp;\\
\hline
\multirow{4}{*}{$1$}&amp; $(1,0)$&amp; $(2,1,1,2)$&amp; \multirow{2}{*}{$\hat{X}_{aabb}$}\\
&amp; $(0,1)$&amp; $(1,2,2,1)$&amp;\\
\cline{2-4}
&amp; $(1,2)$&amp; $(2,0,1,0)$&amp; \multirow{2}{*}{$X_{abac}$}\\
&amp; $(2,1)$&amp; $(0,2,0,1)$&amp;\\
\hline
\multirow{4}{*}{$2$}&amp; $(2,0)$&amp; $(0,1,2,1)$&amp; \multirow{2}{*}{$X_{abac}$}\\
&amp; $(0,2)$&amp; $(1,0,1,2)$&amp;\\
\cline{2-4}
&amp; $(2,1)$&amp; $(0,2,2,0)$&amp; \multirow{2}{*}{$\hat{X}_{aabb}$}\\
&amp; $(1,2)$&amp; $(2,0,0,2)$&amp;
\end{tabular}
\caption{Resultant games after one pebbling move from $X_{abac}$.}
\label{tab:Xabac}
\end{table}

To show that $X_{aaab}\cup X_{abab}\cup X_{aabc}$ is closed under pebbling moves, we suppose by way of contradiction that there exists a pebbling game $\Gamma(a_0,a_1,a_2,a_3)$ in $X_{aaab}\cup X_{abab}\cup X_{aabc}$ and a pebbling move from $v_j$ to $v_{j+\epsilon}$ for some $j\in\{0,1,2,3\}$ and $\epsilon\in\{-1,1\}$ such that the resultant game $\Gamma(a_0',a_1',a_2',a_3')$ is not in $X_{aaab}\cup X_{abab}\cup X_{aabc}$. By Remark~\ref{rmk:XY}$(\ref{item:partition})$, we have $\Gamma(a_0',a_1',a_2',a_3')$ in $\hat{X}_{aabb}\cup X_{abac}$. Now we consider the game $\Gamma(a_0+2,a_1+2,a_2+2,a_3+2)$ in $X_{aaab}\cup X_{abab}\cup X_{aabc}$. After the pebbling move from $v_j$ to $v_{j+\epsilon}$, a rotational symmetric response move from $v_{j+2}$ to $v_{j-\epsilon}$ yields a resultant game in $X_{aaab}\cup X_{abab}\cup X_{aabc}$ by Lemma~\ref{RotSymRefl}. This contradicts that $\hat{X}_{aabb}\cup X_{abac}$ is closed under pebbling moves since $\Gamma(a_0'+2,a_1'+2,a_2'+2,a_3'+2)$ is in $\hat{X}_{aabb}\cup X_{abac}$.
\end{proof}


We now begin classifying all $(2:1)$-pebbling games on $C_4$ as $P$-games and $N$-games.


\begin{theorem}\label{thm:XaabbXabac}
A game $\Gamma(a_0,a_1,a_2,a_3)\in\hat{X}_{aabb}\cup X_{abac}$ is a $P$-game if and only if $a_0+a_1+a_2+a_3$ is even.
\end{theorem}
\begin{proof}
If $a_0+a_1+a_2+a_3=0$, then $\Gamma(0,0,0,0)$ is the only possibility and is a $P$-game. There is no game in $\hat{X}_{aabb}\cup X_{abac}$ with $a_0+a_1+a_2+a_3=1$. If $a_0+a_1+a_2+a_3=2$,\linebreak then $(a_i,a_{i+1},a_{i+2},a_{i-1})=(1,1,0,0)$ for some $i\in\{0,1,2,3\}$, and $\Gamma(a_0,a_1,a_2,a_3)$ is a $P$-game. If $a_0+a_1+a_2+a_3=3$, then $(a_i,a_{i+1},a_{i+2},a_{i-1})\in\{(3,0,0,0),(0,1,0,2)\}$ for some $i\in\{0,1,2,3\}$, and $\Gamma(a_0,a_1,a_2,a_3)$ is an $N$-game. If $a_0+a_1+a_2+a_3=4$, then $(a_i,a_{i+1},a_{i+2},a_{i-1})\in\{(2,2,0,0),(1,1,1,1),(1,0,1,2)\}$ for some $i\in\{0,1,2,3\}$, and it is not difficult to verify that $\Gamma(a_0,a_1,a_2,a_3)$ is a $P$-game. Now assume that for some integer $k\geq4$, $\Gamma(a_0,a_1,a_2,a_3)$ is a $P$-game if and only if $a_0+a_1+a_2+a_3=k$ is even. If $a_0+a_1+a_2+a_3=k+1$, then since $k+1\geq5$, there exists $j\in\{0,1,2,3\}$ such that $a_j\geq2$. Hence, there is at least one pebbling move on $\Gamma(a_0,a_1,a_2,a_3)$, and the resultant pebbling game $\Gamma(a_0',a_1',a_2',a_3')$ is in $\hat{X}_{aabb}\cup X_{abac}$ by Lemma~\ref{lem:XaabbXabac}. By the induction hypothesis, $\Gamma(a_0',a_1',a_2',a_3')$ is a $P$-game if and only if $a_0'+a_1'+a_2'+a_3'=k$ is even, which shows that $\Gamma(a_0,a_1,a_2,a_3)$ is an $N$-game if and only if $k+1$ is odd. This completes our proof by induction.
\end{proof}


\begin{theorem}\label{Yabab}
Every game $\Gamma(a_0,a_1,a_2,a_3) \in \hat{Y}_{abab}$ is a $P$-game. 
\end{theorem}

\begin{proof}
For $\Gamma(a_0,a_1,a_2,a_3) \in \hat{Y}_{abab}$, if there does not exist $j\in\{0,1,2,3\}$ such that $a_j\geq2$, then player $A$ does not have a move and thus $\Gamma(a_0,a_1,a_2,a_3)$ is a $P$-game. Otherwise, assume that player $A$ made a pebbling move from $v_j$ to $v_{j+\epsilon}$ for some $j\in\{0,1,2,3\}$ and $\epsilon \in \{-1,1\}$, where $a_j\geq2$. Since $a_{j+2}\equiv a_j\pmod{4}$, we have $\max(a_j-2,a_{j+2})\geq2$. As a result, if $a_j-2 \ge 2$, then player $B$ can apply a reverse rotational move from $v_j$ to $v_{j-\epsilon}$; if $a_{j+2}\geq2$, then player $B$ can apply a rotational symmetric move from $v_{j+2}$ to $v_{j-\epsilon}$. In both cases, player $B$ has a strategy to ensure that the resultant game returns to $\hat{Y}_{abab}$. Therefore, $\Gamma(a_0,a_1,a_2,a_3)$ can be proved to be a $P$-game inductively.
\end{proof}





\begin{theorem}\label{3XandYabac}
Every game $\Gamma(a_0,a_1,a_2, a_3) \in (X_{abab} \cup X_{aabc} \cup X_{aaab}) \cap \hat{Y}_{abac}$ is a $P$-game.
\end{theorem}

\begin{proof}
For $\Gamma(a_0,a_1,a_2,a_3) \in (X_{abab} \cup X_{aabc} \cup X_{aaab}) \cap \hat{Y}_{abac}$, if there does not exist\linebreak $j\in\{0,1,2,3\}$ such that $a_j\geq2$, then player $A$ does not have a move and thus $\Gamma(a_0,a_1,a_2,a_3)$ is a $P$-game. Otherwise, assume that player $A$ made a pebbling move from $v_j$ to $v_{j+\epsilon}$ for some $j\in\{0,1,2,3\}$ and $\epsilon \in \{-1,1\}$, where $a_j\geq2$.

First, consider the case when $a_{j+2}\equiv a_j\pmod{4}$. In this case, $\max(a_j-2,a_{j+2})\geq2$. If $a_j-2 \ge 2$, then player $B$ can apply the strategy of a reverse rotational move from $v_j$ to $v_{j-\epsilon}$; if $a_{j+2}\geq2$, then player $B$ can apply the strategy of a rotational symmetric move from $v_{j+2}$ to $v_{j-\epsilon}$. In both cases, player $B$ has a strategy to ensure that the resultant game returns to $\hat{Y}_{abac}$.

Next, consider the case when $a_{j+2}\equiv a_j\pm1\pmod{4}$. If $\max(a_j-2,a_{j+2})\geq2$, then player $B$ has the same strategy as above to obtain a resultant game in $\hat{Y}_{abac}$. Otherwise,\linebreak $(a_j,a_{j+2})\in\{(2,1),(3,0)\}$ and $a_{j+1}\equiv a_{j-1}\pmod{4}$. Note that $\Gamma(2,0,1,0)$ and $\Gamma(3,0,0,0)$ are not in $X_{abab} \cup X_{aabc} \cup X_{aaab}$, so $(a_{j+1},a_{j-1})\neq(0,0)$. If $a_{j+\epsilon}\geq1$, then when\linebreak $(a_j,a_{j+2})=(2,1)$, player $B$ can apply an echo pebbling move from $v_{j+\epsilon}$ to $v_j$, and when $(a_j,a_{j+2})=(3,0)$, player $B$ can make a pebbling move from $v_{j+\epsilon}$ to $v_{j+2}$. Otherwise, if $a_{j+\epsilon}=0$, then $a_{j-\epsilon}\geq4$, so when $(a_j,a_{j+2})=(2,1)$, player $B$ can make a pebbling move from $v_{j-\epsilon}$ to $v_j$, and when $(a_j,a_{j+2})=(3,0)$, player $B$ can apply a reflectional move from $v_{j-\epsilon}$ to $v_{j+2}$. In all cases, player $B$ has a strategy to ensure that the resultant game returns to $\hat{Y}_{abac}$. By Lemma~\ref{lem:XaabbXabac}, this resultant game is in $(X_{abab} \cup X_{aabc} \cup X_{aaab})\cap \hat{Y}_{abac}$. Therefore, the game $\Gamma(a_0,a_1,a_2,a_3)$ can be proved to be a $P$-game inductively.
\end{proof}


Theorems \ref{thm:XaabbXabac}, \ref{Yabab}, and \ref{3XandYabac} are summarized in Table \ref{IncompletePNtable}. Recall from Remark~\ref{rmk:XY}(\ref{item:odd}) that $|\gamma|=a_0+a_1+a_2+a_3$ is even if $\gamma\in \hat{Y}_{abab}\cup(\hat{Y}_{abab})^c$ and $|\gamma|$ is odd if $\gamma\in \hat{Y}_{abac}\cup Y_{aabc}$.
\begin{table}[htb]
\begin{center}
    \begin{tabular}{|c|c|c|c|c|c|}
    \hline
    &amp; $\hat{X}_{aabb}$ &amp; $X_{abac}$ &amp; $X_{abab}$ &amp; $X_{aabc}$ &amp; $X_{aaab}$ \\
    \hline
    $\hat{Y}_{abab}$ &amp; $P$ &amp; $P$ &amp; $P$ &amp; $P$ &amp; $P$ \\
    \hline
    $(\hat{Y}_{abab})^c$ &amp; $P$ &amp; $P$ &amp;  &amp;  &amp;  \\
    \hline
    $\hat{Y}_{abac}$ &amp; $N$ &amp; $N$ &amp; $P$ &amp; $P$ &amp; $P$ \\
    \hline
    $Y_{aabc}$ &amp; $N$ &amp; $N$ &amp;  &amp;  &amp;  \\
    \hline
    \end{tabular}
    \caption{Classification of $C_4$ $(2:1)$-pebbling games on $C_4$ due to Theorems \ref{thm:XaabbXabac}, \ref{Yabab}, and \ref{3XandYabac}.}
    \label{IncompletePNtable}
\end{center}
\end{table}

\begin{theorem}\label{Yaabc}
Every game $\Gamma(a_0,a_1,a_2,a_3) \in Y_{aabc}$ is an $N$-game.
\end{theorem}


\begin{proof}
For $\Gamma(a_0,a_1,a_2,a_3)\in Y_{aabc}$, let $i\in\{0,1,2,3\}$ and $\epsilon\in\{-1,1\}$ such that
\begin{center}$a_i\equiv a_{i+\epsilon}\pmod4$ and $a_{i+2}\equiv a_i+2\pmod4$.
\end{center}
By the definition of $Y_{aabc}$, we have $a_{i-\epsilon}\equiv a_{i+\epsilon}\pm1\pmod4$. Note that $\max(a_i,a_{i+2})\geq2$. If $a_{i-\epsilon}\equiv a_{i+\epsilon}+1\pmod4$, then player $A$ can make a pebbling move from $v_i$ or $v_{i+2}$ to $v_{i+\epsilon}$; otherwise, if $a_{i-\epsilon}\equiv a_{i+\epsilon}-1\pmod4$, then player $A$ can make a pebbling move from $v_i$ or $v_{i+2}$ to $v_{i-\epsilon}$. In both cases, player $A$ has a strategy to obtain a resultant game in $\hat{Y}_{abab}$, which is a $P$-game by Theorem~\ref{Yabab}. Therefore, the game $\Gamma(a_0,a_1,a_2,a_3)$ is an $N$-game.
\end{proof}

\begin{theorem}\label{3XYcomp}
Every game $\Gamma(a_0,a_1,a_2,a_3) \in (X_{abab} \cup X_{aabc} \cup X_{aaab}) \cap (\hat{Y}_{abab})^c$ is an $N$-game.
\end{theorem}

\begin{proof}
Let $\Gamma(a_0,a_1,a_2,a_3)\in (X_{abab}\cup X_{aabc}\cup X_{aaab})\cap(\hat{Y}_{abab})^c$. By the definition of $(\hat{Y}_{abab})^c$, there exists $i\in\{0,1\}$ such that $a_i\not\mod{a_{i+2}}{4}$. If $a_{i+2}\mod{a_i+2}{4}$, then $\max(a_i,a_{i+2})\geq2$, and player $A$ can make a pebbling move from $v_i$ to $v_{i+\epsilon}$ or from $v_{i+2}$ to $v_{i+\epsilon}$. Otherwise, we have $a_{i+2}\equiv a_i\pm1\pmod4$. This implies that $a_{i-\epsilon}\equiv a_{i+\epsilon}+1\pmod4$ for some $\epsilon\in\{-1,1\}$ since $a_0+a_1+a_2+a_3$ is even. If $\max(a_0,a_1,a_2,a_3)\leq1$, then $(a_i,a_{i+\epsilon},a_{i+2},a_{i-\epsilon})$ is in $\{(0,0,1,1),(1,0,0,1)\}$, contradicting that $\Gamma(a_0,a_1,a_2,a_3)\in X_{abab}\cup X_{aabc}\cup X_{aaab}$. Hence, either $\max(a_i,a_{i+2})\geq2$ or $\max(a_{i+\epsilon},a_{i-\epsilon})\geq2$. Without loss of generality, assume that $\max(a_i,a_{i+2})\geq2$. Then player $A$ can make a pebbling move from $v_i$ to $v_{i+\epsilon}$ or from $v_{i+2}$ to $v_{i+\epsilon}$. In both cases, player $A$ has a strategy to obtain a resultant game in $\hat{Y}_{abac}$. By Lemma~\ref{lem:XaabbXabac}, this resultant game is in $(X_{abab}\cup X_{aabc}\cup X_{aaab})\cap\hat{Y}_{abac}$, which is a $P$-game by Theorem~\ref{3XandYabac}. Therefore, the game $\Gamma(a_0,a_1,a_2,a_3)$ is an $N$-game.
\end{proof}

Theorems~\ref{thm:XaabbXabac} through \ref{3XYcomp} completely classify all $(2:1)$-pebbling games on $C_4$ into $P$-games and $N$-games. To conclude, we summarize the results in Table~\ref{PNtable}.


\begin{table}[H]
\begin{center}
    \begin{tabular}{|c|c|c|c|c|c|}
    \hline
    &amp; $\hat{X}_{aabb}$ &amp; $X_{abac}$ &amp; $X_{abab}$ &amp; $X_{aabc}$ &amp; $X_{aaab}$ \\
    \hline
    $\hat{Y}_{abab}$ &amp; $P$ &amp; $P$ &amp; $P$ &amp; $P$ &amp; $P$ \\
    \hline
    $(\hat{Y}_{abab})^c$ &amp; $P$ &amp; $P$ &amp; $N$ &amp; $N$ &amp; $N$ \\
    \hline
    $\hat{Y}_{abac}$ &amp; $N$ &amp; $N$ &amp; $P$ &amp; $P$ &amp; $P$ \\
    \hline
    $Y_{aabc}$ &amp; $N$ &amp; $N$ &amp; $N$ &amp; $N$ &amp; $N$ \\
    \hline
    \end{tabular}
    \caption{Complete classification of $(2:1)$-pebbling games on $C_4$.}
    \label{PNtable}
\end{center}
\end{table}



 
\section{Future directions}

As mentioned in Section~\ref{sec:intro}, among the computational results given in Table~\ref{tbl:m(Kn)}, the data in the first column and the first row are now fully justified by mathematical proofs. It should be noted that different strategies were used for these proofs. It will be interesting if one can develop a unified technique to prove the patterns in additional rows or columns in the table.




\appendix
\section{Appendix: Computer code}\label{Appendix}
\begin{verbatim}
(*n represents the number of vertices in the complete graph. Each 
pebbling move removes k+1 pebbles from a vertex and adds k pebbles to 
an adjacent vertex.*)

Do[(*Given n and m, list all possible assignments with m pebbles.*)
 alltuples[n_, m_] := IntegerPartitions[m + n, {n}] - 1;
 
 (*Given an assignment, list all resultant assignments after one 
 pebbling move; only works for n&gt;=3.*)
 pebblemoves[config_] := 
  Block[{n, temp}, n = Length[config]; 
   temp = Table[config, {i, n (n - 1)}] + 
     Permutations[Join[{-(k + 1), k}, Table[0, {i, n - 2}]]]; 
   temp = Select[temp, Min[#] &gt;= 0 &amp;]; 
   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] &lt; 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["k=", k, " n=", n, " m=", m], {n, 5, 10}], {k, 1, 6}]
\end{verbatim}


\begin{thebibliography}{1}
\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{flww}
E.~Fiorini, M.~Lind, A.~Woldar, and T. W. H.~Wong, Characterizing winning positions in the impartial two-player pebbling game on complete graphs, \textit{J. Integer Sequences} \textbf{24} (2021), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL24/Wong/wong31.html}{Article 21.6.4}.

\bibitem{LFW}
M.~Lind, E.~Fiorini, and A.~Woldar, On properties of pebble assignment graphs, \textit{Graphs Combin.} \textbf{38} (2022), Article 45.

\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, \textit{The On-Line Encyclopedia of Integer Sequences}, \url{https://oeis.org}, 2024.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\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 sequences
\seqnum{A016921},
\seqnum{A340631},
\seqnum{A346197},
\seqnum{A347637}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 4 2023; 
revised versions received June 9 2023;  May 14 2024.
Published in {\it Journal of Integer Sequences}, June 3 2024.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}
</pre></body></html>