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--).

  • $\begingroup$ Your question seems weird...and it looks like you wrote this question. First, you mentioned that a block of 3 consecutive open doors is a 'hole'. but in your N=5 example, there are no 3 consecutive open doors ie "ooo" so there is no hole but 'J' wins. Second, you use the words "cells" and "doors"...can they be assumed to refer to the same thing? Third, are the doors only lined up in 1 direction (left - right) etc? Fourth, what happens if enough doors are opened (say $N-1$) and then no doors are left? Does any player win? Finally, what do you mean by a player playing optimally? $\endgroup$ – bryanblackbee Feb 17 '13 at 11:30
  • 2
    $\begingroup$ J wins there because whatever door B opens in the next step, J will make a "hole" $\endgroup$ – ciceksiz kakarot Feb 17 '13 at 11:32
  • $\begingroup$ @bryansis2010 J wins, whatever B opens. $\endgroup$ – superAnnoyingUser Feb 17 '13 at 11:35
  • $\begingroup$ It seems that there are n choose 3 = n!/((n-3)!*3!) possible combinations of consecutive open doors. My intuition tells me that there's some kind of finite subcovering optimization that can be used here but it's too late/early for me to say anything more concrete than that :-) Cool puzzle! $\endgroup$ – user39898 Feb 17 '13 at 11:36

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$

  • 1
    $\begingroup$ +1 Enlightening post on a subject about which I do not know much, thanks! I have taken the liberty to add a reference for the Grundy numbers. $\endgroup$ – Andreas Caranti Feb 17 '13 at 15:27
  • $\begingroup$ I should have a look at Winning Ways to see whether this game appears in that book. $\endgroup$ – Gerry Myerson Feb 17 '13 at 22:30
  • $\begingroup$ It is! Editing my answer.... $\endgroup$ – Gerry Myerson Feb 18 '13 at 6:12

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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.