геркулес и гидра (математика)
Feb. 21st, 2002 01:29 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВот любопытная математическая задачка.
Если кто уже знает решение, не отвечайте.
Об очень интересной связи этой задачки с мат. логикой будет отдельная запись, после того, как в комментах появится правильное решение (или я сам его напишу). Если в комментах появится правильное решение, я сообщу об этом в апдейте здесь.
Итак, у нас есть гидра и Геркулес, который хочет её победить.
Гидра - любое конечное дерево, растущее из одного корня. Количество "сыновей" каждой вершины не ограничено (но конечно), равно как и высота дерева.
(заранее прошу прощения на случай, если моя терминология не совпадает с принятой в России — я нахально перевожу термины с английского)
Пример гидры с корнем в вершине А:
Головами гидры назовём листья дерева - вершины, не имеющие сыновей. В данном примере головы - B,D,F,G,H.
Битва между Геркулесом и гидрой проводится дискретными ходами. На каждом ходу Геркулес отрубает одну из голов гидры (т.е. разрешается рубить только листья дерева).
Если у отрубленной головы нет "дедушки", т.е. эта голова - корень или вершина, выходящая из корня, то ничего не происходит и мы переходим к следующему ходу. Если же у вершины есть "дедушка", то после её отрубления у гидры вырастают, из "дедушки", N точных копий дерева начиная с "отца" отрубленной головы, где N - номер хода.
Пример. Предположим, что своим первым ходом Геркулес отрубает голову G у гидры, изображённой выше. Тогда после первого хода гидра будет выглядеть так:
Если бы это был не первый ход, а 15-й, то после него от вершины C отходили бы 15 новых под-деревьев E1-F1-H1, E2-F2-H2, ..., E15-F15-H15.
С другой стороны, если у изображённой выше гидры Геркулес отрубает голову B, то у гидры не вырастают новые головы в результате этого хода.
Понятно, таким образом, что после отрубления одной головы у гидры может вырасти сразу очень много новых голов, причём чем дальше продолжается борьба, тем больше номера ходов и тем больше копий под-деревьев создаются в результате следующего хода (если он не рубит корень или вершину, выходящую из него).
Теперь собственно задачи:
1. Доказать: Для любой данной гидры у Геркулеса есть стратегия вырубки голов, позволяющая в результате полностью уничтожить эту гидру (за конечное число шагов).
Это простое задание. Можно заняться им, если не получается второе или в качестве подготовки к нему. Главное же задание вот какое:
2. Доказать: Для любой данной гидры любая стратегия Геркулеса по вырубке голов приводит к полному уничтожению гидры (за конечное число шагов).
Если кто уже знает решение, не отвечайте.
Об очень интересной связи этой задачки с мат. логикой будет отдельная запись, после того, как в комментах появится правильное решение (или я сам его напишу). Если в комментах появится правильное решение, я сообщу об этом в апдейте здесь.
Итак, у нас есть гидра и Геркулес, который хочет её победить.
Гидра - любое конечное дерево, растущее из одного корня. Количество "сыновей" каждой вершины не ограничено (но конечно), равно как и высота дерева.
(заранее прошу прощения на случай, если моя терминология не совпадает с принятой в России — я нахально перевожу термины с английского)
Пример гидры с корнем в вершине А:
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. Доказать: Для любой данной гидры любая стратегия Геркулеса по вырубке голов приводит к полному уничтожению гидры (за конечное число шагов).
ãû.
Date: 2002-02-21 06:31 am (UTC)2. ñðóáàíèå ãîëîâû, íå ÿâëÿþùåéñÿ åäèíñòâåííûì ðåáåíêîì - ïðèâîäèò ê óâåëè÷åíèþ äåòåé íà _ïðåäûäóùåì_ óðîâíå, íî ê óìåíüøåíèþ äåòåé ó îäíîãî ðîäèòåëÿ íà òåêóùåì. òî åñòü, óäàð ïî ãîëîâå ñ M áðàòüÿìè ïðèâîäèò ê ïîÿâëåíèþ N "äÿäåé" ñ M-1 äåòüìè, îòñþäà, êîëè÷åñòâî äåòåé ó êàæäîé, îòäåëüíî âçÿòîé ãîëîâû ñòðåìèòñÿ ê íóëþ (óâåëè÷èâàÿ ïðè ýòîì êîëè÷åñòâî ãîëîâ íà óðîâíå N-1) è ñì. ï.1.
ñîîòâåòñòâåííî, âûðóáàÿ òîëüêî ñàìûå ìëàäøèå ãîëîâû êîëè÷åñòâî óðîâíåé ñòðåìèòñÿ ê íóëþ. à êàê òîëüêî óðîâíåé îñòàíåòñÿ 2, ãîëîâû ïåðåñòàíóò ïëîäèòüñÿ, ÷òî îçíà÷àåò èõ ìåäëåííóþ è ìó÷èòåëüíóþ ñìåðòü.
DEmm.
Re: ãû.
Date: 2002-02-21 06:37 am (UTC)Ó ãîëîâ íå áûâàåò äåòåé ;) ãîëîâû - ýòî êàê ðàç âåðøèíû áåç äåòåé.
×òîáû ýòî ïðèîáðåëî ñâÿçíîñòü, Âàì íóæíî îïðåäåëèòü, ÷òî èìåííî ñòðåìèòñÿ ê íóëþ. È äîêàçàòü ;)
Ïîíÿòíî, ÷òî åñòü "îáùåå îùóùåíèå" òîãî, ÷òî ïîñëå ðóáêè êàæäîé ãîëîâû äåðåâüÿ êàê áû ñòàíîâÿòñÿ "óæå". È òî, ÷òî èõ êîë-âî ðåçêî ðàñò¸ò èõ îò ýòîãî ñóæåíèÿ íå ñïàñàåò. Ïðîáëåìà â òîì, ÷òîáû ýòî èíòóèòèâíîå îùóùåíèå ñòðîãî îïðåäåëèòü è äîêàçàòü, â ýòîì è ñîñòîèò âñÿ çàäà÷à ïî ñóòè äåëà. Äî ñèõ ïîð âñå ïðåäëàãàåìûå ðåøåíèÿ ïðîñòî ïåðåâîäèëè ýòî îùóùåíèå èç îäíîé ñëîâåñíîé ôîðìû â äðóãóþ.