Consider the following game: two players, Yolanda (who always goes first) and Zachary, take turns selecting (not yet chosen) numbers between $1$ and $9$. The first player who can make three of their selected numbers sum to $15$ wins. This is well-known to be isomorphic to Tic-Tac-Toe (and so in particular, the game is a draw with best play) by mapping numbers to their locations in the $3\times 3$ magic square: $$ \begin{array}{c|c|c} 8 & 1 & 6 \\ \hline 3 & 5 & 7 \\ \hline 4 & 9 & 2 \\ \end{array} $$ Thus, for instance, Yolanda can ensure at least a draw by choosing $5$; and if Zachary replies with some other odd number (say, $7$) then she can win — in this particular instance, by choosing $6$ (forcing Zachary to 'block' with $4$) and then picking $1$ (winning next turn with either $\{1,6,8\}$ or $\{1,5,9\}$). Of course, if Zachary responds to Yolanda's first move of $5$ with any of the even numbers (i.e., the corner squares) then he can draw.

On the other hand, the analogous game where the players choose numbers between $1$ and $10$ (still trying to find a subset of three numbers which sum to $15$) becomes a first-player win: Yolanda can start by choosing $2$, and then choose either $3$ or $5$ based on Zachary's first move. For instance, if Zachary replies by picking $5$, then Yolanda picks $3$; now Zachary has to pick $10$ to keep her from winning immediately, and Yolanda can choose $4$, winning next move with one of $\{3,4,8\}$ or $\{2,4,9\}$.

What I'm wondering is if the generalized version of this game has been studied at all: let two players alternate choosing numbers from $\{1\ldots m\}$ with the goal being to select a subset of size $d$ summing to $N$. Then there are a lot of natural questions that can be asked:

(a) Is there a characterization (even partial) of which particular values $(d,m,N)$ lead to a win for the first player?

(b) More particularly: is the game monotonic in $m$? That is, if the $(d,m_0,N)$ game is a first-player win, is $(d,m,N)$ a first-player win for all $m\geq m_0$? The usual strategy-stealing arguments show that the game must be either a draw or a first-player win with perfect play (since having an extra number in your 'bin' is never a down side), but at least at first glance it's not clear that a winning strategy on $\{1\ldots m\}$ can't be invalidated back to a draw by the existence of additional counter options when $m$ increases.

(c) Is it even the case that for every $d\gt2$ there are some $m$ and $N$ with the $(d,m,N)$ game a first-player win? (A trivial pairing argument shows that this can never be true for $d=2$.) It seems like there may be Ramsey arguments here, but I haven't proved it yet.

I've skimmed my various CGT references and haven't found anything about this game so far; any pointers would be greatly appreciated.

  • 1
    $\begingroup$ While this is certainly a finite game of perfect information, etc. It doesn't split up (at least not obviously) as a disjoint sum of other games, which makes it less likely to appear in a resource on combinatorial games. I would suggest looking at/asking more general combinatorial sources. $\endgroup$ – Mark S. Feb 28 '15 at 13:34
  • 1
    $\begingroup$ Note that the game state is related to a uniform block design on $m$ points whose "lines" correspond to the partitions of $N$ into $d$ distinct parts not greater than $m$. For fixed $N$ and $d$, the largest summand that can appear is $N - \binom{d}{2}$, so we need consider only $m$ at most this value. $\endgroup$ – hardmath Jul 26 '15 at 12:19

Your Answer

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

Browse other questions tagged or ask your own question.