A361315 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 (3;1,1) pebbling game.
31, 26, 19, 17, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41
Offset: 4
Examples
For n = 4, a(4) = 31 is the least number of pebbles for which every game is 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
- 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.
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 (3;1,1)-pebbling move; only work for n>=3.*) pebblemoves[config_] := Block[{n, temp}, n = Length[config]; temp = Table[config, {i, n (n - 1) (n - 2)/2}] + Permutations[Join[{-3, 1, 1}, Table[0, {i, n - 3}]]]; 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, 4, 20}]
Comments