геркулес и гидра (математика)

[avva]

Вот любопытная математическая задачка.
Если кто уже знает решение, не отвечайте.
Об очень интересной связи этой задачки с мат. логикой будет отдельная запись, после того, как в комментах появится правильное решение (или я сам его напишу). Если в комментах появится правильное решение, я сообщу об этом в апдейте здесь.

Итак, у нас есть гидра и Геркулес, который хочет её победить.
Гидра - любое конечное дерево, растущее из одного корня. Количество "сыновей" каждой вершины не ограничено (но конечно), равно как и высота дерева.
(заранее прошу прощения на случай, если моя терминология не совпадает с принятой в России — я нахально перевожу термины с английского)
Пример гидры с корнем в вершине А:

        A
       / \
      B   C
         / \
         D  E
           /|\
          F G H

Головами гидры назовём листья дерева - вершины, не имеющие сыновей. В данном примере головы - B,D,F,G,H.

Битва между Геркулесом и гидрой проводится дискретными ходами. На каждом ходу Геркулес отрубает одну из голов гидры (т.е. разрешается рубить только листья дерева).

Если у отрубленной головы нет "дедушки", т.е. эта голова - корень или вершина, выходящая из корня, то ничего не происходит и мы переходим к следующему ходу. Если же у вершины есть "дедушка", то после её отрубления у гидры вырастают, из "дедушки", N точных копий дерева начиная с "отца" отрубленной головы, где N - номер хода.

Пример. Предположим, что своим первым ходом Геркулес отрубает голову G у гидры, изображённой выше. Тогда после первого хода гидра будет выглядеть так:

       A
      / \
     B   C
        /|\
       / | \
      D  E  E1
       / |  | \
      F  H F1 H1 

Если бы это был не первый ход, а 15-й, то после него от вершины C отходили бы 15 новых под-деревьев E1-F1-H1, E2-F2-H2, ..., E15-F15-H15.
С другой стороны, если у изображённой выше гидры Геркулес отрубает голову B, то у гидры не вырастают новые головы в результате этого хода.

Понятно, таким образом, что после отрубления одной головы у гидры может вырасти сразу очень много новых голов, причём чем дальше продолжается борьба, тем больше номера ходов и тем больше копий под-деревьев создаются в результате следующего хода (если он не рубит корень или вершину, выходящую из него).

Теперь собственно задачи:

1. Доказать: Для любой данной гидры у Геркулеса есть стратегия вырубки голов, позволяющая в результате полностью уничтожить эту гидру (за конечное число шагов).

Это простое задание. Можно заняться им, если не получается второе или в качестве подготовки к нему. Главное же задание вот какое:

2. Доказать: Для любой данной гидры любая стратегия Геркулеса по вырубке голов приводит к полному уничтожению гидры (за конечное число шагов).

Comments

Re: vague solution

[avva.livejournal.com]

The third step is a huge leap that remains unproved. What you perhaps fail to realize is the following. Suppose you chop off a head on level k and such that its father has N sons. Then it's true that after the chopping this father and all the new uncles will have N-1 sons (but don't forget that the grandfather may have other sons with >N sons, by the way). But once you got that, you can't really continue and get that down to N-2, etc. because you can't generally chop off *another* son of the same father, since that son might not be a head - it might be a vertex with a whole tree hanging off it. If at some point you chop a head such that all its siblings are not heads, you have no choice but to go to lower levels of these subtrees and start chopping there, and this in fact may eventually increase the number of heads on the level k; moreover, you're not guaranteed that you'll eventually chop off everything in any particular subtree to come up to the original father's son (to make it a head) - that's a vicious circle in the reasoning.

That's if I understood your intent correctly.

As for step 4, you aren't proving that either. Let's call a head which is not on the lowest level of the tree a "bad" head. When you chop off a bad head, you create, potentially, a huge amount of other bad heads on this and lower levels. I understand that you want to get rid of all the bad heads and then it's all easy, but I don't think you proved you can do that.