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

Zbl 0501.03017
Full Text: