×

Hercules and Hydra. (English) Zbl 0666.05024

Hercules and Hydra is a game on finite rooted trees. In what follows, it is supposed that the game starts with a path \(T_ 0\) and the sequence of rooted trees \(T_ 0,T_ 1,T_ 2,..\). (resulting in course of the game) is called a trajectory. The author defines two simple recursive strategies MAX, MIN of Hercules. He proves that they give trajectories of maximum and minimum length, respectively. Improving a result of L. Kirby and J. Paris [Bull. Lond. Math. Soc. 14, 285-293 (1982; Zbl 0501.03017)], he shows that the statement “Strategy MAX is a winning strategy of Hercules” cannot be proved in Peano arithmetic.
Reviewer: A.Ádám

MSC:

05C05 Trees
91A99 Game theory
03B25 Decidability of theories and sets of sentences

Keywords:

game; rooted trees

Citations:

Zbl 0501.03017
PDF BibTeX XML Cite
Full Text: EuDML