Tic-tac-toe with one mark type

Question

In an $atimes b$ board, two players take turns putting a mark on an empty square. Whoever gets $cleq max(a,b)$ consecutive marks horizontally, vertically, or diagonally first wins. (Someone must win because we use only one mark type.) For each triple $(a,b,c)$, who has a winning strategy?
For $a=b=c=3$ (tic-tac-toe size), the first player can win by first going on the middle square and winning in the next turn. A generalization is that for $a,b,c$ are all odd, the first player can go on the middle square, then reflect the second player's move across the middle square. (He also needs to keep his eyes open in case the second player marks the $(c-1)$st square of a $c$-in-a-row, so that he can win immediately.)
In the one-dimensional case ($a=1$), this may well be a known game, but I also cannot find a reference.

Eli Howitt · Answer

I dont have a general-case answer rather some insight regarding the c=3 case leading to a general conclusion:
(In the c=3 case:)Given some tic already placed 'p', you lose if you place a tic 'q' in a place allowing the opponent to complete a 3-line with p & q. One notices quickly that all such tics lie  within the Manhattan-distance circle of radius 2 centered around p. This means that if when you start playing one can place a tic everywhere, each tic placed limits the non-losing space with the area of a square (a Manhattan-distance circle is a square rotated). This means each player 'survives' their turn by placing another square inside the remaining area, so this is a classic Packing problem. Many variants exist such as circle packing (https://en.wikipedia.org/wiki/Circle_packing#:~:text=In%20geometry%2C%20circle%20packing%20is,enlarged%20without%20creating%20an%20overlap.) or square packing (https://en.wikipedia.org/wiki/Square_packing_in_a_square#:~:text=Square%20packing%20in%20a%20square%20is%20a%20packing%20problem%20where,wasted%20space%20for%20non%2Dinteger), both of which dont have a closed form for their packing capacity, this leads me to believe that, other than some specific cases, this generalization your searching for does not exist!
I think in cases c>3 one can express the area taken by a move similarly (much more complex but still an area taken-up) and thus some weird packing-problem. This leads me to believe no generalization exists at all for any c.
The specific cases are cool though. Cheers!
(Manhattan-distance AKA Taxicab distance : https://en.wikipedia.org/wiki/Taxicab_geometry)

Tic-tac-toe with one mark type

One Answer

Add your own answers!

Related Questions

Constant invariant quantities

Convergence of martingales is a martingale

Question on cardinality of a set

$X$ is a random variable with PDF $f$, with $f$ continuous at $x=a$. Then $lim_{varepsilonto0^-}frac{1}{varepsilon}P(Xin(a,a+varepsilon))=f(a)$

Suppose that $N$ and $r$ are positive integers. Prove or disprove that if $N$ is an even integer and $r$ is odd, then $binom{N}{r}$ is even.

Confusions about the proof of representations of isometries as products of reflections.

Combinatorics doubts

$limlimits_{n rightarrow infty} e^{-2n}sum_{k=0}^n frac{(2n)^k}{k!}$

Why is $[1,2]$ relatively open in $[1,2] cup [3,4]$?

Algebra – How can I graph this function and work with exponential function with base $a$?

Best approximation of sum of unit vectors by a smaller subset

Unbounded on every interval except null set but finite a.e

Jordan normal form of $;begin{pmatrix}0 & 1 & 0 \ 0 & 0 & 1 \ 0 & a & b end{pmatrix},; a,binmathbb{R}$

Derivative of random normal times indicator function

Critical points of a nonnegative quadratic form on a subspace

Geometric interpretation of a symmetric matrix

Minimum number of solutions for $f=g$

$X_i equiv a_i pmod{P}$ for some $a_i in mathcal{O}$ given a prime ideal $P$ of $mathcal{O}[X_1, ldots, X_n]/(f_1, …, f_n)$

A limit involving the integer nearest to $n$-th power

Proving that $F(x)=sumlimits_{k=1}^{p-1}left(frac{k}{p}right)x^k$ has at least $frac{p-1}{2}$ different complex roots

Ask a Question