How to solve this puzzle?

Question

There are $N$ consecutive doors. Two players 'B' and 'J' plays a game. Both take turns alternately, and in each turn a player can open any one door. They define a block of 3 consecutive open doors as "hole". The first one to create a "hole" wins. Player 'J' plays first.

Given 'N', how could we determine the winner assuming both plays optimally?

Example: Let us denote the open door by 'o' and closed door by '-'.

If N = 3: Initially all cells are closed (---), if 'J' opens first door configuration is (o--). 'B' can either open second cell leading to configuration (oo-) or third cell (o-o). In both cases 'J' wins.

If N = 5:

'J' wins by opening the 3rd cell i.e. configuration (--o--).

Answer 1

In the course of a the game, the players will want to avoid forming configurations o-o or oo, because that means the other player will win in the next move. Thus they will have to open doors in order to split consecutive sequences of closed doors into two smaller consecutive sequences of closed doors.

If a player creates a sequence of length $0$ or $1$ bounded by opened doors (o-o or oo) by opening a door, then the next player wins, so until the last move, the game will only consist of sequences of length $\ge 2$ (except maybe at the boundaries)

Add three imaginary doors on each side of the original sequence, and open the two extreme doors. Then you have an equivalent game, since the players will never try to open the $4$ closed imaginary doors (this would create a sequence of length $<2$ allowing the next player to win). Therefore we only need to think about games with sequences of closed doors bounded by two open doors.

Since players play into only one sequence at a time, we can consider that each sequence is its own game, and we only need to compute their respective Grundy numbers. Letting $\otimes$ be the bitwise xor operations on natural numbers on $\oplus$ be the superposition of games, we have $G(x \oplus y) = G(x) \otimes G(y)$, and $G(x) = \min \Bbb N - \{G(y); x \to y\}$ (where $x \to y$ means there is a move to play on $x$ to get $y$)

If we note $n$ the game with a sequence of $n$ closed doors bounded by two open doors, and looking at the allowed moves, we get :
$G(n) = \min \Bbb N - \{G(i)\otimes G(j); 2 \le i,j ; i+j+1=n\}$

This allows you to compute the Grundy number of $(n)$ in $O(n^2)$ steps. For example, $G(2) = G(3) = G(4) = 0$ because you can't make any move in there (you can't play in there without creating a $(0)$ or $(1)$ sequence, which means the opponent wins globally on the next turn).

If $G(N+4) = 0$ then the first player loses, and if $G(N+4)>0$, then there is a winning strategy for the first player.
The first few $N$ where the first player loses are $6,12,22,30,32,44,54,64,76,86,98,\ldots$

Answer 2

EDITED in response to comment by Gugg:

If $N$ is odd, it's a 1st player win. Let $N=2n+1$ and label the doors $-n,\dots,n$. 1st player opens door zero and for the rest of the game plays a game-ending move if possible, otherwise replies to 2nd player opening door $k$ by opening door $-k$. Opening door $-k$ can never permit a game-ending move by 2nd player since if it did then by symmetry 2nd player allowed a game-ending move by opening door $k$, and 1st player would have made it.

MORE EDIT: Berlekamp, Conway, and Guy, Winning Ways, Volume 1, page 93: "Treblecross is a Tic-Tac-Toe game played on a $1\times n$ strip in which both players use the same symbol (X). The first person to complete a line of three consecutive crosses wins." They find the "nim-value" for $n\le12$, but so far as I can see don't work out any general results.

EVEN MORE EDIT: There are explorations of Treblecross available on the web.

http://lbv-pc.blogspot.com.au/2012/07/treblecross.html discusses it.

http://www.calstatela.edu/faculty/sheubac/presentations/EllieSJhandout.pdf is a discussion by Heubach, Chinn, Dufour, and Stevens, from May 2009. They say there is no complete analysis; that Grundy values have been computed up to $n=2^{21}=2097152$, finding 37 "P" positions: $0, 1, 2, 8, 14, 24, 32, 34, 46, 56, 66, 78, \dots, 16170$

http://www.mathstat.dal.ca/~rjn/papers/UnsolvedCGT.pdf is Guy and Nowakowski, Unsolved problems in combinatorial games, Feb 2008. Treblecross comes in bottom of page 3, top of page 4. Grundy number computation pushed to $2^{25}$. They call this game "Perhaps the most notorious and deserving of attention" of the "finite octal games".

Flammenkamp keeps an up-to-date website on these games, http://wwwhomes.uni-bielefeld.de/achim/octal.html He has pushed the Grundy number computation to $2^{28}$.