Characterizing Winning Positions in the Impartial Two-Player Pebbling Game on Complete Graphs

Eugene Fiorini

DIMACS Rutgers University

96 Frelinghuysen Road Piscataway, NJ 08854

USA

efiorini@dimacs.rutgers.edu

Max Lind

University Scholars Program Pennsylvania Leadership Charter School

1585 Paoli Pike West Chester, PA 19380

USA

mlind314@icloud.com

Andrew Woldar

Department of Mathematics & Statistics Villanova University 800 Lancaster Avenue Villanova, PA 19085

USA

andrew.woldar@villanova.edu

Tony W. H. Wong Department of Mathematics

Kutztown University of Pennsylvania 15200 Kutztown Road Kutztown, PA 19530

USA

wong@kutztown.edu

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 ≥ 5 is odd and at least n + 7 pebbles if n ≥ 6 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.

1 Introduction

In a classical graph pebbling game played on a simple graph (i.e., an undirected graph with no loops or multiple edges) with a target vertex, a 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 [3], 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 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 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 Nim. Readers may refer to Winning Ways for Your Mathematical Plays, Volume 1 [1, p. 15] for more information on impartial games.

In any impartial game, every game is either first-player winning, denoted as an N-game (N for the next player), or 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. [2], we define a pebble assignment on G to be an n-tuple (S_{G}) = (a_{1}, a_{2}, …, a_{n}), where a_{i} denotes the number of pebbles on vertex v_{i} of G for 1 ≤ i ≤ 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} ≥ a_{2} ≥ ⋯ ≥ a_{n} ≥ 0. We observe that every pebbling game on K_{n} is equivalent to one of this type.

Let m = a_{1} + a_{2} + ⋯ + 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 (n, m)-game and we denote a general such game by Γ_{n,m}. When a particular assignment (a_{1}, a_{2}, …, a_{n}) is specified, we indicate the corresponding pebble game by Γ(a_{1}, a_{2}, …, a_{n}).

The main result of our paper provides conditions for winning positions as follows.

Theorem 1.

(a) Every (2, m)-game Γ(a_{1}, a_{2}) is an N-game if and only if a_{1} ≢ a_{2} (mod 3) when m is even or a_{1} ≡ a_{2} (mod 3) when m is odd.

(b) For m ≥ 7, Γ_{3,m} is an N-game if and only if m is odd.

(c) For m ≥ 23, Γ_{4,m} is an N-game if and only if m is odd.

(d) For odd n ≥ 5 and m ≥ n + 2, Γ_{n,m} is an N-game if and only if m is odd.

(e) For even n ≥ 6 and m ≥ n + 7, Γ_{n,m} is an N-game if and only if m is odd.

Theorem 1 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 ≥ 3, let p(n) denote the smallest positive integer m such that every Γ_{n,m} is an N-game. Observe that if every Γ_{n,m} is an N-game, then every Γ_{n,m+1} is a P -game since all available moves result in an N-game. In turn, every Γ_{n,m+2} is an N-game, and this pattern continues. Hence, the proof of parts (b)–(e) of Theorem 1 will rely on showing that p(3) = 7, p(4) = 23, p(n) = n + 2 when n ≥ 5 is odd, and p(n) = n + 7 when n ≥ 6 is even. (This sequence has been published as \underline{A340631} in the On-Line Encyclopedia of Integer Sequences [4].)

2 Main results

Lemma 2. Let Γ(a′_{1}, a′_{2}) result from any sequence of allowable pebbling moves applied to Γ(a_{1}, a_{2}). Then a′_{1} ≡ a′_{2} (mod 3) if and only if a_{1} ≡ a_{2} (mod 3).

Proof. If Γ(a′_{1}, a′_{2}) results from a single pebbling move, then there are three possibilities: Γ(a′_{1}, a′_{2}) = Γ(a_{2} + 1, a_{1} − 2) (provided a_{2} + 1 ≥ a_{1} − 2), Γ(a′_{1}, a′_{2}) = Γ(a_{1} − 2, a_{2} + 1) (provided a_{1} − 2 ≥ a_{2} + 1), and Γ(a′_{1}, a′_{2}) = Γ(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} ≡ a′_{2} (mod 3) if and only if a_{1} ≡ a_{2} (mod 3). An easy induction on the number of pebbling moves completes the proof.

Proof of Theorem 1(a). We proceed by induction on m. When m = 1, the only possibility is Γ(1, 0) which is clearly a P -game. When m = 2, the only possibilities are Γ(1, 1) and Γ(2, 0). Clearly Γ(1, 1) is a P -game. Since Γ(2, 0) transforms to the P -game Γ(1, 0) after a single move, we conclude that Γ(2, 0) is an N-game. Hence, the statement of Theorem 1(a) holds for m = 1 and m = 2.

Assume now that the statement is true for all ℓ < m and consider an arbitrary game Γ_{2,m}. Observe that every game Γ_{2,m−2} that arises from Γ_{2,m} after two allowable moves must be an N-game by induction if and only if either a_{1} ≢ a_{2} (mod 3) when m − 2 is even, or a_{1} ≡ a_{2} (mod 3) when m − 2 is odd. Since m and m − 2 have the same parity, the result follows immediately from Lemma 2.

Γ(1, 0) ; P ; Γ(2, 0) ; N ; Γ(1, 1) ; P ; Γ(2, 1) ; P ; Γ(3, 0) ; N ; Γ(3, 1) ; N ; Γ(4, 0) ; N ; Γ(2, 2) ; P ; Γ(5, 0) ; P ; Γ(3, 2) ; P ; Γ(4, 1) ; N ; Γ(4, 2) ; N ; Γ(5, 1) ; N ; Γ(3, 3) ; P ; Γ(6, 0) ; P ; Γ(6, 1) ; P ; Γ(4, 3) ; P ; Γ(7, 0) ; P ; Γ(5, 2) ; N ; Γ(8, 0) ; N ; Γ(5, 3) ; N ; Γ(6, 2) ; N ; Γ(4, 4) ; P ; Γ(7, 1) ; P

Figure 1: Diagram of pebbling moves for games Γ_{2,m} with 1 ≤ m ≤ 8

Figure 1 contains all possible games Γ_{2,m} with 1 ≤ m ≤ 8. An arrow indicates the resultant game after a pebbling move, and the letter identifies if the game is an N-game or a P -game.

We initially established p(3) = 7, p(4) = 23, and p(5) = 7 with the aid of a Mathematica program (see Appendix A), but without much trouble, we were able to reproduce the cases p(3) and p(5) by hand. The cases for p(3) and p(4) provide the proof of parts (b) and (c) of Theorem 1, respectively, and the case for p(5) forms the base case for part (d) of the theorem. Thus, for the balance of this section we focus on the case n ≥ 6.

Let P_{n,m} (resp., N_{n,m}) denote the set of all (n, m)-games Γ(a_{1}, a_{2}, …, a_{n}) that are P - games (resp., N-games). For example, P_{n,1} = {Γ(1, 0^{(n−1)})} and N_{n,2} = {Γ(2, 0^{(n−1)})}, where we use the notation 0^{(n−1)} to indicate that there are n − 1 zero entries (i.e., n − 1 vertices with zero pebbles). In what follows, we adopt a similar notation to indicate repeated ones and zeros within a game or assignment.

Let us call Γ_{n,m+1} a predecessor of Γ_{n,m} if Γ_{n,m} results from Γ_{n,m+1} after a single pebbling move. In such case, we refer to Γ_{n,m} as the resultant game.

Lemma 3. For all odd integers n ≥ 7, P_{n,n} = {Γ(1^{(n)})} implies P_{n,n+2} = ∅.

Proof. Assume that P_{n,n} = {Γ(1^{(n)})} for n odd, n ≥ 7, and observe that Γ(3, 1^{(n−2)}, 0) is the unique predecessor of Γ(1^{(n)}). This implies that N_{n,n+1} = {Γ(3, 1^{(n−2)}, 0)}. Continuing in this manner, we see that the only predecessors of Γ(3, 1^{(n−2)}, 0) are Γ(5, 1^{(n−3)}, 0^{(2)}), Γ(3, 3, 1^{(n−4)}, 0^{(2)}), Γ(3, 2, 1^{(n−3)}, 0) and Γ(2, 2, 1^{(n−2)}). Accordingly, these four games are the only candidates for inclusion in P_{n,n+2}.

