login
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.
12
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,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
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.
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
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
Cf. A084964.
Sequence in context: A273216 A367002 A070411 * A367003 A167224 A175483
KEYWORD
nonn,easy
STATUS
approved