February 21st, 2002

moose, transparent

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

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

Итак, у нас есть гидра и Геркулес, который хочет её победить.
Гидра - любое конечное дерево, растущее из одного корня. Количество "сыновей" каждой вершины не ограничено (но конечно), равно как и высота дерева.
(заранее прошу прощения на случай, если моя терминология не совпадает с принятой в России — я нахально перевожу термины с английского)
Пример гидры с корнем в вершине А:Collapse )
moose, transparent

Тезей и Минотавр (лабиринт)

Андрей Асиновский прислал отличную ссылку.

Это головоломка: Тезею нужно пройти лабиринт так, чтобы его не поймал Минотавр. На каждый ход Тезея Минотавр делает два хода; в каждом из них он сначала пытается продвинуться ближе к Тезею по горизонтали; если это невозможно - по вертикали; если и это невозможно - остаётся на месте. Это я вкратце повторяю условие, на странице там всё объясняется подробно, но по-английски.

Лабиринт нелёгкий, но не исключительно тяжёлый. Мне понадобилось минут 20 30-35 , чтоб пройти, но я ещё несколько торможу от бессонницы, так что чур сапогами не бить :)