However, each of Γ(5, 1^{(n−3)}, 0^{(2)}), Γ(3, 3, 1^{(n−4)}, 0^{(2)}) and Γ(3, 2, 1^{(n−3)}, 0) can lead to the resultant game Γ(3, 2, 1^{(n−4)}, 0^{(2)}) after one pebbling move, whereas Γ(2, 2, 1^{(n−2)}) can lead to the resultant game Γ(2, 2, 1^{(n−3)}, 0). Since N_{n,n+1} = {Γ(3, 1^{(n−2)}, 0)}, we conclude that both Γ(3, 2, 1^{(n−4)}, 0^{(2)}) and Γ(2, 2, 1^{(n−3)}, 0) are necessarily P -games. Thus each of the four listed candidates must be N-games, which implies P_{n,n+2} = ∅ as desired.

Lemma 4. Let Γ(a_{1}, a_{2}, …, a_{n+2}) be an (n + 2, m)-game with at least m − n + 2 zeros in its assignment. Then Γ(a_{1}, a_{2}, …, a_{n+2}) and Γ(a_{1}, a_{2}, …, a_{n}) share the same winning positions.

Proof. If m ≤ n, then after any sequence of pebbling moves, the resultant game always has at least 2 zeros. If m > n, then let i be a positive integer such that i ≤ 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 ≥ 2 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, Γ(a_{1}, a_{2}, …, a_{n+2}) and Γ(a_{1}, a_{2}, …, a_{n}) share the same winning positions.

Lemma 5. For all odd integers n ≥ 7, P_{n,n} = {Γ(1^{(n)})} implies P_{n+2,n+2} = {Γ(1^{(n+2)})}.

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 P_{n,n} = {Γ(1^{(n)})} then P_{n+2,n} = {Γ(1^{(n)}, 0^{(2)})}.

If an (n + 2, n + 2)-game has at least four zeros in its assignment, then by Lemma 4 this game is equivalent to an (n, n + 2)-game played on a subgraph K_{n} of K_{n+2}. Since P_{n,n+2} = ∅ by Lemma 3, any (n + 2, n + 2)-game that has at least four zeros in its assignment is an N-game. This implies that P_{n+2,n+2} can only contain (n + 2, n + 2)-games that have at most three zeros in its assignment, i.e.,

P_{n+2,n+2} ⊆ {Γ(4, 1^{(n−2)}, 0^{(3)}), Γ(3, 2, 1^{(n−3)}, 0^{(3)}), Γ(2, 2, 2, 1^{(n−4)}, 0^{(3)}),
Γ(3, 1^{(n−1)}, 0^{(2)}), Γ(2, 2, 1^{(n−2)}, 0^{(2)}), Γ(2, 1^{(n)}, 0), Γ(1^{(n+2)})}.

Four of these games Γ(4, 1^{(n−2)}, 0^{(3)}), Γ(3, 2, 1^{(n−3)}, 0^{(3)}), Γ(2, 2, 2, 1^{(n−4)}, 0^{(3)}), and Γ(2, 2, 1^{(n−2)}, 0^{(2)}) are predecessors of Γ(2, 2, 1^{(n−3)}, 0^{(3)}). After another pebbling move, Γ(2, 2, 1^{(n−3)}, 0^{(3)}) can only result in Γ(3, 1^{(n−3)}, 0^{(4)}), Γ(2, 2, 1^{(n−4)}, 0^{(4)}), or Γ(2, 1^{(n−2)}, 0^{(3)}). Since P_{n+2,n} = {Γ(1^{(n)}, 0^{(2)})}, the last three (n + 2, n)-games are all N-games. Hence, Γ(2, 2, 1^{(n−3)}, 0^{(3)}) is a P -game, and the four games Γ(4, 1^{(n−2)}, 0^{(3)}), Γ(3, 2, 1^{(n−3)}, 0^{(3)}), Γ(2, 2, 2, 1^{(n−4)}, 0^{(3)}), and Γ(2, 2, 1^{(n−2)}, 0^{(2)}) are N-games. Furthermore, the two games Γ(3, 1^{(n−1)}, 0^{(2)}) and Γ(2, 1^{(n)}, 0) are predecessors of the P -game Γ(1^{(n+1)}, 0) after a pebbling move, so they are also N-games. As a result, P_{n+2,n+2} = {Γ(1^{(n+2)})}.

Now we are prepared to prove Theorem 1(d).

Proof of Theorem 1(d). As previously mentioned, p(5) = 7 has been proved by hand. For odd n ≥ 7, we induct on n. The case that P_{7,7} = {Γ(1^{(7)})} has been verified both by hand and by computer. Verification of the inductive step now follows from Lemmas 3 and 5.

Prefatory to proving Theorem 1(e), we will require a couple more lemmas.

Lemma 6. For all even integers n ≥ 6, P_{n,n+1} = {Γ(2, 1^{(n−1)})} implies that each of the following holds:

(i) P_{n,n+3} = {Γ(5, 1^{(n−2)}, 0), Γ(3, 3, 1^{(n−3)}, 0)},

(ii) P_{n,n+5} = {Γ(6, 1^{(n−1)})}, and

(iii) P_{n,n+7} = ∅.

Proof. (i) Let n ≥ 6 be an even integer for which P_{n,n+1} = {Γ(2, 1^{(n−1)})}. Observe that N_{n,n+2} = {Γ(4, 1^{(n−2)}, 0), Γ(3, 2, 1^{(n−3)}, 0), Γ(3, 1^{(n−1)})} since Γ(4, 1^{(n−2)}, 0), Γ(3, 2, 1^{(n−3)}, 0), and Γ(3, 1^{(n−1)}) are the only possible predecessors of Γ(2, 1^{(n−1)}). Continuing in this manner, the only games Γ_{n,n+3} that can be predecessors of some Γ_{n,n+2} ∈ N_{n,n+2} are the following:

Γ(6, 1^{(n−3)}, 0^{(2)}), Γ(4, 3, 1^{(n−4)}, 0^{(2)}), Γ(4, 2, 1^{(n−3)}, 0), Γ(3, 3, 1^{(n−3)}, 0), Γ(3, 2, 1^{(n−2)}),

Γ(5, 2, 1^{(n−4)}, 0^{(2)}), Γ(5, 1^{(n−2)}, 0), Γ(3, 3, 2, 1^{(n−5)}, 0^{(2)}), Γ(3, 2, 2, 1^{(n−4)}, 0), Γ(2, 2, 2, 1^{(n−3)}).

Clearly, these are the only possible candidates for inclusion in P_{n,n+3}. However, we observe that

⋄ each of Γ(6, 1^{(n−3)}, 0^{(2)}), Γ(4, 3, 1^{(n−4)}, 0^{(2)}), Γ(4, 2, 1^{(n−3)}, 0), Γ(3, 3, 2, 1^{(n−5)}, 0^{(2)}) and Γ(3, 2, 2, 1^{(n−4)}, 0) is a predecessor of Γ(4, 2, 1^{(n−4)}, 0^{(2)});

⋄ Γ(3, 2, 1^{(n−2)}) is a predecessor of Γ(2, 2, 1^{(n−2)});

⋄ Γ(5, 2, 1^{(n−4)}, 0^{(2)}) is a predecessor of Γ(5, 2, 1^{(n−5)}, 0^{(3)});

⋄ Γ(2, 2, 2, 1^{(n−3)}) is a predecessor of Γ(2, 2, 2, 1^{(n−4)}, 0).

The four indicated resultant games are P -games since they are not in N_{n,n+2}. As a result, each of the eight indicated predecessor games is in N_{n,n+3}. This leaves only two of the 10 aforementioned candidates, yielding P_{n,n+3} = {Γ(5, 1^{(n−2)}, 0), Γ(3, 3, 1^{(n−3)}, 0)} as desired.

(ii) We next observe that N_{n,n+4} is comprised of all games Γ_{n,n+4} that can result in some Γ_{n,n+3} ∈ P_{n,n+3} after a single pebbling move. It is straightforward to see that N_{n,n+4} consists of the following eight games: Γ(7, 1^{(n−3)}, 0^{(2)}), Γ(5, 3, 1^{(n−4)}, 0^{(2)}), Γ(5, 2, 1^{(n−3)}, 0), Γ(4, 3, 1^{(n−3)}, 0), Γ(4, 2, 1^{(n−2)}), Γ(3, 3, 3, 1^{(n−5)}, 0^{(2)}), Γ(3, 3, 2, 1^{(n−4)}, 0) and Γ(3, 2, 2, 1^{(n−3)}).

Below we list all games Γ_{n,n+5} that can result in some Γ_{n,n+4} ∈ N_{n,n+4} after a single pebbling move:

Γ(9, 1^{(n−4)}, 0^{(3)}), Γ(7, 3, 1^{(n−5)}, 0^{(3)}), Γ(7, 2, 1^{(n−4)}, 0^{(2)}), Γ(6, 3, 1^{(n−4)}, 0^{(2)}), Γ(6, 2, 1^{(n−3)}, 0),

Γ(5, 5, 1^{(n−5)}, 0^{(3)}), Γ(5, 4, 1^{(n−4)}, 0^{(2)}), Γ(5, 3, 3, 1^{(n−6)}, 0^{(3)}), Γ(5, 3, 2, 1^{(n−5)}, 0^{(2)}), Γ(5, 2, 2, 1^{(n−4)}, 0), Γ(4, 3, 3, 1^{(n−5)}, 0^{(2)}), Γ(4, 3, 2, 1^{(n−4)}, 0), Γ(7, 1^{(n−2)}, 0), Γ(5, 3, 1^{(n−3)}, 0),

Γ(5, 2, 1^{(n−2)}), Γ(4, 4, 1^{(n−3)}, 0), Γ(4, 2, 2, 1^{(n−3)}), Γ(3, 3, 3, 1^{(n−4)}, 0), Γ(3, 3, 2, 1^{(n−3)}), Γ(6, 1^{(n−1)}),

Γ(4, 3, 1^{(n−2)}), Γ(3, 3, 3, 3, 1^{(n−7)}, 0^{(3)}), Γ(3, 3, 3, 2, 1^{(n−6)}, 0^{(2)}), Γ(3, 3, 2, 2, 1^{(n−5)}, 0),

Γ(3, 2, 2, 2, 1^{(n−4)}).

Note that these are the only candidates for inclusion in P_{n,n+5}. However, we see that ⋄ each of Γ(9, 1^{(n−4)}, 0^{(3)}), Γ(7, 3, 1^{(n−5)}, 0^{(3)}) and Γ(7, 2, 1^{(n−4)}, 0^{(2)}) is a predecessor of

Γ(7, 2, 1^{(n−5)}, 0^{(3)});

⋄ each of Γ(6, 3, 1^{(n−4)}, 0^{(2)}), Γ(6, 2, 1^{(n−3)}, 0), Γ(5, 4, 1^{(n−4)}, 0^{(2)}), Γ(5, 3, 2, 1^{(n−5)}, 0^{(2)}) and Γ(5, 2, 2, 1^{(n−4)}, 0) is a predecessor of Γ(6, 2, 1^{(n−4)}, 0^{(2)});

⋄ each of Γ(5, 5, 1^{(n−5)}, 0^{(3)}) and Γ(5, 3, 3, 1^{(n−6)}, 0^{(3)}) is a predecessor of Γ(5, 3, 2, 1^{(n−6)}, 0^{(3)});

⋄ each of Γ(4, 3, 3, 1^{(n−5)}, 0^{(2)}), Γ(4, 3, 2, 1^{(n−4)}, 0), Γ(3, 3, 3, 2, 1^{(n−6)}, 0^{(2)}) and Γ(3, 3, 2, 2, 1^{(n−5)}, 0) is a predecessor of Γ(4, 3, 2, 1^{(n−5)}, 0^{(2)});

⋄ each of Γ(7, 1^{(n−2)}, 0), Γ(5, 3, 1^{(n−3)}, 0), and Γ(4, 3, 1^{(n−2)}) is a predecessor of Γ(5, 1^{(n−1)});

⋄ each of Γ(5, 2, 1^{(n−2)}), Γ(3, 3, 3, 1^{(n−4)}, 0) and Γ(3, 3, 2, 1^{(n−3)}) is a predecessor of Γ(3, 3, 1^{(n−2)});

