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

[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

[french-man.livejournal.com]

Íàñ÷åò 2. ÷òî-òî íå òî, åñëè íå äàòü îïðåäåëåíèå ñòðàòåãèè. Åñëè "ñòðàòåãèÿ" â òîì, ÷òîáû âñå âðåìÿ ðóáèòü âåðøèíû ñ äåäóøêîé, òî èõ ê-âî áóäåò óâåëè÷èâàòüñÿ. Èëè òû õî÷åøü ñêàçàòü, ÷òî ðàíî èëè ïîçäíî âåðøèí ñ äåäóøêàìè íå îñòàíåòñÿ? Êàê-òî íå âåðèòñÿ íà ïåðâûé âçãëÿä.

[french-man.livejournal.com]

Îé, ïàðäîí, è â ñàìîì äåëå óìåíüøàåòñÿ. Êëàññ, ïîéäó äîäóìûâàòü.

[avva.livejournal.com]

;)

(åñëè òåáå âäðóã íóæíî ôîðìàëüíîå îïðåäåëåíèå ñòðàòåãèè, òî ýòî ôóíêöèÿ, êîòîðàÿ ïðèíèìàåò ïàðó <äåðåâî, íîìåð õîäà> è âûäàåò çíà÷åíèåì êàêóþ-òî ãîëîâó ýòîãî äåðåâà).

[ejkov.livejournal.com]

Åñëè îòðóáèòü ëèñò  ìîæíî ëè òîãäà ñ÷èòàòü âåðøèíó Ñ êîðíåì äåðåâà ?
Èëè æå êîðíåì ïî ïðåæíåìó îñòàåòñÿ âåðøèíà À?
Òî åñòü åñëè îòðóáèòü Â, ìîæíî ëè ïîñëå ýòîãî ðóáèòü À, (êàê ëèñò îò äåðåâà ñ êîðíåì Ñ)?

Re:

[avva.livejournal.com]

Íåò, êîðåíü äåðåâà âñåãäà îñòà¸òñÿ îäèí è òîò æå.

Ôîðìàëüíî ãîâîðÿ, ãèäðà ýòî îáúåêò (T,r), ãäå Ò - êîíå÷íîå äåðåâî, à r - ôèêñèðîâàííàÿ âåðøèíà T, êîòîðàÿ íàçûâàåòñÿ êîðíåì.

[french-man.livejournal.com]

Íî ìîðàëü ìíå íðàâèòñÿ: òèïà, ÷òî ìîçãîâ Ãåðêóëåñó íå íàäî. Ðóáè ñåáå...

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.

[trurle.livejournal.com]

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.

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.

[avva.livejournal.com]

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.

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.

[novikov.livejournal.com]

Íàâåðíîå, îáùåå äîêàçàòåëüñòâî ìîæåò áûòü ïðèìåðíî òàêèì:
 ðåçóëüòàòå ëþáîãî õîäà Ãåðêóëåñà (îòñå÷åíèÿ ãîëîâû) íå óâåëè÷èâàåòñÿ íè êîëè÷åñòâî "óðîâíåé âëîæåíèÿ" Ãèäðû, íè "ðàçâåòâëåííîñòü" âåòâåé íà ïðåäûäóùåì óðîâíå. Ðàçâåòâëåííîñòü æå êîïèé, âîçíèêàþùèõ íà ïðåä-ïðåäûäóùåì óðîâíå íåèçìåííî óìåíüøàåòñÿ (êàæäàÿ êîïèÿ èìååò íà îäíó ãîëîâó ìåíüøå, ÷åì óñå÷åííûé "îðèãèíàë").
Ýòî íåèçìåííî ïðèâåäåò ê ïîñòåïåííîìó óíè÷òîæåíèþ Ãèäðû.
Èëè ýòî íåäîñòàòî÷íîå îáúÿñíåíèå?

vague solution

[(Anonymous)]

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?

[davidl.livejournal.com]

