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

[KappaGolden]

Мудрецы в черных и белых шляпах стоят в точках натурального ряда и видят всех мудрецов с большими номерами. Докажите, что у мудрецов имеется стратегия, позволяющая каждому из них назвать цвет своей шляпы так, что лишь конечно много мудрецов будут неправы. (Стратегия — это функция, отображающая известную мудрецу информацию в его ответ; такая функция должна быть одна для всех мудрецов.)

Я смог решить эту задачу для случая, когда все мудрецы знают свой номер. Я решал так: пусть две последовательности совпадающие начиная с некоторого n совпадают, тогда отнесем их к одному классу эквивалентности. По аксиоме выбора я могу сопоставить каждому классу сопоставить "представителя" этого класса. Очевидно, что каждый мудрец может определить класс следующей за ним последовательности, а значит он может сказать свой цвет, в зависимости от того, что стоит в последовательности - "представителе". Значит всего конечное количество мудрецов будет не право. Мне не понятно как обобщить на случай, если мудрецу не известен его номер.

[gabber]

Кто из мудрецов слышит ответ конкретного мудреца?

[Утундрий]

del

[Pphantom]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:
- отсутствуют собственные содержательные попытки решения задачи;
- текст стоит отформатировать нормально.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[arseniiv]

KappaGolden в сообщении #1443942 писал(а):

Мне не понятно как обобщить на случай, если мудрецу не известен его номер.

Посмотрите сначала на периодические последовательности и потом ещё на те из остальных, которые финально периодические (сначала какой-то кусок, а потом пошла периодическая). Останется самое страшное.

[gabber]

В общем случае имеем абсолютно нормальное невычислимое число в двоичной записи. Никакой закономерной Seq она не образует.
Задача не имеет решения.

[mihaild]

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

[arseniiv]

gabber
Глупости пишете, имеет, но при одном часто принимаемом условии.

[Lia]

Не имеющая отношения к делу часть здесь: «Задача про бесконечное количество мудрецов для gabber»

[KappaGolden]

arseniiv в сообщении #1443966 писал(а):

KappaGolden в сообщении #1443942 писал(а):

Мне не понятно как обобщить на случай, если мудрецу не известен его номер.

Посмотрите сначала на периодические последовательности и потом ещё на те из остальных, которые финально периодические (сначала какой-то кусок, а потом пошла периодическая). Останется самое страшное.

Не совсем ясно, как решать даже для периодической последовательности. Можете подсказать, как именно решать для этого случая?

[mihaild]

Допустим что мудрец перед собой видит последовательность $011001\ 011001\ 011001\ 011001\ 011001 \ldots$ (пробелы расставлены для удобства, их не видно). Пусть заведомо известно, что последовательность периодическая. Какой цвет надо называть мудрецу?

[arseniiv]

mihaild в сообщении #1444101 писал(а):

(пробелы расставлены для удобства, их не видно)

Кстати было бы хорошо, если бы их было видно, а то приходится смотреть в код, чтобы убедиться в периодичности.

-- Вт мар 10, 2020 22:08:35 --

KappaGolden в сообщении #1444099 писал(а):

Не совсем ясно, как решать даже для периодической последовательности. Можете подсказать, как именно решать для этого случая?

Альтернативный совет: начните с последовательности одних нулей (или одних единиц). Я так сам и начинал.

[KappaGolden]

mihaild в сообщении #1444101 писал(а):

Допустим что мудрец перед собой видит последовательность $011001\ 011001\ 011001\ 011001\ 011001 \ldots$ (пробелы расставлены для удобства, их не видно). Пусть заведомо известно, что последовательность периодическая. Какой цвет надо называть мудрецу?

Скорее всего, ему нужно ответить: 1, т.к. если он видит перед собой повторяющуюся последовательность 011001, то значит он стоит в самом её конце.

[arseniiv]

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