Загадка про гномов и золото
Обновлено: 22.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 процентов, так как последний из них вполне мог и угадать цвет своей шапки.
Условия остаются такими же. Все гномы стоят в колонне и могут видеть только тех, кто впереди. Но при этом им нельзя повышать или понижать голос, а также как-то иначе менять его.
Допустим, синие шапочки, это – ноль. А белые – единица. Гном, который стоит последним, подсчитывает количество синих и белых шапочек, и, если в сумме получается четное число, говорит – «синяя», а если нечетное – «белая». То есть, он говорит цвет, который вычислил делением всей суммы шапочек на два. Шестой гномик, проделав ту же процедуру, вычисляет цвет, который соответствует его номеру, и таким образом спасается. Точно так же делают все впереди стоящие гномы.
Читайте также: