Generalized Harary games
There are a number of positional games known on the infinite chessboard. One of the most studied is the 5-in-a-row, whose rules are almost identical to the ancient Japanese Go-Moku. Along this line Harary asked if a player can achieve a translated copy of a given polymino P when the two players alte...
Elmentve itt :
| Szerző: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
1997
|
| Sorozat: | Acta cybernetica
13 No. 1 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12580 |
| Tartalmi kivonat: | There are a number of positional games known on the infinite chessboard. One of the most studied is the 5-in-a-row, whose rules are almost identical to the ancient Japanese Go-Moku. Along this line Harary asked if a player can achieve a translated copy of a given polymino P when the two players alternately take the squares of the board. Here we pose his question for general subsets of the board, and give a condition under which a draw is possible. Since a drawing strategy corresponds to a good 2-coloration of the underlying hypergraph, our result can be viewed as a derandomization of the Lovász Local Lemma. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 77-83 |
| ISSN: | 0324-721X |