OFFSET
1,3
COMMENTS
In a domino-covering game, the players take turns placing dominoes (1 X 2 rectangles) on the board (here a 1 X N rectangle), such that the position of the dominoes is an integer, and no two dominoes overlap. The loser is the first player unable to make a move.
The optimal strategies for this game can be determined by computing the nim-value nv(N) of each board 1 X N:
nv(0) = 0
nv(1) = 0
nv(N+2) = least nonnegative integer not in {nimsum(nv(k),nv(N-k)) : k <= N}
(where nimsum(a,b) is the bitwise xor of a and b).
The second player wins a game iff its nim-value is 0.
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Pratik Alladi, Neel Bhalla, Tanya Khovanova, Nathan Sheffield, Eddie Song, William Sun, Andrew The, Alan Wang, Naor Wiesel, and Kevin Zhang Kevin Zhao, PRIMES STEP Plays Games, arXiv:1707.07201 [math.CO], 2017, Section 8.
Stephan Brumme, Project Euler.net Problem 306, (2017).
Randal E. Bryant and Marijn J. H. Heule, Dual Proof Generation for Quantified Boolean Formulas with a BDD-Based Solver, Carnegie Mellon Univ. (2021).
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,-1).
FORMULA
For n > 14, a(n) = a(n-5) + 34. - Rainer Rosenthal and Charles R Greathouse IV, Sep 20 2012
G.f.: x^2*(6*x^13 - 2*x^12 + 8*x^10 - 2*x^9 - 2*x^8 + 2*x^7 + 3*x^5 + 6*x^4 + 6*x^3 + 4*x^2 + 4*x + 1) / ((x - 1)^2*(x^4 + x^3 + x^2 + x + 1)). - Colin Barker, Jan 26 2013
EXAMPLE
N=1: the first player is unable to move (second player win).
N=2,3: any move by the first player renders the second player unable to move (first player win).
N=4: the first player can win by covering the two central squares (first player win).
N=5: any move by the first player has a final counter-move by the second (second player win).
MATHEMATICA
Rest@ CoefficientList[Series[x^2*(6 x^13 - 2 x^12 + 8 x^10 - 2 x^9 - 2 x^8 + 2 x^7 + 3 x^5 + 6 x^4 + 6 x^3 + 4 x^2 + 4 x + 1)/((x - 1)^2*(x^4 + x^3 + x^2 + x + 1)), {x, 0, 39}], x] (* Michael De Vlieger, Aug 18 2021 *)
PROG
(Python)
import numpy as np
N = np.array([0, 0])
U = np.arange(1000)
for i in U:
N = np.append(N, np.setdiff1d(U, np.bitwise_xor(N[:-1], N[-2::-1])).min())
print(list(*np.where(N==0)))
(PARI) a(n)=if(n<10, [0, 1, 5, 9, 15, 21, 25, 29, 35][n], n\5*34-[29, 25, 13, 9, 5][n%5+1]) \\ Charles R Greathouse IV, Aug 24 2012
(PARI) list(lim)=my(v=vector(lim\1+1), u); for(n=0, #v-3, u=vecsort(vector(n\2+1, k, bitxor(v[k], v[n-k+2])), , 8); for(i=0, #u-1, if(u[i+1]!=i, v[n+3]=i; next(2)); v[n+3]=#u)); for(i=0, #v-1, v[i+1]=if(v[i+1], 1, i)); vecsort(v, , 8) \\ Charles R Greathouse IV, Aug 24 2012
CROSSREFS
KEYWORD
nonn,easy,changed
AUTHOR
Yuval Gabay, Aug 22 2012
STATUS
approved