Здравствуйте, хабралюди. Предложу я вам задачку, которую мне вчера показала одна знакомая.
На каждого гнома из бесконечной очереди надет либо синий, либо красный колпак. Каждый гномик смотрит в спину впереди стоящего так, что первый видит колпаки всех, кроме своего, второй видит всех, кроме себя и первого, и так далее. Каждый гном знает лишь то, что видит, свое положение в очереди и то, о чем они все вместе договорились перед тем, как получить колпаки.
По команде все гномы должны одновременно назвать цвет. Тех, кто не угадал, какой на них колпак,расстр в общем, они не угадывают.
Вопрос: как им договориться, чтобы не угадало лишь конечное число гномов?
Тех, кому интересно и кто на данный момент не хочет предпринимать попытки решения, прошу пожаловать под кат. Статья будет представлять собой рассуждения о задаче и ее «решении». (Любителям математики я советую попробовать решить).
На первый взгляд кажется, что решения нет и не может быть. В самом деле, никакой информацией гномики обмениваться не могут никак. Более того, поскольку их бесконечно, все гномики абсолютно равноценны. Каждый из них видит абсолютно одинаковую по сути картину — бесконечную шеренгу из своих друзей. Никаких выводов, расчетов произвести ни у кого не получится, поскольку цвет колпака на данном конкретном гномике никак не зависит от того, что он видит.
Первое о чем я подумал, это подсчет всяких свяких свойств последовательности, видимой гномиком. Представление синих колпаков числом 1, а красных числом -1, суммирование ряда в частных смыслах в попытках найти свойство, которое не сможет в последовательности частичных сумм изменяться слишком много раз. Но это оказалось абсолютно бесполезно.
Ничто не помогало, всё упиралось в факт, что все гномики равнозначно первые в своей очереди, и в какой-то момент я смело сказал: не может быть. Я был абсолютно уверен.
Нашел я его в сети. Автор говорит, что будет пользоваться аксиомой выбора.
Рассмотрим все возможные последовательности колпаков. Назовем две последовательности эквивалентными, если они различаются лишь в конечном числе позиций. Это отношение, очевидно, транзитивно, рефлексивно и симметрично, поэтому можно с его помощью разбить все возможные последовательности на классы. По другому: две последовательности будут принадлежать одному классу, если они различаются лишь конечным числом колпаков. Теперь, из каждого класса выберем представителя (это можно сделать в силу аксиомы выбора) — какую-то конкретную последовательность. Этих представителей гномики должны знать.
Дело за малым: стоя в очереди, любой гномик может определить, в каком классе лежит текущая (та, которая имеет место быть) последовательность. В самом деле, каждый гномик НЕ видит лишь конечное число колпаков, а следовательно они никак не влияют на принадлежность последовательности какому-то классу. Другими словами, гномик может предположить, что все колпаки за ним (и его) — красные, и вспомнить класс, к которому относится такая последовательность. Она будет эквивалентна текущей. Теперь гномик вспомнит представителя этого класса и назовет цвет колпака, который был бы у него на голове, будь текущая последовательность совпадающей с представителем.
Вуаля. Выбранный представитель (всеми гномиками одинаково) и текущая последовательность принадлежат одному классу, а следовательно различаются лишь в конечном числе позиций.
Да, такой разворот событий меня расстроил, и пришлось искать несовершенство в рассуждениях, чтобы защитить мое утверждение о том, что решения нет.
Конечно же, первое, что обращает на себя внимание — аксиома выбора. Автор ее подчеркнул, а все, кто про нее знают, знают так же и причину, по которой ее многие критикуют — неконструктивность.
Вкратце: аксиома выбора говорит о том, что на любом наборе непустых множеств можно определить функцию, которая по каждому множеству будет возвращать какой-то элемент, ему принадлежащий. Проблема в том, что такую функцию может быть невозможно построить/описать. Например, рассматривая все подмножества прямой (так называемый гиперконтинуум), предложить такую функцию нельзя. Хотя аксиома говорит о том, что она существует.
Может быть, дело в этом? Может быть, гномики не могут в принципе одинаково выбирать представителя каждого класса? Ведь классов много, столько же, сколько точек на прямой. То есть функция выбора как бы существует, а договориться о ней нельзя.
Но нет, это предположение оказалось бесполезным. Дело в том, что в решении аксиома выбора вообще не нужна. В каждом классе есть наименьшая в лексикографическом порядке последовательность, — например, её можно брать представителем.
Потом я стал думать о том, как гномики могут понять, к какому классу относится текущая последовательность. Не понадобится ли им для этого перебирать все классы и сравнивать, с чем может возникнуть проблема, ибо континуума времени не хватит на перебор континуума классов, в предположении, что мысль занимает ненулевое время…
Но не буду вас слишком запутывать, и так уже нагородил. Дело в том, что я вас только что обманул. Кто попался? Нельзя выбрать наименьший в лексикографическом порядке элемент класса.
Возьмем, например, класс, содержащий последовательность из всех синих колпаков 1, 1, 1, 1, 1, 1… В нем так же будут последовательности:
-1, 1, 1, 1, 1, 1,…
-1, -1, 1, 1, 1, 1,…
-1, -1, -1, 1, 1, 1,… какую из них ни взять, найдется лексикографически меньшая последовательность. Более того, то же можно сказать о любом классе — какая последовательность ни была бы наименьшей, можно найти в ней первую единицу и заменить на -1, получив еще меньшую. Получается, что такой минимум существует всего в одном из классов — содержащем -1, -1,… последовательность всех красных колпаков.
Вернемся.
Встает вопрос: можно ли всё-таки обойтись без нее в данном решении? Сейчас поанализируем.
Что из себя представляют наши классы? Давайте все последовательности представим числами из отрезка [0; 1]. Будем считать, что колпаки это цифры 0 и 1, а последовательность является числом 0,abcd… в двоичной системе счисления. Мы потеряем часть последовательностей, потому что, например, такие две:
0,011111… и 0,100000… задают одну и ту же дробь 1/2. Но это не слишком страшно, таких коллизий очень мало (всего лишь счётно). Зато каждому числу будет соответствовать какая-то последовательность, так что это почти взаимооднозначное соответствие между всеми последовательностями из 0/1 и всеми числами отрезка [0; 1].
Как выглядят наши классы на отрезке? Ужасно, каждый класс является счетным плотным множеством. Это значит, что для любого класса А и чисел х из [0; 1], эпсилон>0 в классе А будет число, расстояние от которого до х меньше эпсилон.
В этом месте проблема с коллизиями в биекции, которую я чуть выше проигнорировал, заминается, поскольку счетное множество туда-сюда прибавить-отнять на измеримость по Лебегу не влияет.
Ну что ж, кто-то знает, а кто-то может прочитать в той же самой статье на Википедии, что построение ограниченных множеств без меры Лебега всегда опирается на аксиому выбора. Следовательно, решение автора существенно опирается на данную аксиому, и без нее не верно.
Получается, что наши бедные гномики знают, что функция выбора для представителей классов существует (если они согласны с теорей ZFC, конечно же), но выбирать этих представителей они все одинаково не смогут, поскольку описать эту функцию невозможно.
Доказал ли я неверность авторского решения? Думаю, что да. Формулировка задачи — как гномикам договориться. Необходимость аксиомы выбора однозначно говорит, что ответа на «как» в решении нет и быть не может.
Есть ли решение у задачи? Доказать его отсутствие — слишком сложная задача, да и вряд ли можно придумать что-то лучше, чем равнозначность гномиков и отсутствие у них возможности обмениваться информацией. Для меня это достаточно убедительно. Если кто-то придумает что-то строгое — прошу поделиться.
Зачем это всё? Как я уже сказал, читателям этого хаба, на мой взгляд, может быть интересно. А мне, в свою очередь, крайне интересно обсудить задачу с сообществом. А еще, можно рассматривать статью как практический (насколько он может быть практическим) и доступный миниобзор последней буквы в аббревиатуре ZFC и связанных с нею проблем.
Приятного дня!
На каждого гнома из бесконечной очереди надет либо синий, либо красный колпак. Каждый гномик смотрит в спину впереди стоящего так, что первый видит колпаки всех, кроме своего, второй видит всех, кроме себя и первого, и так далее. Каждый гном знает лишь то, что видит, свое положение в очереди и то, о чем они все вместе договорились перед тем, как получить колпаки.
По команде все гномы должны одновременно назвать цвет. Тех, кто не угадал, какой на них колпак,
Вопрос: как им договориться, чтобы не угадало лишь конечное число гномов?
Тех, кому интересно и кто на данный момент не хочет предпринимать попытки решения, прошу пожаловать под кат. Статья будет представлять собой рассуждения о задаче и ее «решении». (Любителям математики я советую попробовать решить).
Часть 1/4. Размышления.
На первый взгляд кажется, что решения нет и не может быть. В самом деле, никакой информацией гномики обмениваться не могут никак. Более того, поскольку их бесконечно, все гномики абсолютно равноценны. Каждый из них видит абсолютно одинаковую по сути картину — бесконечную шеренгу из своих друзей. Никаких выводов, расчетов произвести ни у кого не получится, поскольку цвет колпака на данном конкретном гномике никак не зависит от того, что он видит.
Первое о чем я подумал, это подсчет всяких свяких свойств последовательности, видимой гномиком. Представление синих колпаков числом 1, а красных числом -1, суммирование ряда в частных смыслах в попытках найти свойство, которое не сможет в последовательности частичных сумм изменяться слишком много раз. Но это оказалось абсолютно бесполезно.
Ничто не помогало, всё упиралось в факт, что все гномики равнозначно первые в своей очереди, и в какой-то момент я смело сказал: не может быть. Я был абсолютно уверен.
Часть 2/4. Авторское решение.
Нашел я его в сети. Автор говорит, что будет пользоваться аксиомой выбора.
Рассмотрим все возможные последовательности колпаков. Назовем две последовательности эквивалентными, если они различаются лишь в конечном числе позиций. Это отношение, очевидно, транзитивно, рефлексивно и симметрично, поэтому можно с его помощью разбить все возможные последовательности на классы. По другому: две последовательности будут принадлежать одному классу, если они различаются лишь конечным числом колпаков. Теперь, из каждого класса выберем представителя (это можно сделать в силу аксиомы выбора) — какую-то конкретную последовательность. Этих представителей гномики должны знать.
Дело за малым: стоя в очереди, любой гномик может определить, в каком классе лежит текущая (та, которая имеет место быть) последовательность. В самом деле, каждый гномик НЕ видит лишь конечное число колпаков, а следовательно они никак не влияют на принадлежность последовательности какому-то классу. Другими словами, гномик может предположить, что все колпаки за ним (и его) — красные, и вспомнить класс, к которому относится такая последовательность. Она будет эквивалентна текущей. Теперь гномик вспомнит представителя этого класса и назовет цвет колпака, который был бы у него на голове, будь текущая последовательность совпадающей с представителем.
Вуаля. Выбранный представитель (всеми гномиками одинаково) и текущая последовательность принадлежат одному классу, а следовательно различаются лишь в конечном числе позиций.
Да, такой разворот событий меня расстроил, и пришлось искать несовершенство в рассуждениях, чтобы защитить мое утверждение о том, что решения нет.
Часть 3/4. Что не так.
Конечно же, первое, что обращает на себя внимание — аксиома выбора. Автор ее подчеркнул, а все, кто про нее знают, знают так же и причину, по которой ее многие критикуют — неконструктивность.
Вкратце: аксиома выбора говорит о том, что на любом наборе непустых множеств можно определить функцию, которая по каждому множеству будет возвращать какой-то элемент, ему принадлежащий. Проблема в том, что такую функцию может быть невозможно построить/описать. Например, рассматривая все подмножества прямой (так называемый гиперконтинуум), предложить такую функцию нельзя. Хотя аксиома говорит о том, что она существует.
Может быть, дело в этом? Может быть, гномики не могут в принципе одинаково выбирать представителя каждого класса? Ведь классов много, столько же, сколько точек на прямой. То есть функция выбора как бы существует, а договориться о ней нельзя.
Но нет, это предположение оказалось бесполезным. Дело в том, что в решении аксиома выбора вообще не нужна. В каждом классе есть наименьшая в лексикографическом порядке последовательность, — например, её можно брать представителем.
Потом я стал думать о том, как гномики могут понять, к какому классу относится текущая последовательность. Не понадобится ли им для этого перебирать все классы и сравнивать, с чем может возникнуть проблема, ибо континуума времени не хватит на перебор континуума классов, в предположении, что мысль занимает ненулевое время…
Но не буду вас слишком запутывать, и так уже нагородил. Дело в том, что я вас только что обманул. Кто попался? Нельзя выбрать наименьший в лексикографическом порядке элемент класса.
Возьмем, например, класс, содержащий последовательность из всех синих колпаков 1, 1, 1, 1, 1, 1… В нем так же будут последовательности:
-1, 1, 1, 1, 1, 1,…
-1, -1, 1, 1, 1, 1,…
-1, -1, -1, 1, 1, 1,… какую из них ни взять, найдется лексикографически меньшая последовательность. Более того, то же можно сказать о любом классе — какая последовательность ни была бы наименьшей, можно найти в ней первую единицу и заменить на -1, получив еще меньшую. Получается, что такой минимум существует всего в одном из классов — содержащем -1, -1,… последовательность всех красных колпаков.
Вернемся.
Часть 4. Аксиома выбора.
Встает вопрос: можно ли всё-таки обойтись без нее в данном решении? Сейчас поанализируем.
Что из себя представляют наши классы? Давайте все последовательности представим числами из отрезка [0; 1]. Будем считать, что колпаки это цифры 0 и 1, а последовательность является числом 0,abcd… в двоичной системе счисления. Мы потеряем часть последовательностей, потому что, например, такие две:
0,011111… и 0,100000… задают одну и ту же дробь 1/2. Но это не слишком страшно, таких коллизий очень мало (всего лишь счётно). Зато каждому числу будет соответствовать какая-то последовательность, так что это почти взаимооднозначное соответствие между всеми последовательностями из 0/1 и всеми числами отрезка [0; 1].
Как выглядят наши классы на отрезке? Ужасно, каждый класс является счетным плотным множеством. Это значит, что для любого класса А и чисел х из [0; 1], эпсилон>0 в классе А будет число, расстояние от которого до х меньше эпсилон.
Доказать это просто
Более того, если мы выберем представителей каждого класса, то они образуют типичное множество, не измеримое по Лебегу. Доказательство этого факта предлагаю прочесть в коротенькой статье на Википедии. Множество Витали строится очень похожим образом, а при доказательстве неизмеримости слова «на все рациональные числа» (про сдвиги) следует заменить «на все дроби с знаменателями вида 2^n» (в множестве Витали числа одного класса различаются на рациональное число, а у меня на конечную сумму отрицательных степеней двойки, то есть на дробь указанного вида).Достаточно взять любое число z из А, взять его хвост, начиная с цифры, соответствующей степени двойки n такой, что 2^n < эпсилон / 10. И этим хвостом заменить хвост числа х. Получившееся число и число z принадлежат одному классу и различаются не более, чем на эпсилон / 5.
В этом месте проблема с коллизиями в биекции, которую я чуть выше проигнорировал, заминается, поскольку счетное множество туда-сюда прибавить-отнять на измеримость по Лебегу не влияет.
Ну что ж, кто-то знает, а кто-то может прочитать в той же самой статье на Википедии, что построение ограниченных множеств без меры Лебега всегда опирается на аксиому выбора. Следовательно, решение автора существенно опирается на данную аксиому, и без нее не верно.
Получается, что наши бедные гномики знают, что функция выбора для представителей классов существует (если они согласны с теорей ZFC, конечно же), но выбирать этих представителей они все одинаково не смогут, поскольку описать эту функцию невозможно.
Послесловие.
Доказал ли я неверность авторского решения? Думаю, что да. Формулировка задачи — как гномикам договориться. Необходимость аксиомы выбора однозначно говорит, что ответа на «как» в решении нет и быть не может.
Есть ли решение у задачи? Доказать его отсутствие — слишком сложная задача, да и вряд ли можно придумать что-то лучше, чем равнозначность гномиков и отсутствие у них возможности обмениваться информацией. Для меня это достаточно убедительно. Если кто-то придумает что-то строгое — прошу поделиться.
Зачем это всё? Как я уже сказал, читателям этого хаба, на мой взгляд, может быть интересно. А мне, в свою очередь, крайне интересно обсудить задачу с сообществом. А еще, можно рассматривать статью как практический (насколько он может быть практическим) и доступный миниобзор последней буквы в аббревиатуре ZFC и связанных с нею проблем.
Приятного дня!