Задача о гномах

[Tookser]

Бесконечному числу гномов дают договориться друг с другом, потом завязывают им глаза и надевают на них шапки черного и белого цвета.
Бесконечное число гномов становятся в ряд, ограниченный с одной стороны. Все гномы смотрят в одну и ту же сторону. Первый гном видит всех, кроме себя, второй всех, кроме себя и первого и т.д.
После этого все они должны одновременно сказать цвет своей шапки.
Вопрос: могут ли гномы договориться так, что не угадает лишь конечное число гномов?

Задачу нашел на сайте на букву Х, но не уверен, что она там правильно рассматривается (еще не читал ту статью).

[gris]

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

То есть скорее всего им запрещено обмениваться информацией. Тогда это что-то теоретико-множественное, причем наверняка околопарадоксальное. Последовательность гномов изображает некоторое действительное число, и этих последовательностей возможно несчётное количество. Каждый гном видит всю последовательность, за исключением конечного числа первых членов. То есть он знает о последовательности почти всё. Ладно, не буду ковыряться в чужой песочнице.

[Nemiroff]

gris в сообщении #757084 писал(а):

Тогда это что-то теоретико-множественное, причем наверняка околопарадоксальное.

Причем наверняка неконструктивное. И тогда непонятно, считать это положительным ответом или нет.

[gris]

А я вначале так и написал "наверняка неконструктивное", но потом убоялся употребления малознакомых словей
Хотя по идее задача наверняка обсуждалась и на форуме. А идея достаточно очевидна: разбиваем все последовательности на классы эквивалентности по равенству почти всех членов за исключением конечного их числа. В каждом классе выбираем эталонную последовательность. (Вот тут и неконструктивизьм, понимаете ли). Гномы всё это дело перетирают и запоминают эталонные последовательности. Сдаётся, что их тоже несчётное количество. Ну а потом, смотря вперёд, диагностируют без труда (опять неконструктивно) класс эквивалентности и озвучивают соответствующую позицию эталонной последовательности. Правда, тут надо поаккуратнее разобраться с возможностью этих действий при незнании гномами своих позиций.

[Tookser]

gris
Идея понятна, только не совсем ясно, что значит "равенство почти всех членов"?
Т.е. являются ли примерами эквивалентных последовательностей
$a_0, a_1, a_2...$
и
$a_1, a_2, a_3...$
?
Т.е. "отличается конечным числом гномов" значит "нужно вставить и убрать в последовательности конечное число гномов"?

gris в сообщении #757105 писал(а):

Правда, тут надо поаккуратнее разобраться с возможностью этих действий при незнании гномами своих позиций.

Важное дополнение: в условии задачи было сказано, что позиция гнома в очереди известна ему.

[nikvic]

Эта позиция известна заранее?

[Nemiroff]

gris в сообщении #757105 писал(а):

Гномы всё это дело перетирают и запоминают эталонные последовательности. Сдаётся, что их тоже несчётное количество.

Ну вот тут и выходит, что неконструктивизм портит "запоминание эталонных последовательностей". То бишь, не смогут они выбрать одинаково представителя.

[gris]

Tookser, пардон, вчера начал считать гномов и уснул.
При способе (поостерегусь называть его алгоритмом) с разбиением на классы эквивалентности знание своей позиции, кажется, необходимо. Ведь без этого знания гномы не различат последовательности $01(01)$ и $10(10)$, а они входят в разные классы. Я предложил $\{a_n\}\sim \{b_n\} \Leftrightarrow \exists N: \forall n>N \; a_n=b_n$, то есть совпадение последовательностей с некоторого члена без сдвига.
Тогда ставится вопрос: может ли гном за время (есть ли смысл тут вообще говорить о времени?) до момента озвучивания ответа сравнить бесконечное (несчётное) количество последовательностей? Если да, то всё в порядке.

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

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

Чуть оффтопично: интересно само отношение эквивалентности. Ведь мы можем (после предварительной факторизации множества последовательностей по единичным хвостам) установить его биекцию с множеством действительных чисел на единичном отрезке. То есть считать два числа эквивалентными, если их "хорошие" двоичные записи отличаются в конечном числе позиций. Интересно, что это за разбиение?

[Tookser]

gris, да, такое разбиение подходит. Сам запутался, не обратив внимание на то, что позиция гнома в очереди известна ему.

С числами - получается разбиение на всюду плотные множества. Множества вроде делятся на два типа: множества периодических дробей (в двоичной) и остальные.

[gris]

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

[Tookser]

gris в сообщении #757352 писал(а):

а для непериодических определить свою истинную позицию.

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

Каждый гном тогда может спокойно считать себя первым, и действовать далее как в исходной задаче. В зависимости от выбора эталонных последовательностей и реальной последовательности гномов это может дать, наверное, почти любой результат.
К примеру,
$10100100010000...$ - последовательность гномов.
Некоторые эталонные последовательности, очевидно, входящие каждая в свой класс и выбранные гномами:
$\textit{0}\; 0100100010000100000...$ $\textit{0}\; 00100010000100000...$ $\textit{0}\; 00010000100000...$ $\textit{0}\; 0000100000...$ и т.д.
Таким образом, счетное число гномов, каждый из которых считает себя первым, ошибаются. Можно аналогично сделать так, чтобы все гномы ошиблись (если они будут вести себя именно так). Таким образом, в этой задаче слишком многое зависит от психологии гномов.

nikvic в сообщении #757115 писал(а):

Эта позиция известна заранее?

Не все ли равно? Можно каждому гному запомнить $\aleph_0$ планов действия (если бы он был 1-м, 2-м и т.д.).

[gris]

Я просто подумал о дополнительной факторизации по сдвигу на конечное число позиций. Но это действительно может привести с счётному числу ошибок.