Класс эквивалентности, как и каноническая последовательность этого класса, не зависят от номера узника. Они все определяют один и тот же класс и все отвечают согласно одной и той же канонической последовательности (даже если некоторые из них видят отличия с настоящей последовательностью перед собой).
Пусть узники выбрали такую каноническую последовательтность в этом классе:
0101010101010101010101010101…
4ый узник, например, видет такую подпоследовательность:
____000001010101010101010101…
Тогда, несмотря на то что он уже видит, что последовательности отличаются, всё равно отвечает согласно канонической последовательности, т.е. что на нём колпак 1. И так же поступают все другие узники.
Эти две последовательности, начиная с некоторого номера (в данном случае с 9ого) совпадают. А значит, все узники, начиная с этого номера, будут отвечать правильно.
Указание возможности использования этой аксиомы было подсказкой. По-моему, лучше в условии о ней не упоминать. Если человек додумается, как решать с помощью этой аксиомы, он может спросить, можно ли её использовать (именно так было со мной). Всё-таки аксиома достаточно известна.
Разобъём все последовательности из 0 и 1 (т.е. белых и чёрных колпаков) на классы эквивалентности: две последовательности эквивалентны, если начиная с некоторого номера они совпадают. Для каждого класса эквивалентности выберем «канонического представителя» — последовательность из этого класса (здесь мы используем аксиому выбора). Все эти канонические последовательности будем хранить в бесконечной памяти каждого узника. Когда их выстроют по порядку, каждый узник будет видеть всю «настоящую» последовательность, кроме её конечного начала. По тому бесконечному куску, который он видет, он сможет определить, в каком классе эквивалентности находится настоящая последовательность (например, он может мысленно дополнить видимую им подпоследовательность нужным количеством нулей и сравнить на эквивалентность с каждой из канонических последовательностей). Тогда он должен ответить, что на нём тот вид колпака (т.е. 0 или 1), который стоит на его месте в соответствующей канонической последовательности. Т.к. каноническая последовательность и настоящая начиная с некоторого номера совпадают, то ошибок будет лишь конечное число.
Ошибки наверно нет, просто с точки зрения математики нет никакого абсурда. Действительно получается, что если каждый узник видел все выпадания монетки до него, то начиная с некоторого номера все узники будут угадывать выпадание своей монетки. Попробуйте в этом какое-то логическое противоречие найти. Теория вероятности здесь ни при чём.
Извиняюсь, пост был некоторое время скрыт (из-за нарушения правил по поводу кросс-постинга).
Вопрос: пора уже публиковать решение? Или есть ещё люди, которые хотят подумать (но не смогут не подглядывать)?
Применять теорию вероятности можно, только если введено вероятностное пространство. Тут же никакого вероятностного пространства нет. Требуется, чтобы ДЛЯ ЛЮБОЙ последовательности колпаков количество ошибок было конечно.
Ну хорошо, задачи на спротивное программирование действительно часто связыны с теор. математикой.
Я просто хотел сказать, что эта задача чисто теоретическая, никакого кода десь быть не может.
К вашей задаче нашёл ответ без программирования: 2100010006 (хотя не знаю, единственный ли он)
Разница с монеткой в том, что здесь каждый узник уже видит перед собой бесконечную последовательность, а для монетки известно наоборот только конечное начало.
Хотя мне кажется, с двумя цветами сложнее решать — хочется инвертирование использовать.
Приведу пример.
Пусть настоящая последовательность такая:
0000000001010101010101010101…
Пусть узники выбрали такую каноническую последовательтность в этом классе:
0101010101010101010101010101…
4ый узник, например, видет такую подпоследовательность:
____000001010101010101010101…
Тогда, несмотря на то что он уже видит, что последовательности отличаются, всё равно отвечает согласно канонической последовательности, т.е. что на нём колпак 1. И так же поступают все другие узники.
Эти две последовательности, начиная с некоторого номера (в данном случае с 9ого) совпадают. А значит, все узники, начиная с этого номера, будут отвечать правильно.
Разобъём все последовательности из 0 и 1 (т.е. белых и чёрных колпаков) на классы эквивалентности: две последовательности эквивалентны, если начиная с некоторого номера они совпадают. Для каждого класса эквивалентности выберем «канонического представителя» — последовательность из этого класса (здесь мы используем аксиому выбора). Все эти канонические последовательности будем хранить в бесконечной памяти каждого узника. Когда их выстроют по порядку, каждый узник будет видеть всю «настоящую» последовательность, кроме её конечного начала. По тому бесконечному куску, который он видет, он сможет определить, в каком классе эквивалентности находится настоящая последовательность (например, он может мысленно дополнить видимую им подпоследовательность нужным количеством нулей и сравнить на эквивалентность с каждой из канонических последовательностей). Тогда он должен ответить, что на нём тот вид колпака (т.е. 0 или 1), который стоит на его месте в соответствующей канонической последовательности. Т.к. каноническая последовательность и настоящая начиная с некоторого номера совпадают, то ошибок будет лишь конечное число.
Вопрос: пора уже публиковать решение? Или есть ещё люди, которые хотят подумать (но не смогут не подглядывать)?
Но поверьте, решение у неё есть :)
Я просто хотел сказать, что эта задача чисто теоретическая, никакого кода десь быть не может.
К вашей задаче нашёл ответ без программирования: 2100010006 (хотя не знаю, единственный ли он)
Кстати, много похожих задач есть на projecteuler.net