?

Log in

No account? Create an account
геркулес и гидра (математика) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

геркулес и гидра (математика) [фев. 21, 2002|01:29 pm]
Anatoly Vorobey
Вот любопытная математическая задачка.
Если кто уже знает решение, не отвечайте.
Об очень интересной связи этой задачки с мат. логикой будет отдельная запись, после того, как в комментах появится правильное решение (или я сам его напишу). Если в комментах появится правильное решение, я сообщу об этом в апдейте здесь.

Итак, у нас есть гидра и Геркулес, который хочет её победить.
Гидра - любое конечное дерево, растущее из одного корня. Количество "сыновей" каждой вершины не ограничено (но конечно), равно как и высота дерева.
(заранее прошу прощения на случай, если моя терминология не совпадает с принятой в России — я нахально перевожу термины с английского)
Пример гидры с корнем в вершине А:
        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:
[User Picture]From: french_man
2002-02-21 04:09 am

Насчет 2. что-то не то, если не дать определение стратегии. Если "стратегия" в том, чтобы все время рубить вершины с дедушкой, то их к-во будет увеличиваться. Или ты хочешь сказать, что рано или поздно вершин с дедушками не останется? Как-то не верится на первый взгляд.
(Ответить) (Thread)
[User Picture]From: french_man
2002-02-21 04:13 am

Ой, пардон, и в самом деле уменьшается. Класс, пойду додумывать.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-02-21 04:21 am
;)

(если тебе вдруг нужно формальное определение стратегии, то это функция, которая принимает пару <дерево, номер хода> и выдает значением какую-то голову этого дерева).
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2002-02-21 04:37 am
Но мораль мне нравится: типа, что мозгов Геркулесу не надо. Руби себе...
(Ответить) (Parent) (Thread)
[User Picture]From: ejkov
2002-02-21 04:29 am

Если отрубить лист В можно ли тогда считать вершину С корнем дерева ?
Или же корнем по прежнему остается вершина А?
То есть если отрубить В, можно ли после этого рубить А, (как лист от дерева с корнем С)?
(Ответить) (Thread)
[User Picture]From: avva
2002-02-21 04:31 am

Re:

Нет, корень дерева всегда остаётся один и тот же.

Формально говоря, гидра это объект (T,r), где Т - конечное дерево, а r - фиксированная вершина T, которая называется корнем.
(Ответить) (Parent) (Thread)
[User Picture]From: talash
2002-02-21 04:42 am

solution

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.
(Ответить) (Thread)
[User Picture]From: avva
2002-02-21 04:56 am

Re: solution

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.
(Ответить) (Parent) (Thread)
[User Picture]From: talash
2002-02-21 05:21 am

elaboration of the solution

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.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-02-21 05:31 am

Re: elaboration of the solution

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.
(Ответить) (Parent) (Thread)
[User Picture]From: trurle
2002-02-21 04:46 am
1. When Hercules cut the head on level N that is the only descendant of its' father, it doesn't increase number of heads on level N - instead, new heads appear on level N-1.
2. When Hercules cut the head on level N that has siblings, it increases number of heads on level N - but new heads has less siblings. Whatever head Hercules decides to cut, it bring it closer to the situation when all heads has no siblings - and then depth of tree decreases, until hydra is dead.

(Ответить) (Thread)
[User Picture]From: avva
2002-02-21 05:00 am
2. When Hercules cut the head on level N that has siblings, it increases number of heads on level N - but new heads has less siblings. Whatever head Hercules decides to cut, it bring it closer to the situation when all heads has no siblings - and then depth of tree decreases, until hydra is dead.

This is not nearly precise enough to qualify as a proof. Why does the cutting of a head bring the hydra closer to this situation? It's true that the copies of the subtree that are grown from the grandfather all have "fathers" with one less son in them -- the son corresponding to the chopped head. However, the siblings of the chopped head may themselves be not heads, but rather vertices from which huge trees grow, and these huge trees are now getting replicated an enormous number of times (that grows as the number of moves grows). So why couldn't it be that by cutting heads "unluckily", you always generate so many copies of existing large trees that you'll never run out of heads to chop?

I mean, it _can't be_, really, but you didn't prove that.
(Ответить) (Parent) (Thread)
[User Picture]From: novikov
2002-02-21 05:53 am

Наверное, общее доказательство может быть примерно таким:
В результате любого хода Геркулеса (отсечения головы) не увеличивается ни количество "уровней вложения" Гидры, ни "разветвленность" ветвей на предыдущем уровне. Разветвленность же копий, возникающих на пред-предыдущем уровне неизменно уменьшается (каждая копия имеет на одну голову меньше, чем усеченный "оригинал").
Это неизменно приведет к постепенному уничтожению Гидры.
Или это недостаточное объяснение?

(Ответить) (Thread)
[User Picture]From: avva
2002-02-21 06:45 am
Явно недостаточное.
Уменьшающаяся разветвлённость копий может быть компенсирована их исключительно быстрым ростом. Не говоря уж о том, что при росте голов копируются целые огромные деревья (нижних уровней), у которых разветвлённость при этом не исчезает.

Т.е. это опять-таки всего лишь пересказ интуитивного ошущения "сужения" деревьев, без строгого доказательства (см. также ниже мой коммент по этому поводу).
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-02-21 06:15 am

vague solution

1. Chopping a head decreases number of heads growing out of it's father from N to N-1(trivial)
2. All new "uncles" the grandfather produces, have N-1 children each on the level of the chopped head. Children reproduced on lower levels are irrelevant.
3. Thus, each father on the second-lowest level will have only one child (head).
4. Moreover, eventually the hydra will not have heads on any level other than the lowest one.
I mean, the hydra will look like that :
A
/ \
B C
/ \
D E

5. Then, by chopping any head, we decrease the number of heads on the lowest level (of course, the heads on the second-lowest level increase, but it's irrelevant).
6. Thus we destroy the hydra level by level.

Any luck?


(Ответить) (Thread)
[User Picture]From: avva
2002-02-21 06:32 am

Re: vague solution

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.
(Ответить) (Parent) (Thread)
[User Picture]From: davidl
2002-02-21 06:27 am
Попробуем так: Рассмотрим дерево высоты 2 и покажем, что при любой стратегии Геркулес приходит к дереву с высотой один. Пусть max это макс. кол-во сыновей у под-дерева высоты 1 в каждый ход. Если есть проигрышная стратегия, то max в какой-то момент прекращает уменьшаться, это значит Геркулес не трогает с этого
момента это поддерево. Тогда пусть pair-max это максимальная сумма сыновей каких-то двух поддеревьев высоты 1. Одно из них это max дерево, а другое это меньше max, но больше всех остальных. Начиная с какого-то шага в проигрышной стратегии pair-max прекращает уменьшаться, иначе опять обрубим все деревья высоты 1, поэтому и второе дерево в паре нельзя торгать. По индукции в какой-то момент в проигрышной стратегии нельзя трогать никакое под-дерево высоты 1.
Поэтому нельзя трогать ни одно под-дерево высоты 2 в проигрышной стратегии в какой-то момент, а значит её нет.
(Ответить) (Thread)
[User Picture]From: avva
2002-02-21 06:42 am
Два прокола:

1. (менее важный): несколько под-деревьев высотой 1 могут иметь одно и то же кол-во сыновей max.
2. (более важный): "по индукции" не работает. Количество существующих под-деревьев высотой 1 растёт (потенциально) гораздо быстрее, чем твои ограничения "нельзя трогать одно под-дерево начиная с шага N1... два под-дерева с шага N2... три под-дерева с шага N3...". Может быть, что кол-во поддеревьев на шаге X всегда будет оказываться больше числа тех, на к-е существуют ограничения к этому моменту.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-02-21 06:31 am

гы.

1. срубание головы, являющейся единственным ребенком не ведет к появлению новых голов на текущем уровне. (тут все понятно вроде ;)
2. срубание головы, не являющейся единственным ребенком - приводит к увеличению детей на _предыдущем_ уровне, но к уменьшению детей у одного родителя на текущем. то есть, удар по голове с M братьями приводит к появлению N "дядей" с M-1 детьми, отсюда, количество детей у каждой, отдельно взятой головы стремится к нулю (увеличивая при этом количество голов на уровне N-1) и см. п.1.
соответственно, вырубая только самые младшие головы количество уровней стремится к нулю. а как только уровней останется 2, головы перестанут плодиться, что означает их медленную и мучительную смерть.
DEmm.
(Ответить) (Thread)
[User Picture]From: avva
2002-02-21 06:37 am

Re: гы.

2. срубание головы, не являющейся единственным ребенком - приводит к увеличению детей на _предыдущем_ уровне, но к уменьшению детей у одного родителя на текущем. то есть, удар по голове с M братьями приводит к появлению N "дядей" с M-1 детьми, отсюда, количество детей у каждой, отдельно взятой головы стремится к нулю (увеличивая при этом количество голов на уровне N-1) и см. п.1.

У голов не бывает детей ;) головы - это как раз вершины без детей.

Чтобы это приобрело связность, Вам нужно определить, что именно стремится к нулю. И доказать ;)

Понятно, что есть "общее ощущение" того, что после рубки каждой головы деревья как бы становятся "уже". И то, что их кол-во резко растёт их от этого сужения не спасает. Проблема в том, чтобы это интуитивное ощущение строго определить и доказать, в этом и состоит вся задача по сути дела. До сих пор все предлагаемые решения просто переводили это ощущение из одной словесной формы в другую.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2002-02-21 08:32 am
1. - понятно: среди шей без внуков выбирать самую многоголовую и бить по ней.

2. - ??????????
(Ответить) (Thread)
[User Picture]From: avva
2002-02-21 08:36 am

Re:

Собираюсь где-то завтра днём решение 2 опубликовать.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2002-02-21 08:48 am
Я думаю, что до завтра я справлюсь.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2002-02-21 10:06 am
Уже есть. Сейчас попытаюсь записать.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2002-02-21 11:57 am
Все еще есть дырка. Пока займусь другим, потом вернусь.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-02-24 05:04 pm

идея такая (для первой задачи)

Пусть мы находимся на произвольном шаге (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 и т.д.
Думаю, смысл стратегии ясен, и тот факт, что все происходит в пределах конечных чисел, тоже


Со второй задачей - облом
Не мочу четко уяснить, что _уменьшается_ при уничтожении произвольного сына
Хочется еще подумать
Кстати - а откуда такая задача?

(Ответить) (Thread)
[User Picture]From: avva
2002-02-24 10:20 pm

Re:

Всё правильно насчёт первой задачи.
Вторая задача такими способами не решается, увы.

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

О том, откуда взялась задача, тоже вскоре станет ясно, если будете следить за моим дневником ;) я планирую объяснить её значение и происхождение сегодня или завтра.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-02-25 09:50 am
>Вторая задача такими способами не решается, увы.
Вроде решил и вторую, при этом решение частично первой используется.
Решение приводить не буду - уж больно коряво выглядит, когда пытаюсь его формально описать:) - не математик я, к строгости не приучен.
Кстати, пришел в голову еще один интересный вариант решения второй задачи, но до конца додумать его не могу.
Вариант такой - присвоить всем вершинам номера (уникальные,но не по порядку, и все положительные), у корня - самый большой номер, при порождении новых вершин их номера должны быть меньше номера удаляемой. При таком подходе существование решения очевидно (шагов будет не больше, чем номер корневой вершины). А так как вообще решение существует - номера присвоить можно. Осталось малость - придумать функцию, образующую требуемую нумерацию.
(Ответить) (Parent) (Thread)
From: hewolf
2002-02-28 02:01 am

Хорошая задача. Сразу вспомнились времена, когда новая, найденная где-либо, задача сулила уйму потраченного на нее времени и огромное количество удовольствия.

Наверное уже есть решение. Я пока не читал, проверю сам себя.

Вторая задача:
1. Гидра не способна расти вверх (увеличивать высоту дерева),
Жалко гидру на самом-то деле;) Ни единого ведь шанса.
2. Рано или поздно возникнет ситуация, когда останется
только корень и куча голов идущих от него. И не суть
важно, что голов может быть ->unlim, все равно конечное
количество.
3. При достижение пунка 2 гидра перестанет расти вширь и рано
или поздно умрет.

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

Так же очень интересным бы стало попатыться рассчитать зависимость необходимого количества ходов от известных показателей. Мне кажется что достаточными показателями станут количество внуков и их соответствующий уровень в дереве. Подумаем.
(Ответить) (Thread)
[User Picture]From: melji
2002-04-05 03:48 pm

Взгляд со стороны физики.

При таком интенсивном размножении голов гидры,
оценка количества ходов содержит и факториалы и степени в степени.
Даже если Геркулес будет махать мечом, как лопостями мясорубки, то и простенькую гидру без наворотов
не удастся убить за время жизни Солнечной системы.
Поэтому: Какой бы техникой и стратегией не обладал Геркулес, всегда можно предложить ему непобедимую гидру.

Эх, разные науки - разные ответы.

(Ответить) (Thread)
[User Picture]From: gul_kiev
2015-01-14 05:33 am
Случайно обнаружил ваш старый и очень интересный пост (точнее, серию постов).

Я тут вижу парадокс: формулировка задачи вполне соответствует интерпретации, поэтому обязательно должно быть решение в рамках этой нашей интерпретации, но оказывается, что его нет в рамках аксиоматики Пеано. Ординалы и прочие операции с бесконечностями, как с существующими объектами ("три математика были осуждены на алеф-ноль дней заключения, отсидели срок и вышли", "собака догоняет человека, находящегося на бесконечном расстоянии от неё" и т.п.), как мне кажется, выходят за рамки интерпретации, это операции с полностью абстрактными сущностями ("глокая куздра"), а потому тут возможны парадоксы и противоречия. Если рассмотрим множество всех ординалов, получим парадокс Рассела, поэтому будем называть их не множеством, а классом - на мой взгляд, это просто уловка. А счётные ординалы при этом образуют множество (которое является первым несчётным ординалом) - почему так?

Поэтому я задался целью найти решение задачи в рамках интерпретации, после чего выяснить, на каком этапе возникает расхождение между интерпретацией и аксиоматикой.

После двух дней размышлений (разумеется, не непрерывных) задача свелась к следующей. Есть пара натуральных чисел (n1, n2). Одним действием можно уменьшить любое из чисел, если оно больше нуля. Но если мы уменьшаем n1, то число n2 изменяется произвольным неизвестным нам образом. Верно ли, что мы при любых начальных условиях неминуемо за конечное количество действий придём к паре (0, 0)?

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

Edited at 2015-01-14 06:37 (UTC)
(Ответить) (Thread)