Ïîïðîáóåì òàê: Ðàññìîòðèì äåðåâî âûñîòû 2 è ïîêàæåì, ÷òî ïðè ëþáîé ñòðàòåãèè Ãåðêóëåñ ïðèõîäèò ê äåðåâó ñ âûñîòîé îäèí. Ïóñòü max ýòî ìàêñ. êîë-âî ñûíîâåé ó ïîä-äåðåâà âûñîòû 1 â êàæäûé õîä. Åñëè åñòü ïðîèãðûøíàÿ ñòðàòåãèÿ, òî max â êàêîé-òî ìîìåíò ïðåêðàùàåò óìåíüøàòüñÿ, ýòî çíà÷èò Ãåðêóëåñ íå òðîãàåò ñ ýòîãî
ìîìåíòà ýòî ïîääåðåâî. Òîãäà ïóñòü pair-max ýòî ìàêñèìàëüíàÿ ñóììà ñûíîâåé êàêèõ-òî äâóõ ïîääåðåâüåâ âûñîòû 1. Îäíî èç íèõ ýòî max äåðåâî, à äðóãîå ýòî ìåíüøå max, íî áîëüøå âñåõ îñòàëüíûõ. Íà÷èíàÿ ñ êàêîãî-òî øàãà â ïðîèãðûøíîé ñòðàòåãèè pair-max ïðåêðàùàåò óìåíüøàòüñÿ, èíà÷å îïÿòü îáðóáèì âñå äåðåâüÿ âûñîòû 1, ïîýòîìó è âòîðîå äåðåâî â ïàðå íåëüçÿ òîðãàòü. Ïî èíäóêöèè â êàêîé-òî ìîìåíò â ïðîèãðûøíîé ñòðàòåãèè íåëüçÿ òðîãàòü íèêàêîå ïîä-äåðåâî âûñîòû 1.
Ïîýòîìó íåëüçÿ òðîãàòü íè îäíî ïîä-äåðåâî âûñîòû 2 â ïðîèãðûøíîé ñòðàòåãèè â êàêîé-òî ìîìåíò, à çíà÷èò å¸ íåò.

ãû.

[(Anonymous)]

1. ñðóáàíèå ãîëîâû, ÿâëÿþùåéñÿ åäèíñòâåííûì ðåáåíêîì íå âåäåò ê ïîÿâëåíèþ íîâûõ ãîëîâ íà òåêóùåì óðîâíå. (òóò âñå ïîíÿòíî âðîäå ;)
2. ñðóáàíèå ãîëîâû, íå ÿâëÿþùåéñÿ åäèíñòâåííûì ðåáåíêîì - ïðèâîäèò ê óâåëè÷åíèþ äåòåé íà _ïðåäûäóùåì_ óðîâíå, íî ê óìåíüøåíèþ äåòåé ó îäíîãî ðîäèòåëÿ íà òåêóùåì. òî åñòü, óäàð ïî ãîëîâå ñ M áðàòüÿìè ïðèâîäèò ê ïîÿâëåíèþ N "äÿäåé" ñ M-1 äåòüìè, îòñþäà, êîëè÷åñòâî äåòåé ó êàæäîé, îòäåëüíî âçÿòîé ãîëîâû ñòðåìèòñÿ ê íóëþ (óâåëè÷èâàÿ ïðè ýòîì êîëè÷åñòâî ãîëîâ íà óðîâíå N-1) è ñì. ï.1.
ñîîòâåòñòâåííî, âûðóáàÿ òîëüêî ñàìûå ìëàäøèå ãîëîâû êîëè÷åñòâî óðîâíåé ñòðåìèòñÿ ê íóëþ. à êàê òîëüêî óðîâíåé îñòàíåòñÿ 2, ãîëîâû ïåðåñòàíóò ïëîäèòüñÿ, ÷òî îçíà÷àåò èõ ìåäëåííóþ è ìó÷èòåëüíóþ ñìåðòü.
DEmm.

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.

Re: ãû.

[avva.livejournal.com]

2. ñðóáàíèå ãîëîâû, íå ÿâëÿþùåéñÿ åäèíñòâåííûì ðåáåíêîì - ïðèâîäèò ê óâåëè÷åíèþ äåòåé íà _ïðåäûäóùåì_ óðîâíå, íî ê óìåíüøåíèþ äåòåé ó îäíîãî ðîäèòåëÿ íà òåêóùåì. òî åñòü, óäàð ïî ãîëîâå ñ M áðàòüÿìè ïðèâîäèò ê ïîÿâëåíèþ N "äÿäåé" ñ M-1 äåòüìè, îòñþäà, êîëè÷åñòâî äåòåé ó êàæäîé, îòäåëüíî âçÿòîé ãîëîâû ñòðåìèòñÿ ê íóëþ (óâåëè÷èâàÿ ïðè ýòîì êîëè÷åñòâî ãîëîâ íà óðîâíå N-1) è ñì. ï.1.

