A347637 Table read by ascending antidiagonals. T(n, k) 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 (k+1, k) pebbling game. T(n, k) for n >= 5 and k >= 1.

7, 13, 15, 9, 21, 21, 15, 17, 35, 27, 11, 25, 25, 37, 33, 17, 21, 41, 33, 59, 39, 13, 29, 31, 45, 41, 53

Offset

5,1

Comments

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

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

T(3, k) = A016921(k) for k >= 0. The proof will appear in a paper that is currently in preparation.

It is conjectured that T(4, k) for odd k>=3 is infinite, so we start with n = 5.

T(5, k) = A346197(k) for k >= 1.

T(n, 1) = A340631(n) for n >= 3.

T(n, 2) = A346401(n) for n >= 3.

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=5..31.

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

The data is organized in a table beginning with row n = 5 and column k = 1. The data is read by ascending antidiagonals. The formula binomial(n + k - 5, 2) + k converts the indices from table form to sequence form.
The table T(n, k) begins:
[n/k]  1   2   3   4   5   6  ...
---------------------------------
[ 5]   7, 15, 21, 27, 33, 39, ...
[ 6]  13, 21, 35, 37, 59, 53, ...
[ 7]   9, 17, 25, 33, 41, 51, ...
[ 8]  15, 25, 41, 45, 61, ...
[ 9]  11, 21, 31, 41, 51, ...
[10]  17, 29, 45, 53, 71, ...
[11]  13, 25, 37, 49, 61, ...
[12]  19, 33, 51, ...
[13]  15, 29, 43, ...
[14]  21, 37, ...
[15]  17, 33, ...
[16]  23, 41, ...

Mathematica

(* m represents number of vertices in the complete graph. Each pebbling move removes k+1 pebbles from a vertex and adds k pebbles to an adjacent vertex. *)
Do[(* Given m and a, list all possible assignments with a pebbles. *)
alltuples[m_, a_] := IntegerPartitions[a + m, {m}] - 1;
(* Given an assignment, list all resultant assignments after one pebbling move; only works for m>=3. *)
pebblemoves[config_] :=
  Block[{m, temp}, m = Length[config];
   temp = Table[config, {i, m (m - 1)}] +
     Permutations[Join[{-(k + 1), k}, Table[0, {i, m - 2}]]];
   temp = Select[temp, Min[#] >= 0 &];
   temp = ReverseSort[DeleteDuplicates[ReverseSort /@ temp]]];
(* Given m and a, list all assignments that are P-games. *)
Plist = {};
plist[m_, a_] :=
  Block[{index, tuples},
   While[Length[Plist] < m, index = Length[Plist];
    AppendTo[Plist, {{Join[{1}, Table[0, {i, index}]]}}]];
   Do[AppendTo[Plist[[m]], {}]; tuples = alltuples[m, i];
    Do[If[
      Not[IntersectingQ[pebblemoves[tuples[[j]]],
        If[i > 2, Plist[[m, i - 1]], {}]]],
      AppendTo[Plist[[m, i]], tuples[[j]]]], {j, Length[tuples]}], {i,
      Length[Plist[[m]]] + 1, a}]; Plist[[m, a]]];
(* Given m, print out the minimum a such that there are no P-games with a pebbles *)
Do[a = 1; While[plist[m, a] != {}, a++];
  Print["k=", k, " m=", m, " a=", a], {m, 5, 10}], {k, 1, 6}]

Crossrefs

Cf. A340631, A346197, A346401.

Sequence in context: A269163 A260482 A328254 * A191976 A135054 A076701

Adjacent sequences: A347634 A347635 A347636 * A347638 A347639 A347640

Keyword

nonn,more,tabl

Author

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

Status

approved