%I #50 Dec 16 2023 13:10:32
%S 31,26,19,17,17,19,21,23,25,27,29,31,33,35,37,39,41
%N 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.
%C A (3;1,1) move in an impartial two-player pebbling game consists of removing three pebbles from a vertex and adding a pebble to each of two distinct adjacent vertices. The winning player is the one who makes the final allowable move. We start at n = 4 because we have shown that a(3) does not exist while a(2) is clearly undefined.
%D E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, CRC Press, 2001.
%H Eugene Fiorini, Max Lind, Andrew Woldar, and Tony W. H. Wong, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Wong/wong31.html ">Characterizing Winning Positions in the Impartial Two-Player Pebbling Game on Complete Graphs</a>, J. Int. Seq., Vol. 24 (2021), Article 21.6.4.
%e 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.
%t (*Given n and m, list all possible assignments.*)alltuples[n_, m_] := IntegerPartitions[m + n, {n}] - 1;
%t (*Given an assignment, list all resultant assignments after one (3;1,1)-pebbling move; only work for n>=3.*)
%t 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]]];
%t (*Given n and m, list all assignments that are P-games.*)
%t 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]]];
%t (*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++];
%t Print["n=", n, " m=", m], {n, 4, 20}]
%Y Cf. A340631, A346197, A346401, A347637.
%K nonn,more
%O 4,1
%A _Gabrielle Demchak_, _Eugene Fiorini_, _Michael J. Herrera_, _Samuel Murray_, Rhaldni Sayaman, Brittany Shelton and _Wing Hong Tony Wong_, Mar 14 2023