⋄ each of Γ(4, 4, 1^{(n−3)}, 0), Γ(4, 2, 2, 1^{(n−3)}) and Γ(3, 2, 2, 2, 1^{(n−4)}) is a predecessor of Γ(4, 2, 2, 1^{(n−4)}, 0);

⋄ Γ(3, 3, 3, 3, 1^{(n−7)}, 0^{(3)}) is a predecessor of Γ(4, 3, 3, 1^{(n−6)}, 0^{(3)}).

The eight indicated resultant games are P -games since they are not in N_{n,n+4}. Hence, the 24 indicated predecessors of these games must be in N_{n,n+5}. This leaves only Γ(6, 1^{(n−1)}) as the surviving candidate, i.e., P_{n,n+5} = {Γ(6, 1^{(n−1)})}.

(iii) Note that (ii) implies N_{n,n+6} = {Γ(8, 1^{(n−2)}, 0), Γ(6, 3, 1^{(n−3)}, 0), Γ(5, 3, 1^{(n−2)})}, since Γ(8, 1^{(n−2)}, 0), Γ(6, 3, 1^{(n−3)}, 0) and Γ(5, 3, 1^{(n−2)}) are the only predecessors of Γ(6, 1^{(n−1)}). A further computation now reveals that the only possible predecessors of a game in N_{n,n+6} are the following:

Γ(10, 1^{(n−3)}, 0^{(2)}), Γ(8, 3, 1^{(n−4)}, 0^{(2)}), Γ(8, 2, 1^{(n−3)}, 0), Γ(7, 2, 1^{(n−2)}), Γ(6, 5, 1^{(n−4)}, 0^{(2)}),

Γ(6, 3, 3, 1^{(n−5)}, 0^{(2)}), Γ(6, 3, 2, 1^{(n−4)}, 0), Γ(6, 2, 2, 1^{(n−3)}), Γ(5, 5, 1^{(n−3)}, 0), Γ(5, 3, 3, 1^{(n−4)}, 0),

Γ(5, 3, 2, 1^{(n−3)}), Γ(7, 3, 1^{(n−3)}, 0), Γ(5, 4, 1^{(n−2)}), Γ(4, 3, 3, 1^{(n−3)}).

Once again, the games listed above are the only candidates for inclusion in P_{n,n+7}. However,

⋄ each of Γ(10, 1^{(n−3)}, 0^{(2)}), Γ(8, 3, 1^{(n−4)}, 0^{(2)}) and Γ(8, 2, 1^{(n−3)}, 0) is a predecessor of Γ(8, 2, 1^{(n−4)}, 0^{(2)});

⋄ each of Γ(7, 2, 1^{(n−2)}) and Γ(6, 2, 2, 1^{(n−3)}) is a predecessor of Γ(7, 2, 1^{(n−3)}, 0);

⋄ each of Γ(6, 5, 1^{(n−4)}, 0^{(2)}), Γ(6, 3, 3, 1^{(n−5)}, 0^{(2)}) and Γ(6, 3, 2, 1^{(n−4)}, 0) is a predecessor of Γ(6, 3, 2, 1^{(n−5)}, 0^{(2)});

⋄ each of Γ(5, 5, 1^{(n−3)}, 0), Γ(5, 3, 3, 1^{(n−4)}, 0), Γ(5, 3, 2, 1^{(n−3)}) and Γ(7, 3, 1^{(n−3)}, 0) is a predecessor of Γ(5, 3, 2, 1^{(n−4)}, 0);

⋄ each of Γ(5, 4, 1^{(n−2)}) and Γ(4, 3, 3, 1^{(n−3)}) is a predecessor of Γ(4, 3, 2, 1^{(n−3)}).

The five indicated resultant games are P -games since they are not in N_{n,n+6}. Thus the 14 indicated predecessors are all N-games, which means there are no surviving candidates for inclusion in P_{n,n+7}. We conclude that P_{n,n+7} = ∅ as claimed.

Lemma 7. For all even integers n ≥ 6, P_{n,n+1} = {Γ(2, 1^{(n−1)})} implies P_{n+2,n+3} = {Γ(2, 1^{(n+1)})}.

