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

Author

Gabrielle Demchak, Eugene Fiorini, Michael J. Herrera, Samuel Murray, Rhaldni Sayaman, Brittany Shelton and Wing Hong Tony Wong, Mar 14 2023

Keywords

• nonn
• more

Comments

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.

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.

Crossrefs

Cf. A340631, A346197, A346401, A347637.

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