A340631 a(n) is the minimum number of pebbles such that any assignment of those pebbles on a complete graph with n vertices is a next-player winning game in the two-player impartial pebbling game.

7, 23, 7, 13, 9, 15, 11, 17, 13, 19, 15, 21, 17, 23, 19, 25, 21, 27, 23, 29, 25, 31, 27, 33, 29, 35, 31, 37, 33, 39, 35, 41, 37, 43, 39, 45, 41, 47, 43, 49, 45, 51, 47, 53, 49, 55, 51, 57, 53, 59, 55, 61, 57, 63, 59, 65, 61, 67, 63, 69, 65, 71, 67, 73, 69, 75

Offset: 3

Author

Eugene Fiorini, Max C. Lind, Andrew Woldar, Wing Hong Tony Wong, Jan 13 2021

Keywords

• nonn
• easy

Comments

A move in an impartial two-player pebbling game consists of removing two pebbles from a vertex and adding one pebble to an adjacent vertex. The winning player is the one who makes the final allowable move. We start at n = 3 because we have shown a(2) does not exist.

Examples

			For n=3, a(3)=7 is the least number of pebbles for which every game in a next-player winning game regardless of assignment.
		

References

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

Links

• Michael De Vlieger, Table of n, a(n) for n = 3..10000
• Kayla Barker, Mia DeStefano, Eugene Fiorini, Michael Gohn, Joe Miller, Jacob Roeder, and Tony W. H. Wong, Generalized Impartial Two-player Pebbling Games on K_3 and C_4, J. Int. Seq. (2024) Vol. 27, Issue 5, Art. No. 24.5.8. See p. 3.
• Eugene Fiorini, Max Lind, Andrew Woldar, and Tony W. H. Wong, Characterizing Winning Positions in the Impartial Two-Player Pebbling Game on Complete Graphs, J. Int. Seq., Vol. 24 (2021), Article 21.6.4.
• Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Crossrefs

Cf. A084964.

Programs

Mathematica

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

Formula

For n>2, a(2n-1)=2n+1, a(2n)=a(2n+5)=2n+7.

G.f.: x^3*(12*x^4-10*x^3-23*x^2+16*x+7)/((x+1)*(x-1)^2).

For n>=5, a(n) = 2*A084964(n+4) - 1 = 2*A084964(n+2) + 1. - Hugo Pfoertner, Jan 14 2021