Metraipolis › archive › dc_b4bf8d82c896

The transversal achievement game on a square grid — arXiv:2608.13501

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.13501
License (as archived)
CC0-1.0
Archived
2026-10-19T04:50:25.887Z
SHA-256 of the archived text
e97e5a7c71cb4cee76bed205743385bcec2d66f3fa3a61eb2edd6034ef9f654e
Stable URL of this page
https://metraipolis.com/documento/dc_b4bf8d82c896

How to cite

The transversal achievement game on a square grid — arXiv:2608.13501 — arXiv (en), https://arxiv.org/abs/2608.13501 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b4bf8d82c896 (Metraipolis archive dc_b4bf8d82c896, sha256 e97e5a7c71cb4cee76bed205743385bcec2d66f3fa3a61eb2edd6034ef9f654e)
BibTeX
@misc{dcb4bf8d82c896,
  title = {The transversal achievement game on a square grid — arXiv:2608.13501},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.13501},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b4bf8d82c896; sha256 e97e5a7c71cb4cee76bed205743385bcec2d66f3fa3a61eb2edd6034ef9f654e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.13501. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In the transversal achievement game on the $n\times n$ board, two players alternately claim cells, and the first to own a transversal---a set of $n$ cells of which no two share a row or column---wins. Ranđelović showed that the first player wins for every $n\ge4$, while the game is a draw for $n=2,3$. We give an independent proof that the first player wins for $n\ge4$ that additionally establishes a bound on the length of the win: the given strategy forces a win by ply $2n+3$, i.e.\ on the first player's $(n+2)$-nd move, for every $n\ge4$. The proof yields a strategy that is fully determined by a fixed rule on the current position and can thus be implemented directly. We isolate the use of the hypothesis $n\ge4$ to two steps in the analysis, explaining why the argument fails at $n=3$. An exhaustive computational search implementing the strategy verifies it against every legal defense for $n=4,5,6$, confirming both the strategy's validity and that the $2n+3$ bound is attained in these cases. The main theorem has also been formalized and machine-checked in Lean 4.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-14 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.13501 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T04:28:16.175Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).