Mathematics Asked on January 1, 2022

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.

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)

Answered by Eli Howitt on January 1, 2022

0 Asked on November 6, 2021

1 Asked on November 6, 2021 by satana

martingales probability probability theory stochastic integrals stochastic processes

0 Asked on November 6, 2021 by rosco

cardinals convergence divergence functional analysis real analysis

0 Asked on November 6, 2021 by stackman

3 Asked on November 2, 2021 by s1mple

binomial coefficients combinatorics elementary number theory

1 Asked on November 2, 2021 by user806566

1 Asked on November 2, 2021 by pietro-morri

2 Asked on November 2, 2021

1 Asked on November 2, 2021

1 Asked on November 2, 2021

2 Asked on November 2, 2021 by g-g

combinatorics discrete optimization integer programming linear algebra optimization

1 Asked on November 2, 2021

1 Asked on November 2, 2021 by user731634

1 Asked on November 2, 2021 by forumwhiner

calculus characteristic functions derivatives dirac delta random variables

1 Asked on November 2, 2021

0 Asked on November 2, 2021

0 Asked on November 2, 2021

1 Asked on November 2, 2021

2 Asked on November 2, 2021 by tong_nor

0 Asked on November 2, 2021 by geromty

Get help from others!

Recent Answers

- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP