|
| |
|
|
A340631
|
|
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 pebbling game.
|
|
8
|
|
|
|
7, 23, 7, 13, 9, 15, 11, 17, 13, 19, 15, 21, 17, 23, 19, 25, 21, 27, 23, 29, 25, 31, 27, 33, 29, 35, 31, 37, 33, 39, 35, 41, 37, 43, 39, 45, 41, 47, 43, 49, 45, 51, 47, 53, 49, 55, 51, 57, 53, 59, 55, 61, 57, 63, 59, 65, 61, 67, 63, 69, 65, 71, 67, 73, 69, 75
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
3,1
|
|
|
COMMENTS
|
A move in an impartial two-player pebbling game consists of removing two pebbles from a vertex and adding one pebble to an adjacent vertex. The winning player is the one who makes the final allowable move. We start at n = 3 because we have shown a(2) does not exist.
|
|
|
REFERENCES
|
E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, CRC Press, 2001.
|
|
|
LINKS
|
|
|
|
FORMULA
|
For n>2, a(2n-1)=2n+1, a(2n)=a(2n+5)=2n+7.
G.f.: x^3*(12*x^4-10*x^3-23*x^2+16*x+7)/((x+1)*(x-1)^2).
|
|
|
EXAMPLE
|
For n=3, a(3)=7 is the least number of pebbles for which every game in a next-player winning game regardless of assignment.
|
|
|
MATHEMATICA
|
(* 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[{-2, 1}, 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]]], Plist[[n, i - 1]]]], AppendTo[Plist[[n, i]], tuples[[j]]]], {j, Length[tuples]}], {i, Length[Plist[[n]]] + 1, m}]; Plist[[n, m]]];
(* Given n, print out the minimum m such that there are no P-games with m pebbles *)
Do[m = 1; While[plist[n, m] != {}, m++]; Print["n=", n, " m=", m], {n, 3, 20}]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
