cp's OEIS Frontend

A346401 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, 2) pebbling game.

%I A346401 #15 Jul 23 2021 02:25:12
%S A346401 13,21,15,21,17,25,21,29,25,33,29,37,33,41,37,45,41,49,45,53,49,57
%N A346401 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, 2) pebbling game.
%C A346401 A (3,2) pebbling move involves removing 3 pebbles from a vertex in a simple graph and placing 2 pebbles on an adjacent vertex.
%C A346401 A two-player impartial (3,2) pebbling game involves two players alternating (3,2) pebbling moves. The first player unable to make a move loses.
%D A346401 E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, CRC Press, 2001.
%H A346401 E. Fiorini, M. Lind, A. Woldar, and T. 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, 24(6), 2021.
%F A346401 a(n) = 2n+3 when n >= 7 is odd (conjectured).
%F A346401 a(n) = 2n+9 when n >= 6 is even (conjectured).
%e A346401 For n=6, a(6)=21 is the least number of pebbles for which every (3,2) game on K_6 is a next-player winning game regardless of assignment.
%e A346401 For n=7, a(7)=17 is the least number of pebbles for which every (3,2) game on K_7 is a next-player winning game regardless of assignment.
%t A346401 remove = 3; add = 2;
%t A346401 (*Given n and m,list all possible assignments.*)
%t A346401 alltuples[n_, m_] := IntegerPartitions[m + n, {n}] - 1;
%t A346401 (*Given an assignment,list all resultant assignments after one pebbling move; only work for n>=3.*)
%t A346401 pebblemoves[config_] := Block[{n, temp},
%t A346401     n = Length[config];
%t A346401     temp = Table[config, {i, n (n - 1)}] +
%t A346401         Permutations[Join[{-remove, add}, Table[0, {i, n - 2}]]];
%t A346401     temp = Select[temp, Min[#] >= 0 &];
%t A346401     temp = ReverseSort[DeleteDuplicates[ReverseSort /@ temp]]];
%t A346401 (*Given n and m,list all assignments that are P-games.*)
%t A346401 Plist = {};
%t A346401 plist[n_, m_] :=  Block[{index, tuples},
%t A346401     While[Length[Plist] < n, index = Length[Plist];
%t A346401         AppendTo[Plist, {{Join[{1}, Table[0, {i, index}]]}}]];
%t A346401     Do[AppendTo[Plist[[n]], {}]; tuples = alltuples[n, i];
%t A346401         Do[If[Not[IntersectingQ[pebblemoves[tuples[[j]]],
%t A346401                 If[i > (remove - add), Plist[[n, i - (remove - add)]], {}]]],
%t A346401             AppendTo[Plist[[n, i]], tuples[[j]]]], {j, Length[tuples]}],
%t A346401     {i, Length[Plist[[n]]] + 1, m}]; Plist[[n, m]]];
%t A346401 Do[m = 1; While[plist[n, m] != {}, m++]; Print[" n=", n, " m=", m], {n, 3, 24}]
%Y A346401 Cf. A340631, A084964, A346197.
%K A346401 nonn,more
%O A346401 3,1
%A A346401 _Kayla Barker_, _Mia DeStefano_, _Eugene Fiorini_, _Michael Gohn_, _Joe Miller_, _Jacob Roeder_, _Wing Hong Tony Wong_, Jul 15 2021