?

Log in

Геркулес и гидра (решение) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

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

Links
[Links:| English-language weblog ]

Геркулес и гидра (решение) [фев. 22, 2002|06:58 pm]
Anatoly Vorobey
Эта запись содержит решение вчерашней задачки про Геркулеса и гидру. Не читайте, если вы не хотите его знать.

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

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

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

Пусть 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, т.е. всего одна голова. Что и требовалось доказать.
СсылкаОтветить

Comments:
[User Picture]From: french_man
2002-02-22 09:09 am

Круто

И все-таки я не верю, что без ординалов не обойтись.
(Ответить) (Thread)
[User Picture]From: avva
2002-02-22 09:14 am

Re: Круто

Без чего-то сопоставимого с ними по сложности не обойтись.
Об этом будет в следующей записи на тему.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2002-02-22 09:40 am

Re: Круто

Вероятно, есть "конвенциональное" решение, если количество прибавляемых голов постоянно (или хотя бы ограниченно). А так, может быть ты и прав.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2002-02-22 10:00 am

Re: Круто

Кстати, для построения теории ординалов аксиома выбора, кажется, формально не нужна. Или нужна? Вот забыл. Надо будет посмотреть.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-02-22 10:01 am

Re: Круто

Не нужна, хотя с ней, как обычно, легче.
(Ответить) (Parent) (Thread)
From: 9000
2002-02-22 10:18 am
А для более простых смертных -- можно ссылку на популярное изложение определения и свойств ординалов? А то слово не особо удобное для поиска гуглем -- много лишнего находится %-)
(Ответить) (Thread)
[User Picture]From: french_man
2002-02-22 10:30 am
Натансон, Теория функций вещественной переменной (или вещественного переменного, точно не помню). Там две коротких и очень четких главки по теории множеств, совершенно независимых от остальной книги. Школьного образования достаточно.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2002-02-22 07:55 pm
Забыл сказать. Там ординалы называются "порядковыми числами". (Книга писалась во время борьбы с космополитизмом.)
(Ответить) (Parent) (Thread)
[User Picture]From: maria_d
2002-02-22 11:49 am
Радость жизни :-) Да, а вот есть такая теорема (аксиома? трудно представить себе доказательство) Дэвиса (Robert Davis): Для всякой задачи существует способ ее презентации, который делает решение очевидным. Понятно, надо ввести некие ограничения, которые делают формулировку менее красивой :-) Думаю над этими двумя задачами, пока ничего очевидным не делается :-)
(Ответить) (Thread)
[User Picture]From: avva
2002-02-25 11:18 pm
Ну, если получится, то расскажите ;)
(Ответить) (Parent) (Thread)
[User Picture]From: boroda
2002-02-22 12:17 pm

O, ja! Das ist fantastishe!

Анатолий! Обязательно напишите "краткое введение в арифметику ординалов, понятное не-математикам". Мы все, не-математематики и сами здесь не местные, будем ждать этого с нетерпением. Это, конечно же, никоим образом не требование, но трепетное ожидание. Аналогичное введение в известном учебнике Колмогорова/Смирнова страдает, имхо, излишней академичностью.

Это, извините, я завтрашний праздник праздную. Возможные сарказмы в предыдущем абзаце суть недобитые рефлексы. Интересно было бы, в самом деле, ознакомится с Вашим подходом к этой теме.
(Ответить) (Thread)
[User Picture]From: french_man
2002-02-22 12:57 pm

Re: O, ja! Das ist fantastishe!

fantastisch
(Ответить) (Parent) (Thread)
[User Picture]From: boroda
2002-02-22 04:59 pm

(Смущённо)

спасибо
(Ответить) (Parent) (Thread)
From: ex_ex_annut
2005-07-17 04:58 pm
простите, Авва, не подскажете, а где простинг про приложения этих идей к логике?
(Ответить) (Thread)
From: ex_ex_annut
2005-07-17 05:02 pm
зс
Но важе доказательство говорит, что любая последовательность отрубки голов приведет к тривиальному дереву.
Зачем тогда во втором вопросе упоминалась стратегия (рубка со стратегией получается частный случай)?
(Ответить) (Thread)
[User Picture]From: avva
2005-07-17 10:51 pm
В PA невозможно формализовать любую последовательность рубки. Стратегия всего лишь означает детерминированный выбор следующего шага для каждой конкретной ситуации, и тогда рубку можно формализовать как набор пар (текущее-состояние, голова-которую-рубим).
(Ответить) (Parent) (Thread)
[User Picture]From: rombell
2009-12-27 11:15 am
1000-я запись в избранном
(Ответить) (Thread)