4
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ I'm unfamiliar with this generalization! How does the case $n=7$ reduce to ordinary tic-tac-toe? $\endgroup$
    – Owen Biesel
    Commented Aug 2, 2012 at 14:47
  • 11
    $\begingroup$ 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.) $\endgroup$
    – Seva
    Commented Aug 2, 2012 at 14:51
  • 4
    $\begingroup$ 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. $\endgroup$
    – Owen Biesel
    Commented Aug 2, 2012 at 14:56
  • $\begingroup$ 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. $\endgroup$
    – Benjamin Dickman
    Commented Aug 2, 2012 at 15:38
  • 2
    $\begingroup$ @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). $\endgroup$
    – Zack Wolske
    Commented Aug 2, 2012 at 20:53

3 Answers 3

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ Clever! Wish I'd seen it. $\endgroup$
    – Timothy Chow
    Commented Aug 2, 2012 at 21:48
  • 5
    $\begingroup$ 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.] $\endgroup$
    – user9072
    Commented Aug 2, 2012 at 23:47
  • $\begingroup$ You are correct. This is incomplete or wrong. $\endgroup$
    – Will Sawin
    Commented Aug 3, 2012 at 1:44
  • $\begingroup$ Nice catch, quid. I have "unaccepted" the answer. $\endgroup$
    – Timothy Chow
    Commented Aug 3, 2012 at 1:52
  • $\begingroup$ I fixed my answer. $\endgroup$
    – Will Sawin
    Commented Aug 3, 2012 at 2:05
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user9072
    Commented Aug 3, 2012 at 10:37
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .