геркулес и гидра (математика)
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. Доказать: Для любой данной гидры любая стратегия Геркулеса по вырубке голов приводит к полному уничтожению гидры (за конечное число шагов).
no subject
Date: 2002-02-24 05:04 pm (UTC)èäåÿ òàêàÿ (äëÿ ïåðâîé çàäà÷è)
Ïóñòü ìû íàõîäèìñÿ íà ïðîèçâîëüíîì øàãå (x)
Ïóñòü ìàêñèìàëüíûé óðîâåíü - n
Íàçîâåì äåòèøêàìè âåðøèíû íà n-ì óðîâíå,
îòöàìè - òå âåðøèíû íà n-1 óðîâíå, ó ðîòîðûõ åñòü äåòèøêè
äåäàìè - òå âåðøèíû íà n-2 óðîâíå, ó êîòîðûé åñòü ëåòè, ÿâëÿþùèåñÿ îòöàìè
1. Îïðåäåëÿåì äåòèøåê, îòöîâ è äåäîâ
2. åñëè äåäîâ íåò - äåëî ñäåëàíî
3. âûáèðàåì ïðîèçâîëüíîãî äåäà
4. âûáèðàåì ó äåäà îòöà ñ ìàêñèìàëüíûì êîëè÷åñòâîì äåòèøåê
5. ëèøàåì îòöà êàêîãî-òî ñûíà
ðåçóëüòàò ýòîãî äåñòâèÿ - åñëè ó âûáðàííîãî îòöà îäèí ñûí - îí ïåðåñòàë áûòü
îòöîì, êîëè÷åñòâî ãîëîâ ó ãèäðû óìåíüøèëîñü, åñëè áîëüøå îäíîãî - êîëè÷åñòâî îòöîâ
ñ m äåòèøêàìè óìåíüøèëîñü, c m-1 - âîçðîñëî, îáùåå êîëè÷åñòâî
óçëîâ äåðåâà("ãèäðû") óâåëè÷èëîñü, íî íà _êîíå÷íîå ÷èñëî_ (N+=x*(m-1)-1 - âðîäå)
Ñìûñë â òîì, ÷òî, îñòàâàÿñü â ïðåäåëàõ _êîíå÷íîãî_ ÷èñëà ãîëîâ, ìû ÷åðåç êîíå÷íîå
÷èñëî øàãîâ óíè÷òîæèì âñåõ îòöîâ ñ m äåòèøêàìè, ïîòîì ñ m-1 äåòèøêàìè è ò.ä.
à êîãäà m ñòàíåò ðàâíûì 1, îïÿòü òàêè ÷åðåç êîíå÷íîå ÷èñëî øàãîâ ïåðåðóáèì âñåõ îòöîâ,
ñîîòâåñòâåííî äåäóøêåê ñòàíåò íà 1 ìåíüøå, è ò.ä. â êîíöå êîíöîâ ãèäðà, îñòàâàÿñü
â êîíå÷íûõ ïðåäåëàõ, ñòàíåò íà îäèí óðîâåíî êîðî÷å, òîãäà ïåðåõîä ê ï.1 è ò.ä.
Äóìàþ, ñìûñë ñòðàòåãèè ÿñåí, è òîò ôàêò, ÷òî âñå ïðîèñõîäèò â ïðåäåëàõ êîíå÷íûõ ÷èñåë, òîæå
Ñî âòîðîé çàäà÷åé - îáëîì
Íå ìî÷ó ÷åòêî óÿñíèòü, ÷òî _óìåíüøàåòñÿ_ ïðè óíè÷òîæåíèè ïðîèçâîëüíîãî ñûíà
Õî÷åòñÿ åùå ïîäóìàòü
Êñòàòè - à îòêóäà òàêàÿ çàäà÷à?
Re:
Date: 2002-02-24 10:20 pm (UTC)Âòîðàÿ çàäà÷à òàêèìè ñïîñîáàìè íå ðåøàåòñÿ, óâû.
Ïîäóìàéòå, åñëè õîòèòå, íî ó÷òèòå, ÷òî å¸ ðåøåíèå ÿ óæå çàïèñàë â ñâî¸ì äíåâíèêå (íà äåíü ïîçæå ýòîé çàïèñè). Ñåãîäíÿ åù¸ ïëàíèðóþ îáúÿñíèòü äëÿ òåõ, êòî ýòîãî íå çíàåò, íóæíóþ ìàòåìàòè÷åñêóþ òåðìèíîëîãèþ äëÿ îáúÿñíåíèÿ ðåøåíèÿ.
Î òîì, îòêóäà âçÿëàñü çàäà÷à, òîæå âñêîðå ñòàíåò ÿñíî, åñëè áóäåòå ñëåäèòü çà ìîèì äíåâíèêîì ;) ÿ ïëàíèðóþ îáúÿñíèòü å¸ çíà÷åíèå è ïðîèñõîæäåíèå ñåãîäíÿ èëè çàâòðà.
no subject
Date: 2002-02-25 09:50 am (UTC)Âðîäå ðåøèë è âòîðóþ, ïðè ýòîì ðåøåíèå ÷àñòè÷íî ïåðâîé èñïîëüçóåòñÿ.
Ðåøåíèå ïðèâîäèòü íå áóäó - óæ áîëüíî êîðÿâî âûãëÿäèò, êîãäà ïûòàþñü åãî ôîðìàëüíî îïèñàòü:) - íå ìàòåìàòèê ÿ, ê ñòðîãîñòè íå ïðèó÷åí.
Êñòàòè, ïðèøåë â ãîëîâó åùå îäèí èíòåðåñíûé âàðèàíò ðåøåíèÿ âòîðîé çàäà÷è, íî äî êîíöà äîäóìàòü åãî íå ìîãó.
Âàðèàíò òàêîé - ïðèñâîèòü âñåì âåðøèíàì íîìåðà (óíèêàëüíûå,íî íå ïî ïîðÿäêó, è âñå ïîëîæèòåëüíûå), ó êîðíÿ - ñàìûé áîëüøîé íîìåð, ïðè ïîðîæäåíèè íîâûõ âåðøèí èõ íîìåðà äîëæíû áûòü ìåíüøå íîìåðà óäàëÿåìîé. Ïðè òàêîì ïîäõîäå ñóùåñòâîâàíèå ðåøåíèÿ î÷åâèäíî (øàãîâ áóäåò íå áîëüøå, ÷åì íîìåð êîðíåâîé âåðøèíû). À òàê êàê âîîáùå ðåøåíèå ñóùåñòâóåò - íîìåðà ïðèñâîèòü ìîæíî. Îñòàëîñü ìàëîñòü - ïðèäóìàòü ôóíêöèþ, îáðàçóþùóþ òðåáóåìóþ íóìåðàöèþ.