Ó ãîëîâ íå áûâàåò äåòåé ;) ãîëîâû - ýòî êàê ðàç âåðøèíû áåç äåòåé.

×òîáû ýòî ïðèîáðåëî ñâÿçíîñòü, Âàì íóæíî îïðåäåëèòü, ÷òî èìåííî ñòðåìèòñÿ ê íóëþ. È äîêàçàòü ;)

Ïîíÿòíî, ÷òî åñòü "îáùåå îùóùåíèå" òîãî, ÷òî ïîñëå ðóáêè êàæäîé ãîëîâû äåðåâüÿ êàê áû ñòàíîâÿòñÿ "óæå". È òî, ÷òî èõ êîë-âî ðåçêî ðàñò¸ò èõ îò ýòîãî ñóæåíèÿ íå ñïàñàåò. Ïðîáëåìà â òîì, ÷òîáû ýòî èíòóèòèâíîå îùóùåíèå ñòðîãî îïðåäåëèòü è äîêàçàòü, â ýòîì è ñîñòîèò âñÿ çàäà÷à ïî ñóòè äåëà. Äî ñèõ ïîð âñå ïðåäëàãàåìûå ðåøåíèÿ ïðîñòî ïåðåâîäèëè ýòî îùóùåíèå èç îäíîé ñëîâåñíîé ôîðìû â äðóãóþ.

[avva.livejournal.com]

Äâà ïðîêîëà:

1. (ìåíåå âàæíûé): íåñêîëüêî ïîä-äåðåâüåâ âûñîòîé 1 ìîãóò èìåòü îäíî è òî æå êîë-âî ñûíîâåé max.
2. (áîëåå âàæíûé): "ïî èíäóêöèè" íå ðàáîòàåò. Êîëè÷åñòâî ñóùåñòâóþùèõ ïîä-äåðåâüåâ âûñîòîé 1 ðàñò¸ò (ïîòåíöèàëüíî) ãîðàçäî áûñòðåå, ÷åì òâîè îãðàíè÷åíèÿ "íåëüçÿ òðîãàòü îäíî ïîä-äåðåâî íà÷èíàÿ ñ øàãà N1... äâà ïîä-äåðåâà ñ øàãà N2... òðè ïîä-äåðåâà ñ øàãà N3...". Ìîæåò áûòü, ÷òî êîë-âî ïîääåðåâüåâ íà øàãå X âñåãäà áóäåò îêàçûâàòüñÿ áîëüøå ÷èñëà òåõ, íà ê-å ñóùåñòâóþò îãðàíè÷åíèÿ ê ýòîìó ìîìåíòó.

[avva.livejournal.com]

ßâíî íåäîñòàòî÷íîå.
Óìåíüøàþùàÿñÿ ðàçâåòâë¸ííîñòü êîïèé ìîæåò áûòü êîìïåíñèðîâàíà èõ èñêëþ÷èòåëüíî áûñòðûì ðîñòîì. Íå ãîâîðÿ óæ î òîì, ÷òî ïðè ðîñòå ãîëîâ êîïèðóþòñÿ öåëûå îãðîìíûå äåðåâüÿ (íèæíèõ óðîâíåé), ó êîòîðûõ ðàçâåòâë¸ííîñòü ïðè ýòîì íå èñ÷åçàåò.

Ò.å. ýòî îïÿòü-òàêè âñåãî ëèøü ïåðåñêàç èíòóèòèâíîãî îøóùåíèÿ "ñóæåíèÿ" äåðåâüåâ, áåç ñòðîãîãî äîêàçàòåëüñòâà (ñì. òàêæå íèæå ìîé êîììåíò ïî ýòîìó ïîâîäó).

[french-man.livejournal.com]

