Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

We begin with $2n+1$ cards, each with a distinct number from $-n$ to $+n$ on it, face up in between the two players of the game. The players take turns selecting a card and keeping it. The first player to collect three cards that sum to zero wins the game. If the cards are exhausted and neither player has won, a draw is declared.

Tic-tac-toe, or noughts and crosses, is of course the special case $n=4$, by using the essentially unique $3\times3$ magic square:

$$\begin{matrix} 3 & -4 & 1 \\\ -2 & 0 & 2 \\\ -1 & 4& -3\end{matrix}$$

Has the case of general $n$ been studied?

share|improve this question
    
I'm unfamiliar with this generalization! How does the case $n=7$ reduce to ordinary tic-tac-toe? –  Owen Biesel Aug 2 '12 at 14:47
8  
Tic-tac-toe actually seems to be the case $n=4$. (I'd also suggest to drop "of course", to avoid the reader developing the inferiority complex.) –  Seva Aug 2 '12 at 14:51
4  
Ah, now I see. The correspondence is via a magic square (subtracting 5 from each number in a standard $3\times 3$ square containing 1 through 9), and you can check manually that there are no extra relations of three numbers summing to 0. –  Owen Biesel Aug 2 '12 at 14:56
    
I would have thought that the "general case" would define the winner as the first player to collect $n−1$ cards that sum to zero. Also, I'm wondering if your original phrasing was: each with a distinct number from $1$ to $2n + 1$, where the first player to collect three cards that sum to $2n + 1$ wins the game. Then tic-tac-toe is the special case $n = 7$, where we construct a $3x3$ magic square and let that determine the optimal strategy. –  Benjamin Dickman Aug 2 '12 at 15:38
2  
@Patricia: The correspondence starts with a magic square, where the rows, columns and diagonals all sum to 15, not with the numbers 1-9 in a standard array (that's a Muggle square). –  Zack Wolske Aug 2 '12 at 20:53
show 3 more comments

3 Answers

up vote 9 down vote accepted

First player wins for $n$ at least five. First turn, name $0$. They name a number, say $-a$. Choose two numbers $b$ and $c$ such that neither $b$, $c$, nor $b+c=a$. Then name $b$, forcing them to name $-b$, then $c$, forcing them to name $-c$, then $-b-c$, winning. You can always choose two such numbers, since each positive number is missed by one of the following triples: $1+2=3, 1+3=4, 1+4=5, 2+3=5$.

As quid points out, this is more complicated than I originally made it seem. If $c\neq a+b$ but $a+b$ is in the interval, then the second player can name $a+b$ in response to $c$ and win.

To avoid this, if $1 <a\leq n-2$, choose $b=1$ and $c=a+1$. Neither $1$, $a+1$, nor $a+2=a$ so this works.

If $a\geq n-1$, choose $b=2$ and $c=1$. Since $n\geq 5$, neither $1$, $2$, nor $3=a$ so this works, and $a+b=a+2>n$.

If $a=1$, choose $b=2$ and $c=3$, so $c=a+b$ and neither $2$, $3$, nor $5=a$.

share|improve this answer
    
Clever! Wish I'd seen it. –  Timothy Chow Aug 2 '12 at 21:48
4  
Either I do not understand this description or it is incomplete/wrong. Let me illustrate my problem with an example. Say let n=5, so we choose 0 (according to startegy) and they choose say -4. Now (according to strategy) we choose b=1 and c=2 so neither 1, 2, nor 1+2 is 4. Then we name b=1 so they need to name -1. And now we name c=2. Yet now we lost if they choose 5 (instead of -2)! [We could still win if instead of 2 we defend at 5, forcing them to take -5 and then choose 2, but this is not the point.] –  quid Aug 2 '12 at 23:47
    
You are correct. This is incomplete or wrong. –  Will Sawin Aug 3 '12 at 1:44
    
Nice catch, quid. I have "unaccepted" the answer. –  Timothy Chow Aug 3 '12 at 1:52
    
I fixed my answer. –  Will Sawin Aug 3 '12 at 2:05
show 1 more comment

Since I still do not understand the argument for the accepted answer, but agree with its conclusion (win for $n \ge 5$), here is an alternate strategy (albeit not very elegant):

Let $n \ge 5$. We start with $0$. And assume without restriction they choose a negative number.

Four cases (but one could somewhat merge 1,3,4):

  1. They choose $-a$, for $a$ neither $1$, $n-1$, nor $n$. Then, we choose $1$. They have to choose $-1$. We choose $a+1$ defending against their (only) winning move. And then win, since they cannot both 'defend' against $a+1$ and $a+2$ (both being legit due to the condition on $a$).

  2. They choose $-1$. Then we choose $2$. They need to choose $-2$. We choose $3$ defending against their (only) winning move and creating again two potential wins (at $-3$ and $-4$), and thus winning.

  3. They choose $-(n-1)$. Then we choose $1$. They have to choose $-1$. We choose $n$ defending their winning move. They need to choose $-n$, which does not create any winning move for them, so we can choose $2$, creating two winning options ($-2$ and $-3$) [note due to $n \ge 5$ there is no interference with the earlier moves], and thus win.

  4. They chooose $-n$. We choose $1$. They need to choose $-1$. This does not create any threat. So we can choose $2$ and then win with $-2$ or $-3$.

share|improve this answer
    
The introductory sentence is now not correct anymore, as I do understand the modified version, not sure it is worth editing it (or keeping at all) my answer, though. For the time being I will leave it as is, in case anybody has some opinion on this matter, please kindly let me know. –  quid Aug 3 '12 at 10:37
add comment

I am not sure about this particular game, but the general and well-studied framework is as follows: given a hypergraph $H$, two players take turns choosing vertices from $H$, the first player collecting a whole edge being the winner. (In your case, the vertex set is $[-n,n]$, and the edges are triples $(a,b,c)\in[-n,n]^3$ which add up to $0$.) Two references you may check: Combinatorial Games: Tic-Tac-Toe Theory and Foundations of Positional Games, both by J. Beck.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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