avva | Геркулес и гидра (решение)

Эта запись содержит решение вчерашней задачки про Геркулеса и гидру. Не читайте, если вы не хотите его знать.

Я вообще очень люблю задачи, которые, несмотря на простое условие, требуют для решения каких-то на первый взгляд не связанных с ними математических абстракций. Например, задача о математиках в тюрьме. К этой категории относится и задача про Геркулеса и гидру, но с ней дела обстоят ещё интереснее. Можно строго доказать и объяснить, почему у этой задачи нет "простого", легко понятного решения. Это доказательство, связывающее её с математической логикой, и делает её особенно интересней. Но об этом подробнее в другой записи. Пока что же я хочу извиниться перед теми, кто не знает, что такое ординалы, потому что решения задачи про Геркулеса и гидру они понять не смогут. В качестве компромисса предлагаю следующее: если есть действительно те, кому непонятно приведенное ниже решение задачи и кто очень хочет его понять, напишите об этом в комментах или лично, а я тогда постараюсь на выходных написать краткое введение в арифметику ординалов, понятное не-математикам и долженствующее сделать доказательство понятным.

Итак, решение.

Буква w обозначает ординал омега (он же алеф-ноль и N, множество натуральных чисел).

Пусть T - некоторая гидра. Мы присваиваем ординал каждой вершине T следующим образом. Каждый лист (голова) Т получает значение 0. Если A - некоторая вершина T с детьми, которым мы уже присвоили значения a, b, c, ... u, то вершине A мы присваиваем значение

w^a+w^b+...+w^u.

(техническое замечание для педантов: a...u перед этим выстраиваем в невозрастающем порядке).
По определению w⁰ = 1.
Ординалом всей гидры T назовём ординал, который мы присвоим при помощи такой процедуры корню дерева.

Лемма: после каждого хода Геркулеса ординал гидры уменьшается. То есть, если O_n - ординал гидры после n-го хода, то O_n+1 < O_n (неравенство точное!).

Доказательство: Легко видеть, что достаточно, во-первых, доказать, что после каждого хода ординал дедушки отсечённой головы уменьшается (процедура отсечения меняет только под-дерево начиная с дедушки; кроме того, при уменьшении значения любой вершины по индукции видим, что уменьшается значение корня - это не совершенно тривиальное, но лёгкое утверждение, использующее свойства ординальной арифметики).
Далее, ясно, что можно игнорировать существующих до отсечения "дядей" отсекаемой головы - их вклад в "дедушку" до и после отсечения не меняется.
Пусть таким образом у нас будет "дедушка" A с единственным сыном, "папой" B, у которого есть какие-то сыновья C_1, C_2, ... C_k (необязательно головы), плюс сын-голова D, которую мы отсекаем. Обозначим ординал вершины при помощи функции F. Тогда до отсечения

F(B) = w^F(C_1)+...+w^F(C_k) + w⁰.

Обозначим w^F(C_1)+...+w^F(C_k) = FC. Тогда опять-таки до отсечения

F(B) = FC + w⁰ = FC + 1.
F(A) = w^F(B) = w^FC+1 = w^FC * w.

После отсечения мы получаем вместо одного "папы" B — N копий B (где N на единицу больше номера хода), у каждой из которых будет ординал FC (т.к. голову D, дающую добавку 1 к ординалу "папы", мы отсекли). Поэтому после отсечения

F(A) = w^FC * N.

Сразу видим, что в результате отсечения F(A) уменьшилось. Умножение на сколь угодно большое число N даёт заведомо меньший результат, чем умножение на омегу. Лемма доказана.

Теперь нам осталось только вспомнить, что не бывает бесконечных строго нисходящих последовательностей ординалов (напомню, что ординалы образуют хорошо упорядоченный класс). Следовательно, за конечное число шагов Геркулес приведёт гидру к состоянию, в котором у неё будет ординал 0, т.е. всего одна голова. Что и требовалось доказать.