solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看6829次
Maker-Breaker Percolation Games I: Crossing Grids. (arXiv:1810.05190v1 [math.CO])
来源于:arXiv
Motivated by problems in percolation theory, we study the following 2-player
positional game. Let $\Lambda_{m \times n}$ be a rectangular grid-graph with
$m$ vertices in each row and $n$ vertices in each column. Two players, Maker
and Breaker, play in alternating turns. On each of her turns, Maker claims $p$
(as-yet unclaimed) edges of the board $\Lambda_{m \times n}$, while on each of
his turns Breaker claims $q$ (as-yet unclaimed) edges of the board and destroys
them. Maker wins the game if she manages to claim all the edges of a crossing
path joining the left-hand side of the board to its right-hand side, otherwise
Breaker wins. We call this game the $(p,q)$-crossing game on $\Lambda_{m \times
n}$.
Given $m,n\in \mathbb{N}$, for which pairs $(p,q)$ does Maker have a winning
strategy for the $(p,q)$-crossing game on $\Lambda_{m \times n}$? The
$(1,1)$-case corresponds exactly to the popular game of Bridg-it, which is well
understood due to it being a special case of the older Shannon 查看全文>>