Задача про бесконечное количество мудрецов

[KappaGolden]

Вроде как с периодическими последовательностями я разобрался... А как действовать на более общем случае?

[arseniiv]

Я вот просто начал доопределять стратегию по каждой ещё не обработанной последовательности за раз. Это сразу очевидно требует теоремы Цермело и потому принятия аксиомы выбора. (И знакомства с трансфинитной рекурсией/индукцией, это уже со стороны техники доказательства.) Кажется, mihaild имеет какое-то более красивое построение, но мой несчётный перебор как минимум меня вчера железно убедил.

[mihaild]

Будем считать две последовательности эквивалентными, если после сдвига они совпадают, начиная с какого-то элемента. Формально $\exists n, N \forall i > N: x_i = y_{i + n}$.
Как обычно, разобьем последовательности на классы и выберем канонического представителя из каждого класса. Каждый мудрец знает, в каком он классе.
Теперь важный момент: в каждом классе либо есть периодическая последовательность, и тогда все последовательности в нём финально периодические, либо нет ни одной периодической последовательности.
В первом случае всё понятно: каждый мудрец называет шляпу, которая должна быть у него соответственно периоду (а если он видит что период еще не начался - то этому мудрецу не повезло, но таких только конечное число).
Во втором случае мудрец может либо понять, что реальная последовательность отличается от канонической, либо понять, на каком он месте, если последовательность каноническая, причем понимающих что последовательность не каноническая опять же конечное число.

[KappaGolden]

Все понятно, кроме того факта: как мудрец понимает на каком месте он в канонической последовательности?

[mihaild]

Пусть мудрец видит перед собой последовательность $x$, а каноническая последовательность $y$. Если $x$ не является суффиксом $y$, то этому мудрецу просто не повезло (таких будет конечно число). Если является, то для какого-то $n$ выполнено $x_i = y_{n + i}$. Пусть это выполнено еще и для $m > n$. Тогда $x_i = y_{n + i} = y_{m + i}$, откуда $y_i = y{i + (m - n)}$ при $i > n$. Т.е. каноническая последовательность финально периодическая.
А поскольку мы уже договорились что это не так, то $x_i = y_{n + i}$ только для одного $n$. Соответственно мудрец в канонической последовательности стоит на позиции $n$, и смело называет $y_n$.

[arseniiv]

Ага, я делал то же самое, но не объединял в классы — просто смотрим каждый раз на собственные суффиксы очередной последовательности и добавляем все ещё не добавленные с соответствующими шляпами, сохраняя инвариант «каждая известная последовательность финально правильно обработана». Ну и вся стратегия определяется рекурсивно — как добавление к предыдущей стратегии для непредельного ординала и как объединение всех предыдущих для предельного. Каждая последовательность будет включена, потому что каждая чей-то собственный суффикс.