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

[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

solution

[talash.livejournal.com]

when we chop a hydra's head it grows N copies of the sub-tree which has the chopped head's father as a root from the chopped head's grandfather. the lowest level the of the tree will, however remain the chopped head's level. thus, though the number of heads might increase in the beginning, the number of heads that sprout from each father on the lowest level will decrease. this will continue until we chop all heads of a certain father on the lowest level, which will happen inevitably, since the number of heads that grow from each father on the lowest level always decreases. thus, sooner or later we will reach a higher level. the same applies recursively for a higher level, until we reach a level with no grandfather, wherefore we chop off the remaining heads and finish the hydra off. this will happen inevitable, whatever strategy we choose, since the number of heads that sprout from each father on the lower level always decreases.

Re: solution

[avva.livejournal.com]

when we chop a hydra's head it grows N copies of the sub-tree which has the chopped head's father as a root from the chopped head's grandfather. the lowest level the of the tree will, however remain the chopped head's level.

This is not true. It may be that the chopped head has sibling vertices which are not heads and which in fact have large subtrees growing out of them. These subtrees will be replicated N times with the rest of the subtree growing out of the chopped head's father, and so the number of heads on the chopped head's level and on lower levels may grow dramatically.

elaboration of the solution

[talash.livejournal.com]

when we chop off a head on a certain level we decrease the number of heads that have the same grandfather that sprout from each father on the level of the chopped head. thus we will eventually chop off all the heads of a certain grandfather on a certain level. when this will happen we must proceed starting with another random head. sooner or later we will chop all the heads of a certain grandfather this way, since the number of heads is finite. when this happens, the grandfather will go up one level if possible, unless we have reached a level without a grandfather. we will reach this level inevitably since we will sooner or later chop off the heads of all grandfathers and thus they will always go up, unless there's no more way to go up. when this happens we chop off the remaining heads and finish the hydra off.

Re: elaboration of the solution

[avva.livejournal.com]

Sorry, but no. Even the first sentence is incorrect, and the whole is not nearly precise enough to qualify as a proof.
You have to elaborately and precisely *prove* that Hercules will finish off the tree, not reason vaguely about some number of heads somewhere decreasing. Considering that at the same time heads get multiplied at a crazy rate, it's just not enough.