Geodesic
Hercules versus Hidden Hydra Helper
Commentationes Mathematicae Universitatis Carolinae, Tome 32 (1991) no. 4, pp. 731-741

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

L. Kirby and J. Paris introduced the Hercules and Hydra game on rooted trees as a natural example of an undecidable statement in Peano Arithmetic. One can show that Hercules has a ``short'' strategy (he wins in a primitively recursive number of moves) and also a ``long'' strategy (the finiteness of the game cannot be proved in Peano Arithmetic). We investigate the conflict of the ``short'' and ``long'' intentions (a problem suggested by J. Ne{\v s}et{\v r}il). After each move of Hercules (trying to kill Hydra fast) there follow $k$ moves of Hidden Hydra Helper (making the same type of moves as Hercules but trying to keep Hydra alive as long as possible). We prove that for $k=1$ Hercules can make the game short, while for $k\geq 2$ Hidden Hydra Helper has a strategy for making the game long.
Classification : 03B25, 03F30, 05C05, 90D46, 90D99
Keywords: rooted tree; unprovability; Kirby--Paris Theorem 
@article{CMUC_1991__32_4_a15,
     author = {Matou\v{s}ek, Ji\v{r}{\'\i} and Loebl, Martin},
     title = {Hercules versus {Hidden} {Hydra} {Helper}},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {731--741},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {1991},
     mrnumber = {1159820},
     zbl = {0763.05029},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1991__32_4_a15/}
}
TY  - JOUR
AU  - Matoušek, Jiří
AU  - Loebl, Martin
TI  - Hercules versus Hidden Hydra Helper
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1991
SP  - 731
EP  - 741
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CMUC_1991__32_4_a15/
LA  - en
ID  - CMUC_1991__32_4_a15
ER  - 
%0 Journal Article
%A Matoušek, Jiří
%A Loebl, Martin
%T Hercules versus Hidden Hydra Helper
%J Commentationes Mathematicae Universitatis Carolinae
%D 1991
%P 731-741
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMUC_1991__32_4_a15/
%G en
%F CMUC_1991__32_4_a15
Matoušek, Jiří; Loebl, Martin. Hercules versus Hidden Hydra Helper. Commentationes Mathematicae Universitatis Carolinae, Tome 32 (1991) no. 4, pp. 731-741. http://geodesic.mathdoc.fr/item/CMUC_1991__32_4_a15/