Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2309.11367 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914281724837888 |
|---|---|
| author | Alpert, Hannah Barham, Liam Freidin, Brian Tan, Ian Weiner, Alexandra |
| author_facet | Alpert, Hannah Barham, Liam Freidin, Brian Tan, Ian Weiner, Alexandra |
| contents | Consider the following Maker-Breaker game. Fix a finite subset $S\subset\mathbb{N}$ of the naturals. The players Maker and Breaker take turns choosing previously unclaimed natural numbers. Maker wins by eventually building a homothetic copy $aS+b$ of $S$, where $a\in\mathbb{N}\setminus\{0\}$ and $b\in\mathbb{Z}$. This is a generalization of the van der Waerden game analyzed by Beck. By the Hales-Jewett theorem, there exists a constant $c$ depending only on $|S|$ such that Maker can win in $c$ or less moves. We show that Maker can win in $|S|$ moves if $|S|\leq 3$. When $|S|=4$, we show that Maker can always win in $5$ or less moves and describe all $S$ such that Maker can win in $4$ moves. If $|S|\geq 5$, Maker has no winning strategy in $|S|$ moves. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_11367 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fast winning strategies in a generalized van der Waerden game Alpert, Hannah Barham, Liam Freidin, Brian Tan, Ian Weiner, Alexandra Combinatorics 91A46 Consider the following Maker-Breaker game. Fix a finite subset $S\subset\mathbb{N}$ of the naturals. The players Maker and Breaker take turns choosing previously unclaimed natural numbers. Maker wins by eventually building a homothetic copy $aS+b$ of $S$, where $a\in\mathbb{N}\setminus\{0\}$ and $b\in\mathbb{Z}$. This is a generalization of the van der Waerden game analyzed by Beck. By the Hales-Jewett theorem, there exists a constant $c$ depending only on $|S|$ such that Maker can win in $c$ or less moves. We show that Maker can win in $|S|$ moves if $|S|\leq 3$. When $|S|=4$, we show that Maker can always win in $5$ or less moves and describe all $S$ such that Maker can win in $4$ moves. If $|S|\geq 5$, Maker has no winning strategy in $|S|$ moves. |
| title | Fast winning strategies in a generalized van der Waerden game |
| topic | Combinatorics 91A46 |
| url | https://arxiv.org/abs/2309.11367 |