1. - ïîíÿòíî: ñðåäè øåé áåç âíóêîâ âûáèðàòü ñàìóþ ìíîãîãîëîâóþ è áèòü ïî íåé.

2. - ??????????

Re:

[avva.livejournal.com]

Ñîáèðàþñü ãäå-òî çàâòðà äí¸ì ðåøåíèå 2 îïóáëèêîâàòü.

[french-man.livejournal.com]

ß äóìàþ, ÷òî äî çàâòðà ÿ ñïðàâëþñü.

[french-man.livejournal.com]

Óæå åñòü. Ñåé÷àñ ïîïûòàþñü çàïèñàòü.

[french-man.livejournal.com]

Âñå åùå åñòü äûðêà. Ïîêà çàéìóñü äðóãèì, ïîòîì âåðíóñü.

[(Anonymous)]

èäåÿ òàêàÿ (äëÿ ïåðâîé çàäà÷è)

Ïóñòü ìû íàõîäèìñÿ íà ïðîèçâîëüíîì øàãå (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:

[avva.livejournal.com]

Âñ¸ ïðàâèëüíî íàñ÷¸ò ïåðâîé çàäà÷è.
Âòîðàÿ çàäà÷à òàêèìè ñïîñîáàìè íå ðåøàåòñÿ, óâû.

Ïîäóìàéòå, åñëè õîòèòå, íî ó÷òèòå, ÷òî å¸ ðåøåíèå ÿ óæå çàïèñàë â ñâî¸ì äíåâíèêå (íà äåíü ïîçæå ýòîé çàïèñè). Ñåãîäíÿ åù¸ ïëàíèðóþ îáúÿñíèòü äëÿ òåõ, êòî ýòîãî íå çíàåò, íóæíóþ ìàòåìàòè÷åñêóþ òåðìèíîëîãèþ äëÿ îáúÿñíåíèÿ ðåøåíèÿ.

Î òîì, îòêóäà âçÿëàñü çàäà÷à, òîæå âñêîðå ñòàíåò ÿñíî, åñëè áóäåòå ñëåäèòü çà ìîèì äíåâíèêîì ;) ÿ ïëàíèðóþ îáúÿñíèòü å¸ çíà÷åíèå è ïðîèñõîæäåíèå ñåãîäíÿ èëè çàâòðà.

[(Anonymous)]

>Âòîðàÿ çàäà÷à òàêèìè ñïîñîáàìè íå ðåøàåòñÿ, óâû.
Âðîäå ðåøèë è âòîðóþ, ïðè ýòîì ðåøåíèå ÷àñòè÷íî ïåðâîé èñïîëüçóåòñÿ.
Ðåøåíèå ïðèâîäèòü íå áóäó - óæ áîëüíî êîðÿâî âûãëÿäèò, êîãäà ïûòàþñü åãî ôîðìàëüíî îïèñàòü:) - íå ìàòåìàòèê ÿ, ê ñòðîãîñòè íå ïðèó÷åí.
Êñòàòè, ïðèøåë â ãîëîâó åùå îäèí èíòåðåñíûé âàðèàíò ðåøåíèÿ âòîðîé çàäà÷è, íî äî êîíöà äîäóìàòü åãî íå ìîãó.
Âàðèàíò òàêîé - ïðèñâîèòü âñåì âåðøèíàì íîìåðà (óíèêàëüíûå,íî íå ïî ïîðÿäêó, è âñå ïîëîæèòåëüíûå), ó êîðíÿ - ñàìûé áîëüøîé íîìåð, ïðè ïîðîæäåíèè íîâûõ âåðøèí èõ íîìåðà äîëæíû áûòü ìåíüøå íîìåðà óäàëÿåìîé. Ïðè òàêîì ïîäõîäå ñóùåñòâîâàíèå ðåøåíèÿ î÷åâèäíî (øàãîâ áóäåò íå áîëüøå, ÷åì íîìåð êîðíåâîé âåðøèíû). À òàê êàê âîîáùå ðåøåíèå ñóùåñòâóåò - íîìåðà ïðèñâîèòü ìîæíî. Îñòàëîñü ìàëîñòü - ïðèäóìàòü ôóíêöèþ, îáðàçóþùóþ òðåáóåìóþ íóìåðàöèþ.