Proof. If Γ_{n+2,n+1} has at least three zeros in its assignment, then by Lemma 4, this Γ_{n+2,n+1} shares the same winning positions as a Γ_{n,n+1} with at least one zero. Since P_{n,n+1} = {Γ(2, 1^{(n−1)})}, it follows that any game Γ_{n+2,n+1} with at least three zeros in its assignment is an N-game. In other words, Γ_{n+2,n+1} ∈ P_{n+2,n+1} only if Γ_{n+2,n+1} has at most two zeros in its assignment, i.e.,

P_{n+2,n+1} ⊆ {Γ(2, 1^{(n−1)}, 0^{(2)}), Γ(1^{(n+1)}, 0)}.

However, Γ(2, 1^{(n−1)}, 0^{(2)}) is an N-game since it is a predecessor of the P -game Γ(1^{(n)}, 0^{(2)}), thus P_{n+2,n+1} = {Γ(1^{(n+1)}, 0)}. Moreover, N_{n+2,n+2} = {Γ(3, 1^{(n−1)}, 0^{(2)}), Γ(2, 1^{(n)}, 0)} since Γ(3, 1^{(n−1)}, 0^{(2)}) and Γ(2, 1^{(n)}, 0) are the only predecessors of Γ(1^{(n+1)}, 0).

We are up to the point of determining P_{n+2,n+3}. Here, the candidates are precisely those Γ_{n+2,n+3} that are predecessors of a game from N_{n+2,n+2}. We list all such candidates below:

\begin{matrix}Γ(5, 1^{(n−2)}, 0^{(3)}), Γ(3, 3, 1^{(n−3)}, 0^{(3)}), Γ(3, 2, 1^{(n−2)}, 0^{(2)}), Γ(2, 2, 1^{(n−1)}, 0), Γ(4, 1^{(n−1)}, 0^{(2)}), \\ Γ(3, 1^{(n)}, 0), Γ(2, 1^{(n+1)}). \end{matrix}

However, we observe that

⋄ each of Γ(5, 1^{(n−2)}, 0^{(3)}), Γ(3, 3, 1^{(n−3)}, 0^{(3)}) and Γ(3, 2, 1^{(n−2)}, 0^{(2)}) is a predecessor of Γ(3, 2, 1^{(n−3)}, 0^{(3)});

⋄ each of Γ(2, 2, 1^{(n−1)}, 0) and Γ(4, 1^{(n−1)}, 0^{(2)}) is a predecessor of Γ(2, 2, 1^{(n−2)}, 0^{(2)});

⋄ Γ(3, 1^{(n)}, 0) is a predecessor of Γ(1^{(n+2)}).

The three indicated resultant games are P -games since they are not in N_{n+2,n+2}. It follows that the six indicated predecessors are all N-games. As a result, Γ(2, 1^{(n+1)}) is the only surviving candidate, whence P_{n+2,n+3} = {Γ(2, 1^{(n+1)})} as desired.

We are now prepared to prove Theorem 1(e).

Proof of Theorem 1(e). We leave verification that P_{6,7} = {Γ(2, 1^{(5)})} as an exercise for the reader. By Lemma 7, we have P_{n,n+1} = {Γ(2, 1^{(n−1)})} for all even n ≥ 6. It now follows from Lemma 6 that P_{n,n+7} = ∅ for all even n ≥ 6. Thus, every Γ_{n,n+7} is an N-game, from which it follows that every Γ_{n,m} is an N-game if and only if m is odd, m ≥ n + 7.

A Appendix: Mathematica Program

(*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}]

References

[1] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, CRC Press, 2001.

[2] M. Lind, E. Fiorini, and A. Woldar, On properties of pebble assignment graphs, submitted, 2020.

[3] G. Isaak and M. Prudente, Two-player pebbling on diameter 2 graphs, Int. J. Game

   Theory (2021), https://doi.org/10.1007/s00182-021-00766-0.

[4] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, https://oeis.

   org.

2010 Mathematics Subject Classification: Primary 91A46; Secondary 91A43, 91A05. Keywords: pebbling game, impartial game, pebble assignment, N-game, P -game.

(Concerned with sequence \underline{A340631}.)

Received March 25 2021; revised version received May 4 2021. Published in Journal of Integer Sequences, May 18 2021.

Return to Journal of Integer Sequences home page.