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.

13, 21, 15, 21, 17, 25, 21, 29, 25, 33, 29, 37, 33, 41, 37, 45, 41, 49, 45, 53, 49, 57

Offset

3,1

Comments

A (3,2) pebbling move involves removing 3 pebbles from a vertex in a simple graph and placing 2 pebbles on an adjacent vertex.

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.

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=3..24.

E. Fiorini, M. Lind, A. Woldar, and T. W. H. Wong,Characterizing Winning Positions in the Impartial Two-Player Pebbling Game on Complete Graphs, Journal of Integer Sequences, 24(6), 2021.

Formula

a(n) = 2n+3 when n >= 7 is odd (conjectured).

a(n) = 2n+9 when n >= 6 is even (conjectured).

Example

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.
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.

Mathematica

remove = 3; add = 2;
(*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 pebbling move; only work for n>=3.*)
pebblemoves[config_] := Block[{n, temp},
    n = Length[config];
    temp = Table[config, {i, n (n - 1)}] +
        Permutations[Join[{-remove, add}, Table[0, {i, n - 2}]]];
    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]]],
                If[i > (remove - add), Plist[[n, i - (remove - add)]], {}]]],
            AppendTo[Plist[[n, i]], tuples[[j]]]], {j, Length[tuples]}],
    {i, Length[Plist[[n]]] + 1, m}]; Plist[[n, m]]];
Do[m = 1; While[plist[n, m] != {}, m++]; Print[" n=", n, " m=", m], {n, 3, 24}]

Crossrefs

Cf. A340631, A084964, A346197.

Sequence in context: A278470 A066515 A166656 * A230498 A260747 A032693

Adjacent sequences: A346398 A346399 A346400 * A346402 A346403 A346404

Keyword

nonn,more

Author

Kayla Barker, Mia DeStefano, Eugene Fiorini, Michael Gohn, Joe Miller, Jacob Roeder, Wing Hong Tony Wong, Jul 15 2021

Status

approved