Задача про гномов и разноцветные шапки

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

    Тех, кому интересно и кто на данный момент не хочет предпринимать попытки решения, прошу пожаловать под кат. Статья будет представлять собой рассуждения о задаче и ее «решении». (Любителям математики я советую попробовать решить).

    Часть 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 в классе А будет число, расстояние от которого до х меньше эпсилон.
    Доказать это просто
    Достаточно взять любое число z из А, взять его хвост, начиная с цифры, соответствующей степени двойки n такой, что 2^n < эпсилон / 10. И этим хвостом заменить хвост числа х. Получившееся число и число z принадлежат одному классу и различаются не более, чем на эпсилон / 5.
    Более того, если мы выберем представителей каждого класса, то они образуют типичное множество, не измеримое по Лебегу. Доказательство этого факта предлагаю прочесть в коротенькой статье на Википедии. Множество Витали строится очень похожим образом, а при доказательстве неизмеримости слова «на все рациональные числа» (про сдвиги) следует заменить «на все дроби с знаменателями вида 2^n» (в множестве Витали числа одного класса различаются на рациональное число, а у меня на конечную сумму отрицательных степеней двойки, то есть на дробь указанного вида).
    В этом месте проблема с коллизиями в биекции, которую я чуть выше проигнорировал, заминается, поскольку счетное множество туда-сюда прибавить-отнять на измеримость по Лебегу не влияет.
    Ну что ж, кто-то знает, а кто-то может прочитать в той же самой статье на Википедии, что построение ограниченных множеств без меры Лебега всегда опирается на аксиому выбора. Следовательно, решение автора существенно опирается на данную аксиому, и без нее не верно.
    Получается, что наши бедные гномики знают, что функция выбора для представителей классов существует (если они согласны с теорей ZFC, конечно же), но выбирать этих представителей они все одинаково не смогут, поскольку описать эту функцию невозможно.

    Послесловие.


    Доказал ли я неверность авторского решения? Думаю, что да. Формулировка задачи — как гномикам договориться. Необходимость аксиомы выбора однозначно говорит, что ответа на «как» в решении нет и быть не может.
    Есть ли решение у задачи? Доказать его отсутствие — слишком сложная задача, да и вряд ли можно придумать что-то лучше, чем равнозначность гномиков и отсутствие у них возможности обмениваться информацией. Для меня это достаточно убедительно. Если кто-то придумает что-то строгое — прошу поделиться.
    Зачем это всё? Как я уже сказал, читателям этого хаба, на мой взгляд, может быть интересно. А мне, в свою очередь, крайне интересно обсудить задачу с сообществом. А еще, можно рассматривать статью как практический (насколько он может быть практическим) и доступный миниобзор последней буквы в аббревиатуре ZFC и связанных с нею проблем.
    Приятного дня!
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 142

      +2
      У меня в голове почему-то такие рассуждения.
      Будем рассматривать очередь не с конца, а с начала, то есть каждый гном видит конечное число колпаков. Предположим, что решение задачи существует, то есть для i+1-того гномика существует функция fi (i — индекс) от i аргументов, возвращающая Синий или Красный. Более того, эти функции «независимы» = гномики не умеют общаться = функция i аргументов.
      Я утверждаю, что для любого набора таких функций найдется такая раскраска гномиков, что все гномы умрут.
      Действительно, вставим гномам в уши затычки, чтобы они не слышали друг друга, снимем шапки и начнем опрашивать гномов по одному спереди. При этом каждому гному мы будем надевать шапку противоположного цвета.
      Теперь вынем затычки и спросим гномов одновременно. Каждый гном в обоих случаях видит одно и то же, значит и скажет то же самое, а, значит, умрет к радости эльфов.
      В итоге мы получим для данной последовательности гномов последовательность шапок смертников.

      Кажется, этого для отсутствия решения достаточно.

        0
        Честно говоря, я не понял про рассматривание очереди с другой стороны. Она бесконечная, у нее нет начала.
          0
          Там в авторском решении (2 пункт) подразумевалось, что у очереди есть конец.
          Назовем две последовательности эквивалентными, если они различаются лишь в конечном числе позиций. (...) Дело за малым: стоя в очереди, любой гномик может определить, в каком классе лежит текущая (та, которая имеет место быть) последовательность. В самом деле, каждый гномик НЕ видит лишь конечное число колпаков, а следовательно они никак не влияют на принадлежность последовательности какому-то классу.


          В общем-то, для моего доказательства можно бесконечную с обеих сторон последовательность сделать конечной с одной стороны. Назовем какого-то гнома первым, а на всех перед ним забьем. У нас и так останется бесконечное количество ошибок, даже если все выброшенные угадают.
            0
            Только один из концов есть. Каждый гномик видит бесконечно много других гномиков, а не видит — конечное число других.
          0
          Я подумал над вашей идеей. Продлить ее на бесконечность, к сожалению, не выходит.
            0
            Да, вы правы, я плохо читаю условие) Всё стало куда сложнее. Подумаю на досуге.
          0
          У вас искажены условия задачи.

          Во-первых, очередь не бесконечная, а с произвольным конечным количеством человек (соотношение цветов тоже произвольное).

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

          Такая задача имеет очень элегантное решение в математико-программистком ключе, причём, и это в-третьих, все участники, кроме первого, должны угадать цвет безошибочно.
            +13
            Тогда у вас тоже искажены условия задачи. Потому что там вообще не про гномов, а про спички. И нужно переложить одну спичку так, чтобы получилось равенство.
              0
              Это уже другая, более тривиальная задача.
              В статье поинтересней и посложнее будет.
                +3
                Ничего интересного и сложного я в ней не вижу. Видимо, потому что я не математик. :/

                Если колпак на вас выбран случайно, то его цвет по определению слова «случайно» не имеет ни с чем взаимосвязи. Определить цвет колпака, глядя на окружающие предметы, в том числе на другие колпаки, невозможно просто по условию задачи.

                Всё. Говорить тут больше не о чем.

                Четвертый раздел поста напомнил Корчевателя. Нет, я, конечно, верю, что текст взят из головы автора, а не с vesna.yandex.ru, но благодаря отсутствию задачи в данной задаче на этот пост можно ловить «математиков» в кавычках (по аналогии с «фотографами»).

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

                    Вот вам ниже объяснили в ваших терминах. С тем же успехом можно бы делить этих ваших бесконечных гномиков по сексуальной ориентации. В отличие от цвета шапки, свою-то ориентацию вы знаете!
                    0
                    Ну, вообще-то, для конечного количества гномов есть решение, которое с гарантией спасает всех, кроме одного.
                    Определить цвет, только разглядывая других, конечно, нельзя. Но ведь есть и ещё один канал информации. Каждый гном слышит, всё, что сказано теми, кто видит его. И этим уже можно воспользоваться.
                    Если хотите, кину в личку решение для конечного количества. Здесь, кажется, избегают его публикации. 8)
                      +1
                      Классическое решение предполагает, что гномы называют цвета по очереди. А здесь требуется, чтобы они назвали свои цвета одновременно. Так что обработать информацию от стоящих сзади гном просто не успеет.
                  0
                  Всё-таки скорее очередь бесконечная, но всё же гномики называют цвета по очереди. И тогда действительно имеют смысл все эти размышления о последовательностях.
                  +2
                  думал щас будет известная и красивая задачка:
                  Сидели 3 мудреца, и спорили кто из них мудрее всех. Царь дал им такую задачку. У меня в сумке лежат 5 шляп, 3 белых и 2 черных. Сейчас вы закроете глаза, и я надену какие-то 3 из них. Он усадил их в 3 разных угла, так что каждый мог видеть какие надеты шляпы на 2-х других мудрецах.Тот из вас кто первым скажет, какая у него шляпа – тот и есть наимудрейший.
                    +2
                    Интересная задача!

                    Попробую рассуждать вслух.
                    Если перед вами две черные шапки — остаются только белые, сразу называем белый.

                    Если в первый момент никто другой не поступил так, значит, никто из них не видит перед собой две черные шапки.

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

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

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

                    Правильно? :)
                      +1
                      Тоже мыслил так.

                      Задача заметно усложнится, а то и станет совсем не решаемой, если изменить в условиях «Сидели 2 мудреца и 1 тролль (который не мыслил как описано выше, и даже видя перед собой 2 черные шляпы говорил-бы, что на нем — черная), и спорили кто из них мудрее всех».
                        +2
                        Ну а если всех заменить на троллей — получится мафия.
                        +1
                        да, правильно)
                          0
                          Это задачи не просто на логику, а на рефлексию.
                          Подробнее о рефлексии — см. работы Владимира Лефевра по теории игр.

                          Суть в том, что у каждого мудреца есть не только объектная модель (видимые и невидимая шапки), но и субъектная (представление о том, как думает он сам и как думают его коллеги).
                          А также у него есть модель царя (который может быть добрым или злым, а то и подлым, — наденет три чёрных шапки из заявленных двух, и будет ловить лулзы).

                          Пример короткого решения.
                          с закрытыми глазами
                          «Царь-батюшка справедливый. Следовательно, он всех поставит в равные условия. Следовательно, на всех белые шапки».
                          приоткрывет глаз, видит одну белую и одну чёрную шапку Чорт!!!

                          У царя тоже, кстати, есть модели мудрецов…
                            0
                            Кстати, задачки на хабре были и раньше. Например, не менее известная задачка про зеков и лампочку. habrahabr.ru/post/69558/
                              0
                              Хм, забавно, я слышал про ту же самую задачу, но там еще была уборщица, которая в случайные дни могла заходить и выключать свет, если он горел.
                                0
                                А это условие с уборщицей ничего не меняет, просто делает дольше и без того неопределенно долгий срок решения.
                        0
                        До множества Витали удаётся додуматься быстро, но я пока не смог понять, а корректно ли это решение вообще. Вроде бы, ошибок не видно.
                        Без аксиомы выбора — можно попробовать что-нибудь сделать с помощью аксиомы детерминированности (там все множества измеримы, так что трюк с множеством Витали не пройдёт), но пользоваться ей очень уж сложно.
                          0
                          За исключением неконструктивности авторское решение 100% корректно, поскольку жутко старое и проверенное кучу раз. Кстати, я задачу чуток упростил, дав гномам знание о месте, занимаемом в очереди. В оригинале этого, естественно, нет. Но тогда никто вообще ничего бы не понял.
                          UPD. Я думаю, не стоит пользоваться аксиомой детерминированности вообще, она какая-то совсем уж непризнанная =)
                            0
                            Тем не менее, AD — более-менее известная альтернатива AC, позволяющая построить хоть какую-нибудь математику.
                            Но может быть, есть и другие альтернативы, а я просто плохо искал.
                          • UFO just landed and posted this here
                              0
                              А какая разница? Здесь вообще множество не на отрезке, а в пространстве последовательностей (фактически, в канторовом множестве). Главное, что оно существует (для основной задачи, в ZFC) и неизмеримо (для игр без AC).
                                0
                                Я так и написал в посте, что похоже на Витали.
                              0
                              Делить на классы можно. Одна проблема — принадлежность к классу не несет информации о цвете шапки на тех участках, на которых классы друг от друга отличаются. А это как раз те участки на которых содержится информация о цвете собственной шапки. Тоесть каждый раз, выбирая цвет шапки и зная класс, гномик все равно имеет вероятность угадать в 50% и так бесконечное число раз.
                                0
                                «на которых классы друг от друга отличаются» следует читать «на которых последовательности входящие в класс друг от друга отличаются»
                                  0
                                  Но поскольку все гномики выберут один и тот же класс, ошибётся всё равно лишь конечное число. На самом деле, говорить о «вероятности ошибиться» здесь нельзя: для понятия «вероятности» необходима измеримость в вероятностном пространстве множества, в котором событие реализуется.
                                    0
                                    Еще раз — вероятность ошибиться НЕ зависит от выбранного класса.
                                      0
                                      При этом первый гномик, глядя на последовательность, может совершенно точно перечислить всех гномиков, которые ответят неправильно (и их окажется конечное число). Не знает он только свою судьбу.
                                      Действительно, для конкретного гномика вероятность ошибиться равна 1/2. Матожидание числа казнённых гномиков (если о нём вообще можно говорить) больше любого наперёд заданного числа. Но для каждой конкретной последовательности это число конечно.
                                        0
                                        Задача ставилась найти способ совершить конечное число ошибок для любой(!) последовательности.
                                        А то, если так рассуждать — для каждой конкретной последовательности число ошибок конечно, и ограничено длиной этой последовательности, и для этого гномикам совершенно не нужно о чем либо договариваться.
                                        Но в любом случае от их договоренностей ничего не меняется.
                                          0
                                          Это решение для любой (именно бесконечной) последовательности. И договориться им нужно о том, чтобы из каждого класса эквивалентности выбрать именно общую для всех последовательность. Иначе есть риск, что каждый из гномиков выберет последовательность, которая даёт неверный результат именно на нём.
                                            0
                                            Каким образом выбранная последовательность на что-то влияет?
                                              0
                                              Она гарантирует, что в ней только конечное число ошибок (по построению). Можно выбрать любую из класса эквивалентности — главное, чтобы она была одинакова для всех.
                                                0
                                                Для последнего гномика (с номером бесконечность) это «конечное число ошибок» равно бесконечности.
                                                  0
                                                  Нет такого гномика. И такого номера нет. Перед каждым гномиком стоит бесконечно много других гномиков. И, начиная с какого-то места, они образуют именно ту последовательность, которая содержится в множестве Витали. Так что ни один из этих гномиков уже не ошибётся (хотя сам он знать об этом не будет).
                                                    0
                                                    Для последнего гномика возможное количество ошибок в классе равно длине последовательности.
                                                    Какую «именно ту последовательность»? Вот он последний гномик с не важно каким номером. Он не видит ничего. Какую последовательность он выберет и на что это повлияет?
                                                      0
                                                      По условию задачи, гномиков бесконечно много: «На каждого гнома из бесконечной очереди...» Так что говорить о «последнем гномике» — это то же самое, что говорить о последнем натуральном числе. У каждого гномика номер в очереди конечен (N). За каждым стоит конечное число гномиков. А перед каждым — бесконечное число, так что каждый имеет бесконечно много информации. У этой очереди нет не только конца, но и середины — каждый её элемент находится где-то в начале.
                                                        0
                                                        Тогда о каком конечном числе ошибок идет речь? Берите любое сколь угодно большое конечное число N, берите гномика N+1 — возможное число ошибок для выбранной им последовательности будет N+1. Это не конечное число.
                                                          0
                                                          Для любой последовательности найдётся такой гномик, что после него ошибок не будет. Поскольку они выбирают из множества Витали ту единственную последовательность, которая отличается от последовательности их цветов в конечном числе мест. А значит, есть последнее место, в котором они различаются, а после этого места — совпадают.
                                                            0
                                                            Для бесконечных последовательностей этот гномик бесконечно далеко. Это место есть, но для разных последовательностей оно разное. «последнее место» не равно «конечное».
                                                              0
                                                              Вы считаете, что существует последняя цифра числа «пи»? Или хотя бы числа 1/7? И чему же она равна?
                                                              Можно надеть шапки так, что их цвета будут соответствовать чётности цифр того же числа 1/7. Какого цвета будет шапка у «последнего гномика»?
                                                                0
                                                                Последней цифры чила «пи» не существует. Какая связь с гномиками?
                                                                Гномики не выбирают как надевать шапки и ничего не знают про этот алгоритм по условию задачи.
                                                                  0
                                                                  Точно так же и последнего гномика в бесконечной последовательности не существует. Гномики цветов не выбирают — их выбирает экспериментатор. И для последовательности цветов шапок он может использовать цифры любого вещественного числа, в том числе и «пи». Так какого цвета в этом случае будет шапка у последнего гномика?
                                                                    0
                                                                    Вы сами только что сказали, что гномик не определен, а теперь спрашиваете его цвет — вопрос не имеет смысла и соответственно ответа.
                                                                    Как все то, что Вы только что сказали помогает определить конечность числа ошибок?
                                                                      0
                                                                      Значит, я неправильно понял фразу «Для бесконечных последовательностей этот гномик бесконечно далеко». Да, для каждой последовательности цветов шапок место последней ошибки своё — но для каждой последовательности это место есть, и для каждой последовательности оно конечно (поскольку элементов с бесконечными номерами не существует). Да, оно может быть сколь угодно далеко (в том смысле, что для любого N найдётся последовательность с более, чем N ошибками), но для каждой последовательности число ошибок остаётся конечным.
                                                                        0
                                                                        Уже было — так рассуждать нельзя.
                                                                          0
                                                                          Там было «для каждой конкретной последовательности число ошибок конечно, и ограничено длиной этой последовательности» Какое это отношение имеет к бесконечным последовательностям, я не понимаю — у них длины (как натурального числа) нет. И требования, чтобы максимум числа ошибок по всем последовательностям был конечным, в задаче нет.
                                                                            0
                                                                            Если у них нет длины, как вы их сравнили и создали класс? Вдруг на бесконечном элементе они снова начнут отличаться? Только не надо про возможность создания такой бесконечной последовательности, для которой это будет возможно исходя из способа ее формирования. Тогда задачу можно выродить в одеть всем синюю шапку и всем называть цвет который видят.
                                                                            Требование есть: по условию задачи способ раскраски неизвестен — поэтому придется рассмотреть все возможные последовательности и заключить для них конечность ошибок, не для каждой в отдельности, а для любой.
                                                                              0
                                                                              поэтому придется рассмотреть все возможные последовательности и заключить для них конечность ошибок, не для каждой в отдельности, а для любой.

                                                                              Правильно, именно так она и решается. Берутся все возможные последовательности, делятся на классы эквивалентности по отношению «различаются не более, чем в конечном числе элементов» (то, что это отношение эквивалентности, т.е. рефлексивно, симметрично и транзитивно — проверяется элементарно), далее в каждом классе выбирается какая-нибудь последовательность (по аксиоме выбора), и именно её гномики используют в качестве опорной после того, как разобрались, в каком классе их последовательность находится (а это может сделать любой гномик).
                                                                              Число классов континуально, число элементов в каждом классе счётно. Но из ZFC следует, что решение есть (хоть оно и неконструктивно).
                                                                                0
                                                                                А теперь просуммируйте ошибки бесконечного количества классов так, чтобы получилось конечное число ошибок.
                                                                                  0
                                                                                  А зачем? У нас одна последовательность цветов (неизвестно какая), складывать её ошибки ни с чем больше не надо.
                                                                                    0
                                                                                    Чтобы оценить сколько ошибок приходится на одну бесконечную последовательность. В среднем, а не для какой-то заранее известной.
                                                                                      0
                                                                                      Это и так понятно. В среднем — бесконечно много. Но матожидание случайной величины, принимающей конечные значения, вполне может быть бесконечным — в этом нет никакой трагедии.
                                                                                        0
                                                                                        «В среднем — бесконечно много.» — это ответ на задачу и все остальное в принципе не важно.
                                                                                        «матожидание случайной величины, принимающей конечные значения, вполне может быть бесконечным» — с каких пор среднее конечных чисел бесконечно?
                                                                                          0
                                                                                          Ну, например, чему равно среднее арифметическое членов натурального ряда? Каждое натуральное число конечно. Или среднее значение функции 1/x на интервале от 0 до 1? Она принимает конечное значение в каждой точке.
                                                                                            0
                                                                                            Числа на интервале от 0 до 1 могут быть и бесконечно малыми.
                                                                                              0
                                                                                              Нет, всего лишь сколь угодно малыми. Бесконечно малые — это уже из нестандартного анализа.
                                                              0
                                                              Гномики с конечным номером ничем друг от друга не отличаются. Поэтому если ошибку сделали конечное число гномиков, они должны иметь бесконечный номер в очереди.
                                                                0
                                                                Не может быть бесконечного номера. Номера — это числа. Сколь угодно большие номера — да. Это значит, что какое число N ни взять, злодей сможешь надеть на гномов колпаки так, чтобы неугадали какие-то гномики с номерами больше N.
                                                                  0
                                                                  Значит этих гномиков не существует. Значит либо все гномики угадают свой цвет, либо количество не угадавших — бесконечно.
                                                                    0
                                                                    Не могли бы вы пояснить, почему «значит»?
                                                                      0
                                                                      Ещё раз: чтобы количество казнённых гномиков было конечно, необходимо, чтобы гномики на бесконечном отрезке гарантированно угадали свой цвет. Но так как для первого гномика ситуация ничем не отличается от гномика №N. Поэтому если есть решение, при котором начиная с N-го гномика все гномики угадывают свои шапки, то это же решение применимо для гномика № N-1, и для гномика №1. Разве что если среди гномиков попадётся гномик-эмо, который захочет таким образом избавиться ото всех этих мучений с угадыванием шапок раз и навсегда.
                                                                        0
                                                                        Это неправда. Давайте я вам приведу пример. Задача: дается вещественное число Х. Каждое натуральное число сравнивает себя с Х и убивается, если Х оказывается больше. Убьется, вне зависимости от Х, конечное число нат. чисел. Однако нельзя сказать, что раз на бесконечном отрезке числа выживут, то можно применять стратегию к меньшим числам, и выживут все.
                                                                        Ситуации для гномиков различаются: они видят разные хвосты последовательности, их положения в очереди различаются, и поэтому они по-разному делают вывод о своем цвете.
                                                                          0
                                                                          Тем не менее, гномик №N-1 видит тот же хвост последовательности, что и гномик №N плюс самого гномика №N. Таким образом у гномика №N-1 не меньше информации о последовательности, чем у гномика №N.
                                                                            0
                                                                            В вашем примере как раз для чисел меньше X ситуация отличается, в примере с гномиками — нет.
                                                                      0
                                                                      Вы меня путаете. Я конечно же имел ввиду гномиков, бесконечно удалённых от начала очереди.
                                                                        0
                                                                        Что значит бесконечно удаленных?
                                                            0
                                                            По такой логике гномики могут вообще ни о чём не договариваться, а просто называть случайный цвет.
                                              0
                                              Почему нельзя? Каждый конкретный гномик ошибается или не ошибается, гномиков много, чем не пространство?
                                              0
                                              Не совсем. Все гномики определят принадлежность к классу абсолютно одинаково, поскольку каждый не видит лишь конечное число колпаков, что никак не мешает ему определить верный класс текущей последовательности. Затем все абсолютно одинаково выберут представителя класса (о том, как это сделать, они договариваются заранее). Теперь текущая последовательность и выбраный гномиками представитель, по причине принадлежности одному классу, различаются лишь конечным числом колпаков. Пусть они считают, что представитель и есть текущая последовательность (хоть и видят, что это не так). Ошибется лишь конечное число гномов. Сколь угодно большое, но конечное.
                                                0
                                                В математике правда существует понятие «Сколь угодно большое конечное число»? Можно ссылку?
                                                  0
                                                  Такого конкретного объекта не существует. Давайте я вам приведу пример. Можно начать щелкать пальцами и считать количество щелчков. Вы можете щелкнуть столько раз, сколько захотите, — больше любого наперед заданного числа. Тем не менее это будет конечное число щелчков.
                                                    0
                                                    Если физически, то больше любого наперед заданного не смогу. Если математически, Вы только что описали доказательство бесконечности натурального ряда чисел.
                                                    0
                                                    Обычно это понятие встречается в контексте «для сколь угодно большого натурального числа N выполняется такое-то условие».
                                                      0
                                                      Ряд натуральных чисел бесконечен.
                                                        0
                                                        Вот для всех их оно и выполняется. Например, «для сколь угодно большого натурального числа N существует простое число, большее N» — вполне типичная формулировка теоремы.
                                                        Другой вариант — «число элементов в каком-то множестве (например, делителей числа) может быть сколь угодно большим». Это синоним утверждения «для любого N найдётся множество из указанного семейства, число элементов которого будет больше N».
                                                0
                                                Решение — гномы должны договориться называть синий цвет, если видят перед собой синие и красные шапки, или только синие, в случае если перед гномом все шапки красные — он должен назвать красный цвет
                                                  +1
                                                  Тогда в ситуации, когда цвета чередуются (синий-красный-синий-красный-...) съедят всех, у кого шапки красные. А их бесконечно много.
                                                  0
                                                  Кстати, можно упростить задачу — пусть известно, что цвета шапок гномиков образуют биты рационального числа, т.е. последовательность, начиная с какого-то места, периодическая. Тогда алгоритм становится полностью конструктивным — находим период, продолжаем его до себя и называем соответствующий цвет. И всё равно для каждого конкретного гномика вероятность ошибиться будет 1/2 :)
                                                    0
                                                    Да, вот только периодических последовательностей маловато =)
                                                      0
                                                      Если я не ошибаюсь, нету алгоритма, который находит период числа, если известно, что число периодическое. Вдруг этот настоящий период оооочень большой, намного больше «мнимого» периода, который напрашивается в первую очередь.
                                                      0
                                                      о чем они все вместе договорились перед тем, как получить колпаки

                                                      Раз у них была возможность договариваться, то ошибку можно снизить ровно до одного гнома. Перед раздачей колпаков договориться, что если гном сзади видит красный колпак перед собой, то пинает гнома по правой ноге, а если синий- то по левой. Таким образом ничего не узнает только первый гном и большая часть их племени спасена :)
                                                        0
                                                        Не проходит: «гном знает лишь то, что видит, свое положение в очереди и то, о чем они все вместе договорились...» Так что он не знает, по какой ноге его пнули :(
                                                        0
                                                        Наименьшую последовательность в классе, содержащем последовательность из одних синих колпаков найти можно. Все последовательности этого класса содержат конечное количество красных колпаков, то есть число последовательностей в нем счетно:
                                                        Можно представить каждый бесконечный бинарный вектор с конечным числом единиц как два числа: количество ведущих нулей и число, представленное бинарной записью от первой единицы до последней. То есть это множество равносильно множеству рациональных чисел. (Ничего не напутал?)

                                                        Можно ли сказать, что в любом классе, на которые заданным отношением эквивалентности делится множество любых бесконечных бинарных векторов будет счетное число членов?
                                                          0
                                                          То, что число членов в любом классе счётно — верно: возьмём «исключающее или» двух последовательностей из одного класса — получим число с конечным числом единиц, т.е. двоично-рациональное. То есть, каждый элемент класса, в котором уже выбран канонический представитель, кодируется одним двоично-рациональным числом.
                                                          А вот найти наименьший элемент в счётном множестве можно не всегда: попробуйте, например, множество 1/(2^n), n — натуральные.
                                                          Вполне упорядочить континуум без аксиомы выбора мы, к сожалению, не можем…
                                                            0
                                                            Эх, если бы так просто можно было сказать. Я вот тоже всё пытался свести к вполне упорядоченному континууму, но как назло все классы счётные, упорядочивать нужно только внутри них, а друг к другу они отношения не имеют.
                                                              0
                                                              В чём проблема? Если бы у нас был вполне упорядоченный континуум, то в любом его подмножестве был бы наименьший (в смысле этого порядка) элемент. Существование функции выбора на P(S), насколько я понимаю, эквивалентно возможности вполне упорядочить S.
                                                                0
                                                                Упс, а я и не знаю, что такое P(S).
                                                                  0
                                                                  То же, что и 2^S — множество всех подмножеств.
                                                                    0
                                                                    Да, из упорядоченного континуума следует, конечно же, существование фукнции выбора. Однако нужно было наоборот: предположим, что гномики умеют выбирать представителей, следует ли отсюда, что они могут вполне упорядочить [0; 1]? Если да, то необходимость аксиомы подтверждена. Однако не факт, что следует, так как описанные классы — это далеко не 2^[0; 1].
                                                                      0
                                                                      В рамках псевдонаучных спекуляций:

                                                                      Если у нас нет аксиомы выбора, то можно предположить существование двух экзотических объектов:
                                                                      1) аморфное множество — бесконечное множество, которое нельзя разбить на два непересекающихся бесконечных подмножества.
                                                                      2) Объединение M счётного числа двухэлементных множеств S_i, для которых нет функции выбора, т.е. для любого подмножества X множества M пересечение X с S_i содержит либо 0, либо 2 элемента для всех i, кроме конечного их числа.

                                                                      Предположим, что эта экзотика водится среди подмножеств континуума. Что из этого можно извлечь?
                                                                        0
                                                                        В рамках данной задачи — не представляю. А если просто так, то
                                                                        1) Аморфное множество мощнее континуума, так что его нельзя даже представить. И что говорить о нем? =)
                                                                          0
                                                                          Аморфное множество несравнимо по мощности ни с каким бесконечным вполне упорядоченным множеством, и не мощнее никакого бесконечного множества (кроме совсем небольшого класса). Оно даже не содержит в себе ни одного счётного подмножества. Так что, в каком-то смысле оно совсем небольшое.
                                                                            0
                                                                            Да, я ошибся. Даже представляю себе что-то такое, но что с ним делать, пусть оно и было бы, ума не приложу.
                                                                              0
                                                                              Ещё можно попробовать разобраться в доказательстве отсутствия неизмеримых множеств при выполнении аксиомы детерминированности: seminariomatematico.dm.unito.it/rendiconti/61-4/393.pdf. Может быть, она и «функцию гномиков» отменит?
                                                                          0
                                                                          Увы, вашего аморфного множества не существует, что доказывается тривиально. Любое бесконечное множество содержит счетное подмножество, которое биективно, например, натуральным числам. Если количество оставшихся элементов бесконечно — разбиение уже построено. Если же конечно, возьмем две биекции из четных и нечетных чисел в испытуемое множество, а конечный остаток припишем к любой из частей.
                                                                            0
                                                                            В модели ZFC. Если же отказаться от аксиомы выбора (весьма спорной аксиомы), то всё становится совсем иначе.
                                                                              0
                                                                              Где у меня используется аксиома выбора?
                                                                                0
                                                                                В утверждении «любое бесконечное множество содержит счетное подмножество»
                                                                                  0
                                                                                  Математика без аксиомы выбора превращается в странную вещь… Погуглил — и в самом деле. Но не следует ли отсюда, что существуют множества, мощностью меньше счетной? И если это не так, как тогда доказать минимальность счетной мощности?
                                                                                    0
                                                                                    Например, аморфное множество, менее мощно, чем счетное.
                                                                                      0
                                                                                      Про аморфное множество нельзя сказать, что оно «менее мощно, чем счетное». Их мощности несравнимы, ни одно из них не содержит подмножества, эквивалентного другому. Оно является частным случаем более широкого класса — множеств, «конечных по Дедекинду» (тех, мощность которых изменяется при добавлении к ним ещё одного элемента).
                                                                                      0
                                                                                      «Минимальность счётной мощности» означает, что каждое подмножество натурального ряда либо счётно, либо конечно. Можно воспользоваться тем, что у любого подмножества есть минимальный элемент, и просто пересчитать все элементы подмножества по возрастанию. Либо номера закончатся — тогда подмножество конечно, либо нет — тогда каждому натуральному числу будет соответствовать какой-то элемент подмножества, а значит, оно эквивалентно натуральному ряду, т.е. счётно.
                                                                                        0
                                                                                        Это классическое доказательство. Выходит, в нем используется аксиома выбора. Никогда не задумывался над этим.
                                                                                          0
                                                                                          Не используется. «Выбрать наименьший элемент из подмножества» — конструктивная операция, для неё аксиома выбора не нужна. Как и вообще для построения натурального ряда.
                                                                                          Если мы возьмём классическое построение: 0={}, N+1=N U {N}, то наименьшим элементом множества натуральных чисел будет пересечение всех его элементов.
                                                                0
                                                                Нет, так сказать нельзя. Пусть мое отношение эквивалентности будет константа true. Тогда класс будет один и он будет той же размерности, что и пространство. Или же пусть отношение будет «совпадает первая координата». Классов два, оба континуальные.
                                                                  0
                                                                  Я имею в виду множество и отношение эквивалентности, указанные в задаче.
                                                                  Для того, чтобы избавиться от аксиомы выбора в решении, надо даже не упорядочивать подмножества, а иметь способ находить в каждом из них первый вектор (по какому-нибудь общему для всех подмножеств признаку).
                                                                    0
                                                                    Прошу прощения, не правильно понял вас из-за «любых бинарных векторов». Да, последовательностей в каждом классе счетно. Но первый вектор во всех классах выбрать не получится. Введение в ответ на вопрос «почему?» написано в четвертом разделе статьи.
                                                                      0
                                                                      Это если искать именно минимум. По такому же обоснованию нельзя найти минимум в множестве рациональных чисел исключая ноль. Но их можно упорядочить так, что первое число в последовательности будет четко определено. Емнип, это делается, например, так:
                                                                      1/1 1/2 1/3…
                                                                      2/1 2/2 2/3…
                                                                      3/1 3/2 3/3…
                                                                      .
                                                                      .
                                                                      .
                                                                      А считаем сначала элемент на месте 0,0, потом 0,1 потом 1,0 и так далее, по диагоналям.
                                                                        0
                                                                        Нет, необходимость аксиомы выбора говорит о том, что найти принцип, по которому можно было бы выбирать элемент из каждого класса, нельзя =) Можно взять какой-то конкретный класс, как-то упорядочить его и найти особенный вектор в нем. Но сделать это во всем разом не выйдет.
                                                                        В третьей части я написал, почему легчикографический минимум не подходит. А четвертая часть про то, почему ничего не подойдет. Вот невозможно придумать такой способ выбора особого представителя, чтобы он сработал сразу для всех классов.
                                                                          0
                                                                          Внимательнее перечитал четвертую часть и, кажется, даже понял :)
                                                                          Статья — отличная разминка для мозгов, спасибо.
                                                                            0
                                                                            Не за что =) Для того, можно сказать, и писал.
                                                                      0
                                                                      Чтобы избавиться от аксиомы выбора, надо решить задачу выбора для данного множества :) Верно… Но, по-моему, перспективнее встречный подход — сначала показать, что без аксиомы выбора такой функции в данном случае может и не быть, а потом — что гномики в такой ситуации вообще проиграют. Но это очень сложно, там почти не за что зацепиться.
                                                                  0
                                                                  Предположим, что у гномиков есть выигрышная стратегия, причём детерминированная. Вопрос: можем ли мы с её помощью получить функцию выбора на классах эквивалентности?
                                                                  Ответ: да.
                                                                  Возьмём любой класс. Наденем на гномиков шапки в соответствии с любой последовательностью из этого класса (без АС мы этого сделать не сможем, поэтому будем проводить счётное число экспериментов параллельно). Зададим гномикам Вопрос, возьмём последнего не угадавшего свой цвет, и поменяем его шапку на другую. Его точка зрения не изменится (он видит то же, что и раньше), у гномиков, стоящих перед ним — тем более. Гномики, находящиеся ближе к началу очереди, могут изменить свой ответ, но нам это неважно — главное, что в следующий раз гномик, шапку которого мы поменяли, не ошибётся, и «зона ошибки» уменьшится.
                                                                  За конечное число таких шагов мы получим последовательность из нашего класса, в которой ни один гномик не ошибся. Очевидно, что для любых двух стартовых последовательностей из одного класса итоговая последовательность получится одной и той же, таким образом, мы получили функцию выбора.
                                                                  Таким образом, задача полностью сводится к поиску модели, в которой функции выбора для наших классов нет. Если мы такую модель найдём — гномики проиграют.
                                                                    0
                                                                    Я не понял, честно говоря. Какую злодей последовательность ни выберет, после конечного числа шагов все гномики назовут ее (0 ошибок). Каким это образом тут задается функция выбора?
                                                                      0
                                                                      Гномики не могут использовать результаты предыдущего эксперимента, их стратегия всегда одинакова. Последовательность меняет злодей, а гномики только подсказывают ему, как её менять (например, он каждый раз может надевать на гномиков шапки тех цветов, которые они назвали). Утверждается, что (1) при любой стратегии гномиков и любой исходной последовательности этот процесс стабилизируется за конечное число шагов, (2) что результат стабилизации лежит в том же классе, что и исходная последовательность, и (3) что для всех последовательностей из одного класса результат стабилизации одинаков. А значит, в каждом классе появился канонический (при данной стратегии гномиков) элемент.
                                                                  • UFO just landed and posted this here
                                                                      0
                                                                      Если применять коценпции теории алгоритмов, то вот статья, в которой доказывается, что невозможно найти минимальный алгоритм, выполняющий заданную задачу =)
                                                                      Если конечно сами гномики — машины Тьюринга.
                                                                      • UFO just landed and posted this here
                                                                      0
                                                                      Спасибо за прекрасную задачу. Действительно заставляет задуматься.
                                                                      Есть две разные «математики» — с аксиомой выбора и без нее. Обе математики (пока) имеют право на существование, так как никто не доказал, что они противоречивы. И вопрос верно ли авторское решение теряет смысл в этом контексте. Решение верно в математике с аксиомой выбора и неверно в математике без аксиомы выбора. Вот и все.

                                                                        0
                                                                        Моей целью было показать, что и с аксиомой выбора авторское решение неверно. Двумя комментариями выше человек, вроде бы, поставил точку, доказав, что решения и вовсе нет.
                                                                          0
                                                                          Как ни странно, нельзя даже сказать, что «без аксиомы выбора решения нет». Ведь может быть такая ситуация, что аксиома выбора в полном объёме не действует (например, для подмножеств гиперконтинуума), но, несмотря на это, континуум можно вполне упорядочить. Тогда и функция выбора для гномиков будет существовать. Всё, что пока удалось доказать — что решение есть тогда и только тогда, когда есть функция выбора на классах эквивалентности. И что существует модель (ZF+AD), в которой этой функции нет.
                                                                            0
                                                                            Хм, в статье я даже не упомянал об возможности невыполнения АС. Пост как раз о том, что пусть даже она и есть, решения всё равно нет — так и так нет. И вы это более-менее подтвердили чуть выше =)
                                                                              0
                                                                              Я как раз считаю, что при наличии АС решение есть. Правда, для нас оно неконструктивно, а гномики, чтобы им пользоваться, должны иметь быстродействие не менее континуума операций в секунду (или знать порядок элементов вполне упорядоченного континуума наизусть, тогда им хватит счетного числа операций).
                                                                                0
                                                                                Понимаете, если вы докажете, что решения у задачи нет (с аксиомой выбора), то тем самым решите фундаментальную проблему человечества и докажете противоречивость ZFC. Потому что все рассуждения в авторском решении следуют из аксиом ZFC.

                                                                                Пытаясь поставить задачу в интуитивные русла, вы забываете, что в ней речь идет о бесконечном наборе гномиков, и вы не можете бесплатно оперировать такими интуитивные понятиями типа: «как гномикам договориться» или «гномик видит шапки на всех гномиках перед ним». Вся проблема в том, что задача не реализуема на практике (принимай ты аксиому выбора или не принимай), так как гномиков бесконечно. Единственное, что мы можем сделать в такой ситуации — это признать, что задача про гномиков чисто формальная и не реализуема в реальной жизни. И теперь, приняв это, мы спокойно можем решать эту формальную задачу в разных аксиоматических системах (с аксиомой выбора и без нее). В разных системах наша формальная задача может иметь разный ответ. И ничего страшного в этом нет. Грубо говоря, на практике все равно не проверить, поэтому наша интуиция нам не друг.
                                                                                  0
                                                                                  решите фундаментальную проблему человечества и докажете противоречивость ZFC

                                                                                  Учитывая, что почти вся современная математика основана на ZFC, получается, что фундаментальная проблема человечества — существование математики? :D
                                                                                    0
                                                                                    Не совсем. Если кто-либо завтра докажет, что ZFC противоречива или же, еще проще, арифметика противоречива, то, да, формально вся математика рухнет. Но не забываем, что математические идеи очень живучи. Почти все рассуждения выживут, или же потребуют косметического ремонта.
                                                                          0
                                                                          Но не буду вас слишком запутывать, и так уже нагородил. Дело в том, что я вас только что обманул. Кто попался? Нельзя выбрать наименьший в лексикографическом порядке элемент класса.

                                                                          Подлый, коварный автор! Я прошерстил все комменты, прежде чем догадался прочитать псто дальше. Никак не мог поверить, что такую лажу никто не заметил)
                                                                            0
                                                                            deleted
                                                                              0
                                                                              О чем этот пост вообще?
                                                                                0
                                                                                Да так… парадоксы неконструктивной математики и их интерпретация. Смешная вещь, но с практической точки зрения — не более, чем разминка для мозгов.
                                                                                –3
                                                                                А мне показалось, что разговор все-таки ни о чем. Нет, конечно о чем-то говорят, но это все равно ни о чем. Выращенные в физтехах, верящие в существование абсолютной истины, фанатики симметрии пытаются найти смысл и стройность в загадочном мире. И все только ради того, чтобы не меняться и заставить других верить в подобную инерцию. Сколько открытий же им принесет новый мир, который наступает и никого не спрашивает.
                                                                                  –2
                                                                                  Минусующие, объясните мне, что такое бесконечность?
                                                                                    +2
                                                                                    Какая абсолютная истина? Какой-такой мир? Половина разговора шла о том, что в разных математиках ответ на задачу различен — так что ни о какой абсолютной истине никто и не думает. И ни одна из этих математик ни к какому миру отношения не имеет. Какой бы новый мир не наступил, для него найдётся какая-нибудь модель где-нибудь на задворках математики (частный случай, например, фрактальная размерность 9+2/3 с трансфинитным временем… кого этим можно удивить?)
                                                                                      –2
                                                                                      фрактальная размерность 9+2/3 с трансфинитным временем
                                                                                      1: 0 в вашу пользу.

                                                                                      Но я не считаю, что математика была или будет неприменима. Я считаю, что математики и теор. физики уже вынуждены крошить фундамент на котором стоит их последовательное описание мира, чтобы двигаться дальше (тупо, чтобы получать зарплаты). И эта задача именно об этом. О том, что само понятие модели подвергается деконструкции. А обсуждение пустое, потому что его участники находятся либо со стороны одной математики — одной абсолютной истины, либо со стороны другой. И никто даже не пытается отойти от модели модели. Куда удобнее и мягче конструировать урода дальше.
                                                                                    +1
                                                                                    Доказал ли я неверность авторского решения? Думаю, что да. Формулировка задачи — как гномикам договориться. Необходимость аксиомы выбора однозначно говорит, что ответа на «как» в решении нет и быть не может.

                                                                                    Думаю что нет, не доказали. По формулировке задачи гномики таковы, что как-то способны воспринимать и оперировать любыми бесконечными последовательностями шапок сразу и целиком. Поэтому, думаю, и «говорить» и «сравнивать» такие последовательности они умеют. Значит как-то договорятся.

                                                                                    Only users with full accounts can post comments. Log in, please.