Geodesic
Asymptotically optimal pairing strategy for tic-tac-toe with numerous directions
The electronic journal of combinatorics, Tome 17 (2010)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
We show that there is an $m=2n+o(n)$, such that, in the Maker-Breaker game played on $\mathbb{Z}^d$ where Maker needs to put at least $m$ of his marks consecutively in one of $n$ given winning directions, Breaker can force a draw using a pairing strategy. This improves the result of Kruczek and Sundberg [Electronic Journal of Combinatorics 15(1):N42, 2008] who showed that such a pairing strategy exists if $m\ge 3n$. A simple argument shows that $m$ has to be at least $2n+1$ if Breaker is only allowed to use a pairing strategy, thus the main term of our bound is optimal.
DOI : 10.37236/482
Classification : 91A46 
Padmini Mukkamala; Dömötör Pálvölgyi. Asymptotically optimal pairing strategy for tic-tac-toe with numerous directions. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/482
@article{10_37236_482,
     author = {Padmini Mukkamala and D\"om\"ot\"or P\'alv\"olgyi},
     title = {Asymptotically optimal pairing strategy for tic-tac-toe with numerous directions},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/482},
     zbl = {1202.91044},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/482/}
}
TY  - JOUR
AU  - Padmini Mukkamala
AU  - Dömötör Pálvölgyi
TI  - Asymptotically optimal pairing strategy for tic-tac-toe with numerous directions
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/482/
DO  - 10.37236/482
ID  - 10_37236_482
ER  - 
%0 Journal Article
%A Padmini Mukkamala
%A Dömötör Pálvölgyi
%T Asymptotically optimal pairing strategy for tic-tac-toe with numerous directions
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/482/
%R 10.37236/482
%F 10_37236_482

Cité par Sources :