login
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.
2
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
Kayla Barker, Mia DeStefano, Eugene Fiorini, Michael Gohn, Joe Miller, Jacob Roeder, and Tony W. H. Wong, Generalized Impartial Two-player Pebbling Games on K_3 and C_4, J. Int. Seq. (2024) Vol. 27, Issue 5, Art. No. 24.5.8. See p. 4.
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
KEYWORD
nonn,more,tabl
STATUS
approved