Задача о Геркулесе и Гидре
Привет, Пикабу, мой предыдущий пост не утонул в минусах, а @allozovsky напомнил мне о моем обещании, поэтому продолжу.
Среди математиков в одно время возникла задача о Геркулесе и Гидре. Кто ее предложил, я не знаю, я с ней познакомился в ЖЖ у автора avva, который, между прочим, был в свое время одним из ведущих программистов ЖЖ, а сейчас работает в Гугле.
Задача такая: Геракл находит Гидру, которая состоит из щупалец, из которых растут еще щупальца, из которых растут еще щупальца..., но эта иерархия конечна, и начинает ее рубить беспорядочно. При этом, после отрубания щупальца сразу вырастает два щупальца, но уровнем ниже. Вопрос: сможет ли Геркулес с такой тактикой дорубить Гидру до полного отсутствия щупалец, или нет? Учитываем еще то, что Геркулес смертный, и у него есть только конечное время, чтобы с эту гадину убить.
Вообще, чисто интуитивно кажется, что да, а вот доказать это математически строго довольно сложно.
Даже так, чтобы решить эту задачу (и подобные задачи), пришлось придумать числа, бОльшие, чем бесконечность.
В стандартной арифметике, которую преподают в школе, эту задачу решить невозможно.
Для решения этой задачи математикам пришлось придумать новое понятие, ординалы.
Первый ординал обозначается как w (на самом деле, немного по другому, более скругленно, но почему-то в Юникоде, похоже, нет символа для ординала)
Первый ординал - это, можно сказать, число, на один большее чем бесконечность. дальше идет число w+1, дальше w+2, вплоть до w+w, который, естественно, равен 2*w, и так далее, доходя до w в степени w, но на нем не заканчиваясь.
В чем отличие ординалов от действительных чисел, спросите вы (естественно, никто, не спросит, досюда мало кто дочитает, на самом деле) - а в том, что любая нисходящая последовательность за конечное количество членов последовательности дойдет до нуля, а в действительных числах нисходящая последовательность до нуля может не доходить. Поэтому, задача о Гидре не решается в понятиях действительных чисел.
Дальше идет копипаста решения задачи о Гидре, кто хочет, может ознакомиться:
Пусть T - некоторая гидра. Мы присваиваем ординал каждой вершине T следующим образом. Каждый лист (голова) Т получает значение 0. Если A - некоторая вершина T с детьми, которым мы уже присвоили значения a, b, c, ... u, то вершине A мы присваиваем значение
wa+wb+...+wu.
(техническое замечание для педантов: a...u перед этим выстраиваем в невозрастающем порядке).
По определению w0 = 1.
Ординалом всей гидры T назовём ординал, который мы присвоим при помощи такой процедуры корню дерева.
Лемма: после каждого хода Геркулеса ординал гидры уменьшается. То есть, если On - ординал гидры после n-го хода, то On+1 < On (неравенство точное!).
Доказательство: Легко видеть, что достаточно, во-первых, доказать, что после каждого хода ординал дедушки отсечённой головы уменьшается (процедура отсечения меняет только под-дерево начиная с дедушки; кроме того, при уменьшении значения любой вершины по индукции видим, что уменьшается значение корня - это не совершенно тривиальное, но лёгкое утверждение, использующее свойства ординальной арифметики).
Далее, ясно, что можно игнорировать существующих до отсечения "дядей" отсекаемой головы - их вклад в "дедушку" до и после отсечения не меняется.
Пусть таким образом у нас будет "дедушка" A с единственным сыном, "папой" B, у которого есть какие-то сыновья C_1, C_2, ... C_k (необязательно головы), плюс сын-голова D, которую мы отсекаем. Обозначим ординал вершины при помощи функции F. Тогда до отсечения
F(B) = wF(C_1)+...+wF(C_k) + w0.
Обозначим wF(C_1)+...+wF(C_k) = FC. Тогда опять-таки до отсечения
F(B) = FC + w0 = FC + 1.
F(A) = wF(B) = wFC+1 = wFC * w.
После отсечения мы получаем вместо одного "папы" B — N копий B (где N на единицу больше номера хода), у каждой из которых будет ординал FC (т.к. голову D, дающую добавку 1 к ординалу "папы", мы отсекли). Поэтому после отсечения
F(A) = wFC * N.
Сразу видим, что в результате отсечения F(A) уменьшилось. Умножение на сколь угодно большое число N даёт заведомо меньший результат, чем умножение на омегу. Лемма доказана.
Теперь нам осталось только вспомнить, что не бывает бесконечных строго нисходящих последовательностей ординалов (напомню, что ординалы образуют хорошо упорядоченный класс). Следовательно, за конечное число шагов Геркулес приведёт гидру к состоянию, в котором у неё будет ординал 0, т.е. всего одна голова. Что и требовалось доказать.
Использованные материалы:
https://avva.livejournal.com/244874.html
https://avva.livejournal.com/245918.html
Upd: тут в комментариях некто @gorzo1 настойчиво попросил апдейтнуть мой пост двумя предложениями:
"Геракл находит Гидру, которая состоит из щупалец, из которых растут еще щупальца, из которых растут еще щупальца", но которые растут только на уровень вверх.
И способность Геракла рубить щупальца мы принимаем за аксиому
За эти два предложения я не несу никакой ответственности, если они вам нравятся, лайкайте именно его, если не нравятся, дизлайкайте тоже именно его.
Лига математиков
906 постов2.5K подписчика