Загадка про гномов и золото

Обновлено: 04.11.2024

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

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

Часть 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, конечно же), но выбирать этих представителей они все одинаково не смогут, поскольку описать эту функцию невозможно.

Следующая загадка

Гномики. Детские загадки про гнома.

Загадки про сказки

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

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

ЧИТАЙТЕ ТАКЖЕ: Загадки про помидор.

Кто там на горе стучится день и ночь: «тук» да «тук»?
Кто несет домой и прячет золото в сундук?
Кто там ходит ростом с детский башмачок?
Умник, Скромник, Соня, Ворчун и Простачок!

Ответ

Они жители лесные
Очень добрые смешные.
Вместо шапки колпачок.
Рост с ребячий башмачок.
С ними девушка жила.
Очень доброю была.
Любила стряпать и вязать
Дом в порядке содержать.

Ответ

К нам пришел из сказки он -
Постучал в окошко.
Этот старый добрый …

Ответ

Он пришел из сказки к нам,
Постучал тихонько в дом,
В ярком красном колпачке —
ну, конечно, это …

Ответ

Что стоит тут за игрушка?
Колпачок, в руках ватрушка
Бородатый, маленький —
Ростом прям как валенки …

Ответ

Отгадай, что за игрушка?
Колпачок, как у Петрушки.
Маленький, удаленький,
Каблучками он стучит,
Колокольчиком бренчит.

Ответ

Он носит вместо шапки
Весёлый колпачок.
И ростом он всего лишь
С ребячий бошмачок.
С фонариком и с песней
Идёт в лесу ночном.
Не ошибёшься, если
Ты скажешь:
— Это …

Загадка про гнома и лифт на логику

Гномик жил на 7 этаже. Каждый день он спускался на первый этаж и шел на работу. А, когда возвращался, он поднимался на третий этаж, а остальные четыре проходил пешком. Почему?

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

загадка про гнома для детей

Коллекция рифмованных загадок

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

Следующая загадка

Развитию ребенка способствуют загадки. Постоянное решение незатейливых словесных "задачек" развивает детскую фантазию. Это тренировка, которая помогает искать логическую связь между предметами, образами и ситуациями. Известна также польза загадок и в развитии речи, размышление вслух пополняет словарный запас ребенка.

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

загадка про гномов и великана

Загадка математическая

Гномику на одну ночь хватает одной свечи. Из пяти не догоревших свечек он может сделать еще одну новую. Сколько он может сделать свечек, если у него есть 25 огарков?

Шесть. Из 25 огарков гномик сделает 5 свечек. Когда они догорят, из оставшихся от них пяти огарков он сделает еще одну свечу.

загадка про гнома в стихах

Следующая загадка


Mylabris

Необходимо помочь Белоснежке вспомнить все о 7 гномиках и их привычках.
Итак, Белоснежка точно помнит, что:
- Каждому гномику ежедневно готовит его любимое блюдо,
- Гномы каждый день по очереди помогают ей заниматься хозяйством.
- За столом все гномы сидят на постоянных местах.
- У каждого есть свой любимый напиток и блюдо, а посуду украшает свой цветок.
- Все гномы носят разную обувь и одежду разного цвета.
- Каждый ухаживает за какой-то живностью: зверушкой, птичкой или рыбкой.

Вопросы:
1. Как зовут гнома с самой длинной бородой?
2. Как сидят гномы с Белоснежкой за столом?
3. Кто помогает Белоснежке в понедельник?

Коллекция коротких загадок

Гном - это любимый всеми персонаж, знакомый детям и взрослым по таким сказкам, как "Белоснежка и семь гномов", "Хоббит", "Маленькие человечки" и т. д. Ребенок знакомится с этими карликами при помощи просмотра мультфильмов, рассматривая картинки в книгах. Поэтому отгадывание загадки про гнома для детей превратится в забавную и интересную игру.

Коротенькие загадки для детей о гномах:

  • Маленький, бородатый, в колпаке и с лопатой. Кто он? (Гном).
  • У него есть красный нос, красные сапожки. Он почти как Дед Мороз, только ростом не дорос. Кто это? (Гном).
  • Жили с Белоснежкой звери, птицы и… (гномы).
  • Кто там на горе стучится день и ночь: «тук» да «тук»? Кто несет домой и прячет золото в сундук? Кто там ходит ростом с детский башмачок? Умник, Скромник, Соня, Ворчун и Простачок! (Гномы).

Загадка про гномов и великана для взрослых

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

Вопрос: что придумали гномы ради своего спасения?

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

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

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

загадка про гнома

Читайте также: