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,1

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.

References

E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, CRC Press, 2001.

Links

Table of n, a(n) for n=4..20.

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.

Example

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.

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

Crossrefs

Cf. A340631, A346197, A346401, A347637.

Sequence in context: A299558 A348624 A340744 * A291471 A276992 A008685

Adjacent sequences: A361312 A361313 A361314 * A361316 A361317 A361318

Keyword

nonn,more

Author

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

Status

approved