June 8th, 2018

Парадокс голубоглазых островитян (часть 3, окончательная)



Первая часть
Вторая часть

…в общем-то, понятно, что хотели сказать авторы задачи. Что-то типа: «островитяне не могут сообщать другим цвет их глаз, кроме как вот этими вот своими самоубийствами».

Эта формулировка выглядит крайне натянутой, однако рекурсивное решение приводит к вымиранию всего острова только с ней — такой вот натянутой.

Или не приводит?


О боже мой, а что ещё-то?



Казалось бы, если закрыть глаза на неопределённость приоритетов и ввести «натянутую формулировку», то рекурсия должна работать: ведь даже в обсуждении проблем с приоритетами предполагалось, что она работает. В ней-то где ошибка?

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

Collapse )