[hewolf.livejournal.com]

Õîðîøàÿ çàäà÷à. Ñðàçó âñïîìíèëèñü âðåìåíà, êîãäà íîâàÿ, íàéäåííàÿ ãäå-ëèáî, çàäà÷à ñóëèëà óéìó ïîòðà÷åííîãî íà íåå âðåìåíè è îãðîìíîå êîëè÷åñòâî óäîâîëüñòâèÿ.

Íàâåðíîå óæå åñòü ðåøåíèå. ß ïîêà íå ÷èòàë, ïðîâåðþ ñàì ñåáÿ.

Âòîðàÿ çàäà÷à:
1. Ãèäðà íå ñïîñîáíà ðàñòè ââåðõ (óâåëè÷èâàòü âûñîòó äåðåâà),
Æàëêî ãèäðó íà ñàìîì-òî äåëå;) Íè åäèíîãî âåäü øàíñà.
2. Ðàíî èëè ïîçäíî âîçíèêíåò ñèòóàöèÿ, êîãäà îñòàíåòñÿ
òîëüêî êîðåíü è êó÷à ãîëîâ èäóùèõ îò íåãî. È íå ñóòü
âàæíî, ÷òî ãîëîâ ìîæåò áûòü ->unlim, âñå ðàâíî êîíå÷íîå
êîëè÷åñòâî.
3. Ïðè äîñòèæåíèå ïóíêà 2 ãèäðà ïåðåñòàíåò ðàñòè âøèðü è ðàíî
èëè ïîçäíî óìðåò.

Êàê ïîêàçûâàþò íåñëîæíûå ïðèêèäûâàíèÿ ýòî âîçìîæíî âíå çàâèñèìîñòè îò âûáðàííîãî ïîðÿäêà õîäîâ. Åäèíñòâåííîå, ÷òî ìíå èíòåðåñíî, òàê ýòî åñòü ëè çàâèñèìîñòü ïîðÿäêà õîäîâ îò èõ êîëè÷åñòâà. ß îïåðèðóÿ äåðåâüÿìè ëîãèêîé è ÷óòîê èíòóèöèåé ïîêà íå ìîãó íàéòè ýòîãî ðåøåíèÿ. Îíî, ïî ìîåìó, áîëåå èíòåðåñíî, ÷åì ñàìà çàäà÷à.

Òàê æå î÷åíü èíòåðåñíûì áû ñòàëî ïîïàòûòüñÿ ðàññ÷èòàòü çàâèñèìîñòü íåîáõîäèìîãî êîëè÷åñòâà õîäîâ îò èçâåñòíûõ ïîêàçàòåëåé. Ìíå êàæåòñÿ ÷òî äîñòàòî÷íûìè ïîêàçàòåëÿìè ñòàíóò êîëè÷åñòâî âíóêîâ è èõ ñîîòâåòñòâóþùèé óðîâåíü â äåðåâå. Ïîäóìàåì.

Âçãëÿä ñî ñòîðîíû ôèçèêè.

[melji.livejournal.com]

Ïðè òàêîì èíòåíñèâíîì ðàçìíîæåíèè ãîëîâ ãèäðû,
îöåíêà êîëè÷åñòâà õîäîâ ñîäåðæèò è ôàêòîðèàëû è ñòåïåíè â ñòåïåíè.
Äàæå åñëè Ãåðêóëåñ áóäåò ìàõàòü ìå÷îì, êàê ëîïîñòÿìè ìÿñîðóáêè, òî è ïðîñòåíüêóþ ãèäðó áåç íàâîðîòîâ
íå óäàñòñÿ óáèòü çà âðåìÿ æèçíè Ñîëíå÷íîé ñèñòåìû.
Ïîýòîìó: Êàêîé áû òåõíèêîé è ñòðàòåãèåé íå îáëàäàë Ãåðêóëåñ, âñåãäà ìîæíî ïðåäëîæèòü åìó íåïîáåäèìóþ ãèäðó.

Ýõ, ðàçíûå íàóêè - ðàçíûå îòâåòû.

[gul-kiev.livejournal.com]

Случайно обнаружил ваш старый и очень интересный пост (точнее, серию постов).

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

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

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

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