|
| |
|
|
A215721
|
|
The values of N for which the 1xN domino-covering game is a second player win.
|
|
1
|
|
|
|
0, 1, 5, 9, 15, 21, 25, 29, 35, 39, 43, 55, 59, 63, 73, 77, 89, 93, 97, 107, 111, 123, 127, 131, 141, 145, 157, 161, 165, 175, 179, 191, 195, 199, 209, 213, 225, 229, 233
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
In a domino-covering game, the players take turns placing dominoes (1x2 rectangles) on the board (here a 1xN rectangle), such that the position of the dominoes is integer, and no two dominoes overlap. The loser is the first player unable to move.
The optimal strategies for this game can be determined by computing the nim-value nv(N) of each board 1xN:
nv(0) = 0
nv(1) = 0
nv(N+2) = least non-negative 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
Index to sequences with 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).
|
|
|
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
|
The nim-values are A002187(n-1).
Sequence in context: A059655 A063093 A095948 * A161536 A217277 A087679
Adjacent sequences: A215718 A215719 A215720 * A215722 A215723 A215724
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
Yuval Gabay, Aug 22 2012
|
|
|
STATUS
|
approved
|
| |
|
|
