|
%I #36 Jun 28 2024 01:28:32
%S 7,13,15,9,21,21,15,17,35,27,11,25,25,37,33,17,21,41,33,59,39,13,29,
%T 31,45,41,53
%N 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.
%C 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.
%C 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.
%C T(3, k) = A016921(k) for k >= 0. The proof will appear in a paper that is currently in preparation.
%C It is conjectured that T(4, k) for odd k>=3 is infinite, so we start with n = 5.
%C T(5, k) = A346197(k) for k >= 1.
%C T(n, 1) = A340631(n) for n >= 3.
%C T(n, 2) = A346401(n) for n >= 3.
%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>, J. Int. Seq., Vol. 24 (2021), Article 21.6.4.
%e 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.
%e The table T(n, k) begins:
%e [n/k] 1 2 3 4 5 6 ...
%e ---------------------------------
%e [ 5] 7, 15, 21, 27, 33, 39, ...
%e [ 6] 13, 21, 35, 37, 59, 53, ...
%e [ 7] 9, 17, 25, 33, 41, 51, ...
%e [ 8] 15, 25, 41, 45, 61, ...
%e [ 9] 11, 21, 31, 41, 51, ...
%e [10] 17, 29, 45, 53, 71, ...
%e [11] 13, 25, 37, 49, 61, ...
%e [12] 19, 33, 51, ...
%e [13] 15, 29, 43, ...
%e [14] 21, 37, ...
%e [15] 17, 33, ...
%e [16] 23, 41, ...
%t (* 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. *)
%t Do[(* Given m and a, list all possible assignments with a pebbles. *)
%t alltuples[m_, a_] := IntegerPartitions[a + m, {m}] - 1;
%t (* Given an assignment, list all resultant assignments after one pebbling move; only works for m>=3. *)
%t pebblemoves[config_] :=
%t Block[{m, temp}, m = Length[config];
%t temp = Table[config, {i, m (m - 1)}] +
%t Permutations[Join[{-(k + 1), k}, Table[0, {i, m - 2}]]];
%t temp = Select[temp, Min[#] >= 0 &];
%t temp = ReverseSort[DeleteDuplicates[ReverseSort /@ temp]]];
%t (* Given m and a, list all assignments that are P-games. *)
%t Plist = {};
%t plist[m_, a_] :=
%t Block[{index, tuples},
%t While[Length[Plist] < m, index = Length[Plist];
%t AppendTo[Plist, {{Join[{1}, Table[0, {i, index}]]}}]];
%t Do[AppendTo[Plist[[m]], {}]; tuples = alltuples[m, i];
%t Do[If[
%t Not[IntersectingQ[pebblemoves[tuples[[j]]],
%t If[i > 2, Plist[[m, i - 1]], {}]]],
%t AppendTo[Plist[[m, i]], tuples[[j]]]], {j, Length[tuples]}], {i,
%t Length[Plist[[m]]] + 1, a}]; Plist[[m, a]]];
%t (* Given m, print out the minimum a such that there are no P-games with a pebbles *)
%t Do[a = 1; While[plist[m, a] != {}, a++];
%t Print["k=", k, " m=", m, " a=", a], {m, 5, 10}], {k, 1, 6}]
%Y Cf. A340631, A346197, A346401.
%K nonn,more,tabl
%O 5,1
%A _Kayla Barker_, _Mia DeStefano_, _Eugene Fiorini_, _Michael Gohn_, _Joe Miller_, _Jacob Roeder_, _Wing Hong Tony Wong_, Sep 09 2021
|
