cp's OEIS Frontend

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.

%I A361315 #50 Dec 16 2023 13:10:32
%S A361315 31,26,19,17,17,19,21,23,25,27,29,31,33,35,37,39,41
%N 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.
%C A361315 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 A361315 E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, CRC Press, 2001.
%H A361315 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 A361315 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 A361315 (*Given n and m, list all possible assignments.*)alltuples[n_, m_] := IntegerPartitions[m + n, {n}] - 1;
%t A361315 (*Given an assignment, list all resultant assignments after one (3;1,1)-pebbling move; only work for n>=3.*)
%t A361315 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 A361315 (*Given n and m, list all assignments that are P-games.*)
%t A361315 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 A361315 (*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 A361315  Print["n=", n, " m=", m], {n, 4, 20}]
%Y A361315 Cf. A340631, A346197, A346401, A347637.
%K A361315 nonn,more
%O A361315 4,1
%A A361315 _Gabrielle Demchak_, _Eugene Fiorini_, _Michael J. Herrera_, _Samuel Murray_, Rhaldni Sayaman, Brittany Shelton and _Wing Hong Tony Wong_, Mar 14 2023