login
a(n) is the minimum number of pebbles such that any assignment of those pebbles on K_5 is a next-player winning game in the two-player impartial (n+1,n) pebbling game.
9

%I #21 Jun 28 2024 01:17:30

%S 7,15,21,27,33,39,47,53,59,67,73,79,87,93,99,107,113,119,127,133,139

%N a(n) is the minimum number of pebbles such that any assignment of those pebbles on K_5 is a next-player winning game in the two-player impartial (n+1,n) pebbling game.

%C For n>0, an (n+1,n) pebbling move involves removing n+1 pebbles from a vertex in a simple graph and placing n pebbles on an adjacent vertex.

%C A two-player impartial (n+1,n) pebbling game involves two players alternating (n+1,n) pebbling moves. The first player unable to make a move loses.

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

%H Kayla Barker, Mia DeStefano, Eugene Fiorini, Michael Gohn, Joe Miller, Jacob Roeder, and Tony W. H. Wong, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Wong/wong43.html">Generalized Impartial Two-player Pebbling Games on K_3 and C_4</a>, J. Int. Seq. (2024) Vol. 27, Issue 5, Art. No. 24.5.8. See p. 4.

%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>, Journal of Integer Sequences, (2021) Vol. 24, Issue 6, Art. No. 21.6.4.

%e For n=1, a(1)=7 is the least number of pebbles for which every (2,1) game on K_5 is a next-player winning game regardless of assignment.

%t Do[remove = k + 1; add = k;

%t (*Given n and m, list all possible assignments.*)

%t alltuples[n_, m_] := IntegerPartitions[m + n, {n}] - 1;

%t (*Given an assignment, list all resultant assignments after one pebbling move; only work for n>=3.*)

%t pebblemoves[config_] := Block[{n, temp},

%t n = Length[config];

%t temp = Table[config, {i, n (n - 1)}] +

%t Permutations[Join[{-remove, add}, Table[0, {i, n - 2}]]];

%t temp = Select[temp, Min[#] >= 0 &];

%t temp = ReverseSort[DeleteDuplicates[ReverseSort /@ temp]]];

%t (*Given n and m, list all assignments that are P-games.*)

%t Plist = {};

%t plist[n_, m_] := Block[{index, tuples},

%t While[Length[Plist] < n, index = Length[Plist];

%t AppendTo[Plist, {{Join[{1}, Table[0,{i,index}]]}}]];

%t Do[AppendTo[Plist[[n]], {}]; tuples = alltuples[n, i];

%t Do[If[Not[IntersectingQ[pebblemoves[tuples[[j]]],

%t If[i > (remove - add), Plist[[n, i - (remove - add)]], {}]]],

%t AppendTo[Plist[[n, i]], tuples[[j]]]], {j, Length[tuples]}],

%t {i, Length[Plist[[n]]] + 1, m}]; Plist[[n, m]]];

%t Do[m = 1; While[plist[n, m] != {}, m++]; Print[" k=", k, " m=", m], {n, 5, 5}],

%t {k, 1, 21}]

%Y Cf. A340631, A084964.

%K nonn,more

%O 1,1

%A _Kayla Barker_, _Mia DeStefano_, _Eugene Fiorini_, _Michael Gohn_, _Joe Miller_, _Jacob Roeder_, _Wing Hong Tony Wong_, Jul 09 2021