Generalized Impartial Two-player Pebbling Games on K_{3} and C_{4}

Kayla Barker Mathematics Program Stockton University

101 Vera King Ferris Dr

Galloway, NJ 08205

USA

kaylaabarker5@gmail.com

Mia DeStefano Dept. of Mathematics and Statistics Vassar College 124 Raymond Ave Poughkeepsie, NY 12604 USA

                             mdestefano@vassar.edu

Eugene Fiorini

DIMACS Rutgers University

96 Frelinghuysen Road Piscataway, NJ 08854

USA

efiorini@dimacs.rutgers.edu

Michael Gohn Dept. of Mathematics and Computer Sci. DeSales University 2755 Station Avenue Center Valley, PA 18034 USA

                               mg7785@desales.edu

Joe Miller Department of Mathematics

Iowa State University 411 Morrill Rd Ames, IA 50011

USA

jmiller0@iastate.edu

Jacob Roeder Dept. of Mathematics and Physics Trine University 1 University Ave Angola, IN 46703 USA

                            jwroeder19@my.trine.edu

Tony W. H. Wong Department of Mathematics Kutztown University of Pennsylvania 15200 Kutztown Road Kutztown, PA 19530 USA

           wong@kutztown.edu

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

1 Introduction

Given a simple graph G on vertices v_{1}, v_{2}, …, v_{n}, every vertex v_{i} is assigned with a number of pebbles, specified by a nonnegative integer a_{i} for each 1 ≤ i ≤ n. Fiorini et al. [2] describe an impartial two-player (2 : 1)-pebbling game, denoted by Γ_{G}^{(2:1)}(a_{1}, a_{2}, …, a_{n}), where players A and B take turns (player A taking the first turn) to make a (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 impartial two-player (k + 1 : k)-pebbling game Γ_{G}^{(k+1:k)}(a_{1}, a_{2}, …, 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 terminating game, or every available move results in an N-game. Interested readers may refer to Berlekamp, Conway, and Guy [1] for more information on two-player impartial games.

Let 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, G_{G,m}^{(k+1:k)} can be partitioned into P_{G,m}^{(k+1:k)} and N_{G,m}^{(k+1:k)}, the sets of all P - games and N-games in G_{G,m}^{(k+1:k)}, respectively. Furthermore, if there exists a positive integer m such that G_{G,m}^{(k+1:k)} = N_{G,m}^{(k+1:k)}, then G_{G,m+2r}^{(k+1:k)} = N_{G,m+2r}^{(k+1:k)} and G_{G,m+2r+1}^{(k+1:k)} = 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 G_{G,m}^{(k+1:k)} = N_{G,m}^{(k+1:k)}, which we denote by m^{(k+1:k)}(G). Fiorini et al. [2] established the following result when k = 1 and G = K_{n}.

Theorem 1.

(a) If m is even, then N_{K_{2},m}^{(2:1)} = {Γ_{K_{2}}^{(2:1)}(a_{1}, a_{2}) : a_{1} + a_{2} = m and a_{1} ≢ a_{2} (mod 3)}; if m is odd, then N_{K_{2},m}^{(2:1)} = {Γ_{K_{2}}^{(2:1)}(a_{1}, a_{2}) : a_{1} + a_{2} = m and a_{1} ≡ a_{2} (mod 3)}. Hence, m^{(2:1)}(K_{2}) does not exist.

(b) m^{(2:1)}(K_{3}) = 7.

(c) m^{(2:1)}(K_{4}) = 23.

(d) For all odd integers n ≥ 5, we have m^{(2:1)}(K_{n}) = n + 2.

(e) For all even integers n ≥ 6, we have m^{(2:1)}(K_{n}) = n + 7.

In this paper, we expand our investigation on m^{(k+1:k)}(K_{n}) when k > 1. Through computation using Mathematica (see Appendix A 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.

n k 1  2  3  4  5  6
3  7  13  19  25  31  37
4  23  21  35  49
5  7  15  21  27  33  39
6  13  21  35  37  59  53
7  9  17  25  33  41  51
8  15  25  41  45  61  65
9  11  21  31  41  51  61
10  17  29  45  53  71  77
Table 1: Values of m^{(k+1:k)}(K_{n}) for 1 ≤ k ≤ 6 and 3 ≤ n ≤ 10.

The first column of Table 1 corresponds to the result given in Theorem 1. This sequence appears in the On-Line Encyclopedia of Integer Sequences (OEIS) as \underline{A340631} [5]. On the other hand, the sequence given by the first row appears in the OEIS as \underline{A016921} [5]. This sequence is a result of the following theorem, which will be proved in Section 2. Theorem 2. For all positive integers k, we have m^{(k+1:k)}(K_{3}) = 6k + 1.

The empty cells in the row corresponding to n = 4 are due to the following conjecture, suggested by our computational data. Conjecture 3. For all odd integers k ≥ 3, the value m^{(k+1:k)}(K_{4}) does not exist.

Since m^{(k+1:k)}(K_{4}) is conjectured to be nonexistent for odd k ≥ 3, only the data corresponding to n ≥ 5 in Table 1 appears in the OEIS (see \underline{A346197} and \underline{A347637} [5]).

We also study m^{(k+1:k)}(G) when G is not a complete graph. In particular, we prove in Section 3 that m^{(2:1)}(C_{4}) does not exist. In fact, we fully determine how G_{C_{4},m}^{(2:1)} is partitioned into P_{C_{4},m}^{(2:1)} and 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 echo pebbling move. Next, for all γ = Γ_{G}^{(k+1:k)}(a_{1}, a_{2}, …, a_{n}), we let |γ| = a_{1} + a_{2} + ⋯ + a_{n} denote the total number of pebbles in this game. Furthermore, the game γ_{i+1} is called a successor of γ_{i} = Γ_{G}^{(k+1:k)}(a_{1}, a_{2}, …, a_{n}) if γ_{i+1} is a resultant game by performing one (k +1 : k)-pebbling move on γ_{i}, and γ_{i} is called a predecessor of γ_{i+1}.

2 The investigation on m^{(k+1:k)}(K_{3})

In this section, since the focus is G = K_{3} with (k + 1 : k)-pebbling moves, we will abbreviate the notation G_{K_{3},m}^{(k+1:k)}, P_{K_{3},m}^{(k+1:k)}, N_{K_{3},m}^{(k+1:k)}, and Γ_{K_{3}}^{(k+1:k)}(a_{1}, a_{2}, a_{3}) as G_{m}, P_{m}, N_{m}, and Γ(a_{1}, a_{2}, a_{3}), respectively. Furthermore, due to the symmetry of K_{3}, the game Γ(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 Γ{a_{1}, a_{2}, a_{3}}. For convenience, we always assume a_{1} ≥ a_{2} ≥ a_{3}.

The technique we utilize to prove Theorem 2 is to show that P_{3,6k−1} = Γ{4k + 1, k − 1, k − 1}. We demonstrate this via a sequence of lemmas. The first three lemmas prove that every game in Γ{4k + 1, k − 1, k − 1} is a P -game.

Lemma 4. Every game in Γ{2k + 3, 0, 0} is a P -game.

Proof. Consider γ_{0} ∈ Γ{2k + 3, 0, 0}. Every successor γ_{1} of γ_{0} is in Γ{k + 2, k, 0}, and player B can make one pebbling move on γ_{1} to obtain γ_{2} ∈ Γ{k, k, 1}. Clearly γ_{2} is a P -game, so γ_{0} is also a P -game.

Lemma 5. Let 0 ≤ ℓ ≤ k − 1 and ℓ_{1} ≤ ℓ_{2} be nonnegative integers such that ℓ_{1} + ℓ_{2} = ℓ. Then every game in Γ{2k − 1 − ℓ, k − ℓ_{1}, k − ℓ_{2}} is a P -game.

Proof. Consider γ_{0} ∈ Γ{2k − 1, k, k}. Every successor of γ_{0} is in Γ{2k, k, k − 2}, and the subsequent echo pebbling move by player B leads to γ_{2} ∈ Γ{2k − 2, k, k − 1}. If player B repeats the strategy of echoing player A’s every move, then for every 0 ≤ ℓ ≤ k − 1, we have γ_{2ℓ} ∈ Γ{2k − 1 − ℓ, k − ℓ_{1}, k − ℓ_{2}}, where ℓ_{1} ≤ ℓ_{2} and ℓ_{1} + ℓ_{2} = ℓ. Note that all vertices in γ_{2(k−1)} have at most k pebbles, which implies that γ_{2(k−1)} is a P -game. Since player B has a strategy to bring every γ_{2ℓ} ∈ Γ{2k − 1 − ℓ, k − ℓ_{1}, k − ℓ_{2}} to a P -game, the game γ_{2ℓ} is also a P -game.

Lemma 6. Every game in Γ{4k + 1, k − 1, k − 1} is a P -game.

Proof. Consider γ_{0} ∈ Γ{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 γ_{2k−2+2ℓ} ∈ Γ{3k +2−ℓ, k −1−ℓ, 0} for some 0 ≤ ℓ ≤ k −1 and player A makes one pebbling move to obtain γ_{2k−1+2ℓ} ∈ Γ{2k +1−ℓ, k, k −1−ℓ}. In this situation, player B can make one pebbling move to obtain γ_{2k+2ℓ} ∈ Γ{2k −1−ℓ, k, k −ℓ}, which is a P -game by Lemma 5.

The next two lemmas together show that γ ∈ G_{m} is a P game if m ≤ 6k is even and no vertex contains more than m/2 pebbles.

Lemma 7. Consider γ_{2ℓ} ∈ Γ{a_{1}, a_{2}, a_{3}}, where |γ_{2ℓ}| = a_{1} + a_{2} + a_{3} = 6k − 2ℓ for some 0 ≤ ℓ ≤ 2k − 1 and k + 1 ≤ a_{1} ≤ 3k − ℓ. Then regardless of the move by player A, player B can obtain γ_{2ℓ+2} ∈ Γ{a′′_{1}, a′′_{2}, a′′_{3}}, where a′′_{1} ≤ 3k − ℓ − 1.

Proof. If a_{3} = 0, then γ_{2ℓ} ∈ Γ{3k − ℓ, 3k − ℓ, 0}. In this case, the game γ_{2ℓ+1} is in Γ{4k − ℓ, 2k − ℓ − 1, 0} or

\begin{cases}Γ\{3k − ℓ, 2k − ℓ − 1, k\}, & if 0 ≤ ℓ ≤ k − 1; \\ Γ\{3k − ℓ, k, 2k − ℓ − 1\}, & if k ≤ ℓ ≤ 2k − 1, \end{cases}

and player B can make one pebbling move to obtain γ_{2ℓ+2} in

\begin{cases}Γ\{3k − ℓ − 1, 2k − ℓ − 1, k\}, & if 0 ≤ ℓ ≤ k − 1; \\ Γ\{3k − ℓ − 1, k, 2k − ℓ − 1\}, & if k ≤ ℓ ≤ 2k − 1, \end{cases}

thus establishing our assertion.

Now suppose a_{3} ≥ 1. If a_{1} ≤ 3k − ℓ − 1, then regardless of the move by player A, player B is going to perform an echo pebbling move to obtain γ_{2ℓ+2} ∈ Γ{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} ≤ a_{1} ≤ 3k − ℓ − 1.

It remains to consider the case where a_{1} = 3k − ℓ and a_{2} ≤ 3k − ℓ − 1. If player A makes one pebbling move that involves the vertex with 3k − ℓ pebbles, then player B is going to perform an echo pebbling move to obtain γ_{2ℓ+2}. Otherwise, player A obtains γ_{2ℓ+1} ∈ Γ{3k − ℓ, a′_{2}, a′_{3}} with a′_{2} + a′_{3} = 3k − ℓ − 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} ≥ k. This implies that a′_{3} ≤ 2k − ℓ − 1. Hence, player B can make one pebbling move to obtain γ_{2ℓ+2} ∈ Γ{a′′_{1}, a′′_{2}, a′′_{3}} such that {a′′_{1}, a′′_{2}, a′′_{3}} = {2k − ℓ − 1, a′_{2}, a′_{3} + k}. In both scenarios, the resultant γ_{2ℓ+2} satisfies the desired condition.

Lemma 8. Consider γ_{2ℓ} ∈ Γ{a_{1}, a_{2}, a_{3}}, where |γ_{2ℓ}| = 6k − 2ℓ for some 0 ≤ ℓ ≤ 2k − 1 and a_{1} ≤ 3k − ℓ. Then γ_{2ℓ} is a P -game.

Proof. Suppose player B inductively applies the strategy described in Lemma 7. Under this strategy, if player A obtains γ_{2ℓ+1} for some 0 ≤ ℓ ≤ 2k − 1, then player B always has an available pebbling move to obtain γ_{2ℓ+2}. Hence, player B can ensure that the game either terminates at γ_{2ℓ} for some 0 ≤ ℓ ≤ 2k − 1 or does not terminate at γ_{4k−2}. If γ_{4k−2} is not a terminating game, then according to Lemma 7, player B can obtain γ_{4k} ∈ Γ{a_{1}^{∗}, a_{2}^{∗}, a_{3}^{∗}} with a_{1}^{∗} ≤ 3k − (2k − 1) − 1 = k. This implies that γ_{4k} is a terminating game. Therefore, player B has a winning strategy, meaning that γ_{2ℓ} is a P -game.

The remaining preliminary results before the proof of Theorem 2 show that every γ ∈ G_{6k−1} \ Γ{4k + 1, k − 1, k − 1} is an N-game.

Lemma 9. Consider γ_{2ℓ−1} ∈ Γ{a_{1}, a_{2}, a_{3}}, where |γ_{2ℓ−1}| = 6k−2ℓ+1 for some 1 ≤ ℓ ≤ 2k−1, a_{1} ≤ 4k − ℓ + 1, and a_{3} ≤ 2k − ℓ. Then γ_{2ℓ−1} is an N-game.

Proof. Note that a_{2} ≤ ⌊(6k − 2ℓ + 1)/2⌋ = 3k − ℓ. If player A makes a pebbling move from the vertex with a_{1} pebbles to the vertex with a_{3} pebbles, then γ_{2ℓ} is in Γ{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 ≤ 4k − ℓ + 1 − (k + 1) = 3k − ℓ and a_{3} + k ≤ 2k − ℓ + k = 3k − ℓ. By Lemma 8, the game γ_{2ℓ} is a P -game, so γ_{2ℓ−1} is an N-game.

Corollary 10. Consider γ_{1} ∈ Γ{a_{1}, a_{2}, a_{3}}, where |γ_{1}| = 6k − 1 and a_{1} ≤ 4k. Then γ_{1} is an N-game.

Proof. Note that a_{3} ≤ ⌊(6k −1)/3⌋ = 2k −1. Hence, the conditions in Lemma 9 are satisfied with ℓ = 1.

Lemma 11. Consider γ_{2ℓ−1} ∈ Γ{a_{1}, a_{2}, 0}, where |γ_{2ℓ−1}| = 6k−2ℓ+1 for some 1 ≤ ℓ ≤ k−1 and a_{2} ≤ k. Then γ_{2ℓ−1} is an N-game.

Proof. Player A can make a pebbling move to obtain γ_{2ℓ} ∈ Γ{a_{1} − k − 1, k, a_{2}}, and player B can only obtain γ_{2ℓ+1} in Γ{a_{1} − 2k − 2, 2k, a_{2}} or Γ{a_{1} − 2k − 2, a_{2} + k, k}. Since

a_{1} − 2k − 2 ≤ (6k − 2ℓ + 1) − 2k − 2 = 4k − 2ℓ − 1 ≤ 4k − (ℓ + 1) + 1

and a_{2} ≤ k ≤ 2k − (ℓ + 1), Lemma 9 applies and γ_{2ℓ+1} is an N-game, which implies our assertion.

Lemma 12. Consider γ_{1} ∈ Γ{a_{1}, a_{2}, a_{3}}, where |γ_{1}| = 6k − 1 and a_{1} ≥ 4k + 1. If γ_{1} ∉ Γ{4k + 1, k − 1, k − 1}, then γ_{1} is an N-game.

Proof. Without loss of generality, let γ_{1} = Γ(a_{1}, a_{2}, a_{3}). Note that

a_{3} ≤ ((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} ≤ k − 2.

Suppose that a_{2} ≤ k. If a_{3} = 0, then γ_{1} is an N-game by Lemma 11, so we may assume that a_{3} ≥ 1. To start the game, player A can make a pebbling move to obtain γ_{2} = Γ(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 ℓ be the maximum nonnegative integer such that for each positive integer ℓ̃≤ ℓ, player B makes a pebbling move from v_{3} at the game γ_{2ℓ̃} to obtain γ_{2ℓ̃+1}. Note that if ℓ = 0, then player B must have made a pebbling move from v_{1} at the game γ_{2} to obtain γ_{3}. After each pebbling move by player B to obtain γ_{2ℓ̃+1}, player A can always perform an echo pebbling move to obtain γ_{2ℓ̃+2} since a_{1} − k − 1 > a_{2} ≥ a_{3}. With this strategy, player A can obtain γ_{2ℓ+2} = Γ(a_{1} − k − 1 − ℓ_{1}, a_{2} − ℓ_{2}, a_{3} + k − ℓ) for some nonnegative integers ℓ_{1} and ℓ_{2} such that ℓ_{1} +ℓ_{2} = ℓ. Note that a_{3} +k −ℓ ≥ k, so ℓ ≤ a_{3}. Now by the definition of ℓ, the next pebbling move by player B is from v_{1}, so γ_{2ℓ+3} is either Γ(a_{1}−2k−2−ℓ_{1}, a_{2}+k−ℓ_{2}, a_{3}+k−ℓ) or Γ(a_{1} − 2k − 2 − ℓ_{1}, a_{2} − ℓ_{2}, a_{3} + 2k − ℓ). Since

• a_{1}−2k−2−ℓ_{1} = (6k−1−a_{2}−a_{3})−2k−2−ℓ_{1} ≤ 4k−a_{3}−3 ≤ 4k−ℓ−3 < 4k−(ℓ+2)+1,

• a_{3} + k − ℓ ≤ k − 2 + k − ℓ = 2k − (ℓ + 2), and

• a_{2} − ℓ_{2} = (6k − 1 − a_{1} − a_{3}) − ℓ_{2} ≤ (6k − 1 − (4k + 1) − ℓ) − ℓ_{2} ≤ 2k − (ℓ + 2),

Lemma 9 implies that γ_{2ℓ+3} = γ_{2(ℓ+2)−1} is an N-game. Therefore, player A has a winning strategy and γ_{1} is an N-game.

Next, suppose that a_{2} ≥ k +1. To start the game, player A can make a pebbling move to obtain γ_{2} = Γ(a_{1}+k, a_{2}−k−1, a_{3}). Since (a_{2}−k−1)+a_{3} ≤ (6k−1)−(4k+1)−k−1 = k−3, player B can only make a pebbling move from v_{1} to obtain γ_{3}. From here, we can inductively define γ_{2t̃+1} for each positive integer t̃ as follows. Let γ_{i} = Γ(a_{1}^{(i)}, a_{2}^{(i)}, a_{3}^{(i)}) for positive integers i. If either a_{2}^{(2t̃+1)} or a_{3}^{(2t̃+1)} is at least k + 1, then player A can perform an echo pebbling move to obtain γ_{2t̃+2}. After that, player B can only make a pebbling move from v_{1} to obtain γ_{2t̃+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 ∈ {2, 3} be such that a_{i}^{(2t+1)} ≤ a_{5−i}^{(2t+1)}. Note that a_{5−i}^{(2t+1)} = k and a_{i}^{(2t+1)} ≤ (6k − 1) − (4k + 1) − k − t = k − 2 − t, thus t ≤ k − 2. At this stage, player A can make a pebbling move from v_{1} to v_{i} to obtain γ_{2t+2}, where a_{1}^{(2t+2)} = a_{1} − t − (k + 1), a_{i}^{(2t+2)} ≤ 2k − 2 − t, and a_{5−i}^{(2t+2)} = k.

Now we can inductively define γ_{2t+2τ̃} for each positive integer τ̃ as follows. At the game γ_{2t+2τ̃}, if player B makes a pebbling move from v_{i} to obtain γ_{2t+2τ̃+1}, then player A can always perform an echo pebbling move to obtain γ_{2t+2τ̃+2} since a_{1} − t − (k + 1) > k > k − 2 − t. Let τ be the smallest positive integer such that at γ_{2t+2τ}, player B makes a pebbling move from v_{1} to obtain γ_{2t+2τ+1}. Note that a_{i}^{(2t+2τ−1)} = a_{i}^{(2t+1)} − (τ − 1) ≤ k − 2 − t − (τ − 1), and thus t + τ + 1 ≤ k. Then

a_{1}^{(2t+2τ+1)} ≤ a_{1}^{(2t+2)} − (k + 1)
= (6k − 1) − a_{2} − a_{3} − t − 2(k + 1)
≤ (6k − 1) − (k + 1) − t − 2(k + 1)
= 3k − 4 − t < 4k − (t + τ + 1) − 1,

and

min (a_{2}^{(2t+2τ+1)}, a_{3}^{(2t+2τ+1)}) ≤ max(2k − 1 − t − τ, k) = 2k − (t + τ + 1).

As a result, γ_{2t+2τ+1} is an N-game by Lemma 9.

We are now ready to prove Theorem 2.

Proof of Theorem 2. Note that P_{6k−1} = Γ{4k + 1, k − 1, k − 1} by Lemma 6, Corollary 10, and Lemma 12. Hence, N_{6k} = Γ{3k + 1, 2k, k − 1} since they are the only predecessors of the games in Γ{4k + 1, k − 1, k − 1}. The predecessors of the games in Γ{3k + 1, 2k, k − 1} are given by

Γ{4k + 2, k, k − 1} ∪ Γ{3k + 1, 2k + 1, k − 1} ∪ Γ{2k + 1, 2k, 2k} ∪ Γ{3k + 1, 2k, k}. (1)

The set of games in (1) contains the only candidates for inclusion in P_{6k+1}. However,

• the games in Γ{4k + 2, k, k − 1} ∪ Γ{3k + 1, 2k + 1, k − 1} are predecessors of the games in Γ{3k + 1, 2k − 1, k}, which are P -games since they are not in N_{6k};

• the games in Γ{2k + 1, 2k, 2k} ∪ Γ{3k + 1, 2k, k} are predecessors of the games in Γ{3k, 2k, k}, which are also P -games.

Therefore, all the games in (1) are not in P_{6k+1}. This implies that P_{6k+1} = ∅, and m = 6k+1 is the minimum integer such that G_{m} = N_{m}.

3 Classifying the (2 : 1)-pebbling games on C_{4}

The focus of this section is G = C_{4} with (2 : 1)-pebbling moves, so we will abbreviate the notation G_{C_{4},m}^{(2:1)}, P_{C_{4},m}^{(2:1)}, N_{C_{4},m}^{(2:1)}, and Γ_{C_{4}}^{(2:1)}(a_{0}, a_{1}, a_{2}, a_{3}) as G_{m}, P_{m}, N_{m}, and Γ(a_{0}, a_{1}, a_{2}, a_{3}), respectively. We will fully determine the sets P_{m} and 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 ∈ {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+ϵ} for some j ∈ {0, 1, 2, 3} and ϵ ∈ {−1, 1}. Then several response moves by their opponent are as follows. A reverse rotational move is a pebbling move by the opponent from v_{j} to v_{j−ϵ} (Figure 1), a rotational symmetric move is from v_{j+2} to v_{j−ϵ} (Figure 2), and a reflectional move is from v_{j−ϵ} to v_{j+2} (Figure 3).

Next, we define five subsets of ⋃_{m∈ℤ^{+}} G_{m} based on the number pebbles modulo 3 on each vertex.

• X_{aaab} = {Γ(a_{0}, a_{1}, a_{2}, a_{3}) : a_{i} ≡ a_{i+1} ≡ a_{i+2} ≢ a_{i−1} (mod 3) for some i ∈ {0, 1, 2, 3}},

• X_{abab} = {Γ(a_{0}, a_{1}, a_{2}, a_{3}) : (a_{0} ≡ a_{2}) ≢ (a_{1} ≡ a_{3}) (mod 3)}, v_{j} v_{j+ϵ} v_{j+2} v_{j−ϵ} Initial move

Response move

Figure 1: Reverse rotational move. v_{j} v_{j+ϵ} v_{j+2} v_{j−ϵ} Initial move

Response move

Figure 2: Rotational symmetric move. v_{j} v_{j+ϵ} v_{j+2} v_{j−ϵ} Initial move

Response move

Figure 3: Reflectional move.

• X_{aabc} = {Γ(a_{0}, a_{1}, a_{2}, a_{3}) : a_{i} ≡ a_{i+1} (mod 3) and a_{i}, a_{i+2}, a_{i−1} are distinct modulo 3 for some i ∈ {0, 1, 2, 3}},

• X_{abac} = {Γ(a_{0}, a_{1}, a_{2}, a_{3}) : a_{i} ≡ a_{i+2} (mod 3) and a_{i}, a_{i+1}, a_{i−1} are distinct modulo 3 for some i ∈ {0, 1}}, and

• X̂_{aabb} = {Γ(a_{0}, a_{1}, a_{2}, a_{3}) : a_{i} ≡ a_{i+1} (mod 3) and a_{i+2} ≡ a_{i−1} (mod 3) for some i ∈ {0, 1}}. The hat notation indicates X̂_{aabb} includes games with a_{i} ≡ a_{i+2} (mod 3) and those with a_{i} ≢ a_{i+2} (mod 3).

We further define four subsets of ⋃_{m∈ℤ^{+}} G_{m} based on the number pebbles modulo 4 on each vertex.

• Y_{aabc} = {Γ(a_{0}, a_{1}, a_{2}, a_{3}) : a_{i+2} ≡ a_{i} + 2 (mod 4) and a_{i+1} ≡ a_{i−1} + 1 (mod 4) for some i ∈ {0, 1, 2, 3}}.

• Ŷ_{abac} = {Γ(a_{0}, a_{1}, a_{2}, a_{3}) : a_{i} ≡ a_{i+2} (mod 4) and a_{i+1} ≡ a_{i−1} + 1 (mod 4) for some i ∈ {0, 1, 2, 3}}. The hat indicates Ŷ_{abac} includes games with a_{i} ≡ a_{i+1} (mod 4), those with a_{i} ≡ a_{i−1} (mod 4), and those with distinct a_{i}, a_{i+1}, a_{i−1} modulo 4.

• Ŷ_{abab} = {Γ(a_{0}, a_{1}, a_{2}, a_{3}) : a_{0} ≡ a_{2} (mod 4) and a_{1} ≡ a_{3} (mod 4)}. The hat indicates Ŷ_{abab} includes games with a_{0} ≡ a_{1} (mod 4) and those with a_{0} ≢ a_{1} (mod 4).

• (Ŷ_{abab})^{c} = {Γ(a_{0}, a_{1}, a_{2}, a_{3}) : a_{0} + a_{1} + a_{2} + a_{3} is even and Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∉ Ŷ_{abab}}.

Remark 13. Here are some quick observations on the sets defined above.

(a) The sets X_{aaab}, X_{abab}, X_{aabc}, X_{abac}, X̂_{aabb} form a partition of ⋃_{m∈ℤ^{+}} G_{m}.

(b) The sets Y_{aabc} and Ŷ_{abac} form a partition of ⋃_{m∈ℤ^{+}} G_{2m−1}, while Ŷ_{abab} and (Ŷ_{abab})^{c} form a partition of ⋃_{m∈ℤ^{+}} G_{2m}.

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

Lemma 14. Each of X_{aaab}, X_{abab}, X_{aabc}, X_{abac}, and X̂_{aabb} is invariant after a pebbling move by one player followed by a rotational symmetric or reflectional move by their opponent.

Proof. Suppose one player makes a pebbling move on Γ(a_{0}, a_{1}, a_{2}, a_{3}) to obtain a_{j} − 2 and a_{j+ϵ}+1 pebbles on vertices v_{j} and v_{j+ϵ}, respectively, for some j ∈ {0, 1, 2, 3} and ϵ ∈ {−1, 1}. A subsequent rotational symmetric move by their opponent results in a_{j+2} − 2 and a_{j−ϵ} + 1 pebbles on vertices v_{j+2} and v_{j−ϵ}, respectively, and a reflectional move results in a_{j+2} +1 and a_{j−ϵ} − 2 pebbles on vertices v_{j+2} and v_{j−ϵ}, 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 ≤ j ≤ 3. Therefore, each of X_{aaab}, X_{abab}, X_{aabc}, X_{abac}, and X̂_{aabb} is invariant after the specified response move by the opponent.

Lemma 15. Both sets X̂_{aabb} ∪ X_{abac} and X_{aaab} ∪ X_{abab} ∪ X_{aabc} are closed under pebbling moves.

Proof. We first show that X̂_{aabb} ∪ X_{abac} is closed under pebbling moves. Consider a pebbling game Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ X̂_{aabb} ∪ X_{abac} with one pebbling move from v_{j} to v_{j+ϵ} for some j ∈ {0, 1, 2, 3} and ϵ ∈ {−1, 1}, and let the resultant pebbling game be Γ(a′_{0}, a′_{1}, a′_{2}, a′_{3}). Suppose that Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ X̂_{aabb} with a_{i} ≡ a_{i+1} (mod 3) and a_{i+2} ≡ a_{i−1} (mod 3) for some i ∈ {0, 1}. If a_{j} ≡ a_{j+ϵ} (mod 3), then a′_{j} ≡ a_{j} + 1 ≡ a_{j+ϵ} + 1 ≡ a′_{j+ϵ} (mod 3) and a′_{j+2} ≡ a_{j+2} ≡ a_{j−ϵ} ≡ a′_{j−ϵ} (mod 3), thus Γ(a′_{0}, a′_{1}, a′_{2}, a′_{3}) ∈ X̂_{aabb}. If a_{j} ≢ a_{j+ϵ} (mod 3), then Table 2 gives the remaining possible outcomes of Γ(a′_{0}, a′_{1}, a′_{2}, a′_{3}) after one pebbling move.

{a_{i}, a_{i+2}} (mod 3) (a_{j}, a_{j+ϵ}) (mod 3) (a′_{j}, a′_{j+ϵ}, a′_{j+2}, a′_{j−ϵ}) (mod 3) Γ(a′_{0}, a′_{1}, a′_{2}, a′_{3})
{0, 1} (0, 1) (1, 2, 1, 0) X_{abac}
(1, 0)  (2, 1, 0, 1)
{0, 2} (0, 2) (1, 0, 2, 0)
(2, 0)  (0, 1, 0, 2)
{1, 2} (1, 2) (2, 0, 2, 1)
(2, 1)  (0, 2, 1, 2)

Table 2: Resultant games after one pebbling move from X̂_{aabb} if a_{j} ≢ a_{j+ϵ} (mod 3).

Next, suppose that Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ X_{abac} with a_{i} ≡ a_{i+2} (mod 3) and a_{i}, a_{i+1}, a_{i−1} being distinct modulo 3 for some i ∈ {0, 1}. Table 3 gives all possible outcomes of Γ(a′_{0}, a′_{1}, a′_{2}, a′_{3}) after one pebbling move. By exhausting all possible resultant games Γ(a′_{0}, a′_{1}, a′_{2}, a′_{3}), we see that X̂_{aabb} ∪ X_{abac} is closed under pebbling moves.

a_{i} (mod 3) (a_{j}, a_{j+ϵ}) (mod 3) (a′_{j}, a′_{j+ϵ}, a′_{j+2}, a′_{j−ϵ}) (mod 3) Γ(a′_{0}, a′_{1}, a′_{2}, a′_{3})
0 (0, 1) (1, 2, 0, 2) X_{abac}
(1, 0)  (2, 1, 2, 0)
(0, 2) (1, 0, 0, 1) X̂_{aabb}
(2, 0)  (0, 1, 1, 0)
1 (1, 0) (2, 1, 1, 2) X̂_{aabb}
(0, 1)  (1, 2, 2, 1)
(1, 2) (2, 0, 1, 0) X_{abac}
(2, 1)  (0, 2, 0, 1)
2 (2, 0) (0, 1, 2, 1) X_{abac}
(0, 2)  (1, 0, 1, 2)
(2, 1) (0, 2, 2, 0) X̂_{aabb}
(1, 2)  (2, 0, 0, 2)

Table 3: Resultant games after one pebbling move from X_{abac}.

To show that X_{aaab} ∪ X_{abab} ∪ X_{aabc} is closed under pebbling moves, we suppose by way of contradiction that there exists a pebbling game Γ(a_{0}, a_{1}, a_{2}, a_{3}) in X_{aaab} ∪ X_{abab} ∪ X_{aabc} and a pebbling move from v_{j} to v_{j+ϵ} for some j ∈ {0, 1, 2, 3} and ϵ ∈ {−1, 1} such that the resultant game Γ(a′_{0}, a′_{1}, a′_{2}, a′_{3}) is not in X_{aaab} ∪ X_{abab} ∪ X_{aabc}. By Remark 13(a), we have Γ(a′_{0}, a′_{1}, a′_{2}, a′_{3}) in X̂_{aabb} ∪ X_{abac}. Now we consider the game Γ(a_{0} + 2, a_{1} + 2, a_{2} + 2, a_{3} + 2) in X_{aaab}∪X_{abab}∪X_{aabc}. After the pebbling move from v_{j} to v_{j+ϵ}, a rotational symmetric response move from v_{j+2} to v_{j−ϵ} yields a resultant game in X_{aaab} ∪ X_{abab} ∪ X_{aabc} by Lemma 14. This contradicts that X̂_{aabb}∪X_{abac} is closed under pebbling moves since Γ(a′_{0}+2, a′_{1}+2, a′_{2}+2, a′_{3}+2) is in X̂_{aabb} ∪ X_{abac}.

We now begin classifying all (2 : 1)-pebbling games on C_{4} as P -games and N-games.

Theorem 16. A game Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ X̂_{aabb} ∪ X_{abac} is a P -game if and only if a_{0} + a_{1} + a_{2} + a_{3} is even.

Proof. If a_{0} + a_{1} + a_{2} + a_{3} = 0, then Γ(0, 0, 0, 0) is the only possibility and is a P -game. There is no game in X̂_{aabb} ∪ X_{abac} with a_{0} + a_{1} + a_{2} + a_{3} = 1. If a_{0} + a_{1} + a_{2} + a_{3} = 2, then (a_{i}, a_{i+1}, a_{i+2}, a_{i−1}) = (1, 1, 0, 0) for some i ∈ {0, 1, 2, 3}, and Γ(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}) ∈ {(3, 0, 0, 0), (0, 1, 0, 2)} for some i ∈ {0, 1, 2, 3}, and Γ(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}) ∈ {(2, 2, 0, 0), (1, 1, 1, 1), (1, 0, 1, 2)} for some i ∈ {0, 1, 2, 3}, and it is not difficult to verify that Γ(a_{0}, a_{1}, a_{2}, a_{3}) is a P -game. Now assume that for some integer k ≥ 4, Γ(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 ≥ 5, there exists j ∈ {0, 1, 2, 3} such that a_{j} ≥ 2. Hence, there is at least one pebbling move on Γ(a_{0}, a_{1}, a_{2}, a_{3}), and the resultant pebbling game Γ(a′_{0}, a′_{1}, a′_{2}, a′_{3}) is in X̂_{aabb} ∪ X_{abac} by Lemma 15. By the induction hypothesis, Γ(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 Γ(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.

Theorem 17. Every game Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ Ŷ_{abab} is a P -game.

Proof. For Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ Ŷ_{abab}, if there does not exist j ∈ {0, 1, 2, 3} such that a_{j} ≥ 2, then player A does not have a move and thus Γ(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+ϵ} for some j ∈ {0, 1, 2, 3} and ϵ ∈ {−1, 1}, where a_{j} ≥ 2. Since a_{j+2} ≡ a_{j} (mod 4), we have max(a_{j} − 2, a_{j+2}) ≥ 2. As a result, if a_{j} − 2 ≥ 2, then player B can apply a reverse rotational move from v_{j} to v_{j−ϵ}; if a_{j+2} ≥ 2, then player B can apply a rotational symmetric move from v_{j+2} to v_{j−ϵ}. In both cases, player B has a strategy to ensure that the resultant game returns to Ŷ_{abab}. Therefore, Γ(a_{0}, a_{1}, a_{2}, a_{3}) can be proved to be a P -game inductively.

Theorem 18. Every game Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ (X_{abab} ∪ X_{aabc} ∪ X_{aaab}) ∩ Ŷ_{abac} is a P -game.

Proof. For Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ (X_{abab} ∪ X_{aabc} ∪ X_{aaab}) ∩ Ŷ_{abac}, if there does not exist j ∈ {0, 1, 2, 3} such that a_{j} ≥ 2, then player A does not have a move and thus Γ(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+ϵ} for some j ∈ {0, 1, 2, 3} and ϵ ∈ {−1, 1}, where a_{j} ≥ 2.

First, consider the case when a_{j+2} ≡ a_{j} (mod 4). In this case, max(a_{j} − 2, a_{j+2}) ≥ 2. If a_{j} −2 ≥ 2, then player B can apply the strategy of a reverse rotational move from v_{j} to v_{j−ϵ}; if a_{j+2} ≥ 2, then player B can apply the strategy of a rotational symmetric move from v_{j+2} to v_{j−ϵ}. In both cases, player B has a strategy to ensure that the resultant game returns to Ŷ_{abac}.

Next, consider the case when a_{j+2} ≡ a_{j} ± 1 (mod 4). If max(a_{j} − 2, a_{j+2}) ≥ 2, then player B has the same strategy as above to obtain a resultant game in Ŷ_{abac}. Otherwise, (a_{j}, a_{j+2}) ∈ {(2, 1), (3, 0)} and a_{j+1} ≡ a_{j−1} (mod 4). Note that Γ(2, 0, 1, 0) and Γ(3, 0, 0, 0) are not in X_{abab} ∪ X_{aabc} ∪ X_{aaab}, so (a_{j+1}, a_{j−1}) ≠ (0, 0). If a_{j+ϵ} ≥ 1, then when (a_{j}, a_{j+2}) = (2, 1), player B can apply an echo pebbling move from v_{j+ϵ} to v_{j}, and when (a_{j}, a_{j+2}) = (3, 0), player B can make a pebbling move from v_{j+ϵ} to v_{j+2}. Otherwise, if a_{j+ϵ} = 0, then a_{j−ϵ} ≥ 4, so when (a_{j}, a_{j+2}) = (2, 1), player B can make a pebbling move from v_{j−ϵ} to v_{j}, and when (a_{j}, a_{j+2}) = (3, 0), player B can apply a reflectional move from v_{j−ϵ} to v_{j+2}. In all cases, player B has a strategy to ensure that the resultant game returns to Ŷ_{abac}. By Lemma 15, this resultant game is in (X_{abab} ∪ X_{aabc} ∪ X_{aaab}) ∩ Ŷ_{abac}. Therefore, the game Γ(a_{0}, a_{1}, a_{2}, a_{3}) can be proved to be a P -game inductively.

Theorems 16, 17, and 18 are summarized in Table 4. Recall from Remark 13(b) that |γ| = a_{0} + a_{1} + a_{2} + a_{3} is even if γ ∈ Ŷ_{abab} ∪ (Ŷ_{abab})^{c} and |γ| is odd if γ ∈ Ŷ_{abac} ∪ Y_{aabc}.

Theorem 19. Every game Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ Y_{aabc} is an N-game.

Proof. For Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ Y_{aabc}, let i ∈ {0, 1, 2, 3} and ϵ ∈ {−1, 1} such that

a_{i} ≡ a_{i+ϵ} (mod 4) and a_{i+2} ≡ a_{i} + 2 (mod 4).

X̂_{aabb} X_{abac} X_{abab} X_{aabc} X_{aaab}
Ŷ_{abab} P P P P P
(Ŷ_{abab})^{c} P  P
Ŷ_{abac}  N  N  P  P  P
Y_{aabc}  N  N

Table 4: Classification of C_{4} (2 : 1)-pebbling games on C_{4} due to Theorems 16, 17, and 18.

By the definition of Y_{aabc}, we have a_{i−ϵ} ≡ a_{i+ϵ} ± 1 (mod 4). Note that max(a_{i}, a_{i+2}) ≥ 2. If a_{i−ϵ} ≡ a_{i+ϵ} + 1 (mod 4), then player A can make a pebbling move from v_{i} or v_{i+2} to v_{i+ϵ}; otherwise, if a_{i−ϵ} ≡ a_{i+ϵ} − 1 (mod 4), then player A can make a pebbling move from v_{i} or v_{i+2} to v_{i−ϵ}. In both cases, player A has a strategy to obtain a resultant game in Ŷ_{abab}, which is a P -game by Theorem 17. Therefore, the game Γ(a_{0}, a_{1}, a_{2}, a_{3}) is an N-game.

Theorem 20. Every game Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ (X_{abab} ∪ X_{aabc} ∪ X_{aaab}) ∩ (Ŷ_{abab})^{c} is an N-game.

Proof. Let Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ (X_{abab} ∪ X_{aabc} ∪ X_{aaab}) ∩ (Ŷ_{abab})^{c}. By the definition of (Ŷ_{abab})^{c}, there exists i ∈ {0, 1} such that a_{i} ≢ a_{i+2} (mod 4). If a_{i+2} ≡ a_{i} + 2 (mod 4), then max(a_{i}, a_{i+2}) ≥ 2, and player A can make a pebbling move from v_{i} to v_{i+ϵ} or from v_{i+2} to v_{i+ϵ}. Otherwise, we have a_{i+2} ≡ a_{i}±1 (mod 4). This implies that a_{i−ϵ} ≡ a_{i+ϵ}+1 (mod 4) for some ϵ ∈ {−1, 1} since a_{0}+a_{1}+a_{2}+a_{3} is even. If max(a_{0}, a_{1}, a_{2}, a_{3}) ≤ 1, then (a_{i}, a_{i+ϵ}, a_{i+2}, a_{i−ϵ}) is in {(0, 0, 1, 1), (1, 0, 0, 1)}, contradicting that Γ(a_{0}, a_{1}, a_{2}, a_{3}) ∈ X_{abab} ∪ X_{aabc} ∪ X_{aaab}. Hence, either max(a_{i}, a_{i+2}) ≥ 2 or max(a_{i+ϵ}, a_{i−ϵ}) ≥ 2. Without loss of generality, assume that max(a_{i}, a_{i+2}) ≥ 2. Then player A can make a pebbling move from v_{i} to v_{i+ϵ} or from v_{i+2} to v_{i+ϵ}. In both cases, player A has a strategy to obtain a resultant game in Ŷ_{abac}. By Lemma 15, this resultant game is in (X_{abab} ∪ X_{aabc} ∪ X_{aaab}) ∩ Ŷ_{abac}, which is a P -game by Theorem 18. Therefore, the game Γ(a_{0}, a_{1}, a_{2}, a_{3}) is an N-game.

Theorems 16 through 20 completely classify all (2 : 1)-pebbling games on C_{4} into P -games and N-games. To conclude, we summarize the results in Table 5.

X̂_{aabb} X_{abac} X_{abab} X_{aabc} X_{aaab}
Ŷ_{abab}  P  P  P  P  P
(Ŷ_{abab})^{c} P  P  N  N  N
Ŷ_{abac}  N  N  P  P  P
Y_{aabc}  N  N  N  N  N

Table 5: Complete classification of (2 : 1)-pebbling games on C_{4}.

4 Future directions

As mentioned in Section 1, among the computational results given in Table 1, 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.

A Appendix: Computer code

(*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>=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[#] >= 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["k=", k, " n=", n, " m=", m], {n, 5, 10}], {k, 1, 6}]

References

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

[2] E. Fiorini, M. Lind, A. Woldar, and T. W. H. Wong, Characterizing winning positions in the impartial two-player pebbling game on complete graphs, J. Integer Sequences 24 (2021), Article 21.6.4.

[3] M. Lind, E. Fiorini, and A. Woldar, On properties of pebble assignment graphs, Graphs Combin. 38 (2022), Article 45.

[4] 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.

[5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org, 2024.

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

(Concerned with sequences \underline{A016921}, \underline{A340631}, \underline{A346197}, \underline{A347637}.)

Received June 4 2023; revised versions received June 9 2023; May 14 2024. Published in Journal of Integer Sequences, June 3 2024.

Return to Journal of Integer Sequences home page.