OFFSET
3,1
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.
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).
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).
EXAMPLE
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.
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}]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved