Hercules and Hydra. (English) Zbl 0666.05024

Loebl, Martin

Commentat. Math. Univ. Carol. 29, No. 1, 85-95 (1988).

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