Загадка про гномов и шапки

Обновлено: 25.12.2024

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

2. Допустим. На мне надет черный. Любой из оставшихся двух это видит и думает "на нем черный. Если на мне тоже черный, то третий бы это увидел и догадался, значит скорее всего на мне белый" но он так не говорит! Те, гипотеза то что на мне черный неверна.

8 лет назад Он рассуждал так: "Предположим, что на мне черный колпак. Тогда второй мудрец видит напротив себя один белый и один черный колпаки. В таком случае он должен был бы догадаться, что на нем белый колпак, исходя из того, что иначе третий мудрец, видя перед собой два черных колпака, понял бы, что сам в белом. Раз такого не произошло, следовательно на мне - белый 8 лет назад Напомнило историю "Есть два стула. ")) 8 лет назад Так у них были закрыты глаза или они смотрели друг на друга? раскрыть ветку 1 8 лет назад Они закрыли глаза, когда на них надевали колпаки. Потом открыли 8 лет назад Предположим, — сказал мудрец-победитель, — на мне белый колпак. Как тогда должен вести себя мудрец, который стоит от меня по правую руку? Мудрец, стоящий от меня по правую руку, может высказать два предположения:
предположение 1 (стоящего справа) — на мне белый колпак
предположение 2 (стоящего справа) — на мне чёрный колпак
Как должен рассматривать свои два предположения мудрец стоящий справа от меня?
Рассматривая своё предположение 1, мудрец стоящий от меня справа, должен сделать вывод, что третий наш мудрец должен просто кричать: "На мне чёрный колпак!". Но он же этого не кричит. Значит, мудрец, стоящий справа от меня должен отбросить своё предположение 1.
Тогда мудрец, стоящий справа от меня должен подумать так: "Наше предположение 1 неверно, значит, верно предположение 2, как отрицание предположения 1, значит, на мне чёрный колпак. "
Таким образом, мудрец, стоящий справа от меня, должен кричать: "На мне чёрный колпак. "
Но он же этого не кричит. Значит, наше предпложение о том, что на мне белый колпак, неверно.
Значит, на мне чёрный колпак! раскрыть ветку 1 8 лет назад Ебануца! Я явно не мудрец. ) 8 лет назад Для случая, когда использованы оба чернух колпака - очевидно. хотя бы один из мудрецов видит два черных на других - значит, на нем белый.
Менее скучные вариант: 1 черный, два белых. Допустим, наш мудрец видит черный и белый. Если бы тот, кто сидит в белом перед ним, видел на нам черный, он бы уже давно сказал правильный ответ (пункт 1).Значит, на нашем мудреце не черный - значит, белый.
Хардкор. Три белых. Но у нас же мудрецы! Они знают, что если кто-то видит черный и белый, то по второму пункту довольно быстро можно сказать, какой на тебе колпапк. (как раз несколько часов на раздумья). Значит, если ни один не юзает второй вариант, то все колпаки белые. показать ещё 0 комментариев Похожие посты 4 месяца назад

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

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

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

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

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

Часть 1/4. Размышления.

Часть 2/4. Авторское решение.

Часть 3/4. Что не так.

Часть 4. Аксиома выбора.

Интересный был покойник

- А вы слышали? Герман Савельевич-то умер на прошлой неделе! – слегка взволновано говорила Светлана, туже затягивая шарф на шее своего пятилетнего сына. – Не скажу, что неожиданно, ему же… сколько там ему лет было?

- Честно говоря, не знаю, - протянула Зоя. – Мы с ним и знакомы-то почти не были, я же переехала сюда только год назад.

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

- Пугающий? Что это значит? – поинтересовалась Зоя. До этого она ничего подобного не слышала, да и при встрече с Германом Савельевичем странностей в нём не замечала.

- Согласна, - тут же закивала Света. - С ним явно было что-то не так. И мне было не по себе от того, что мы соседи.

- Так, а в чём дело? Что он сделал? – Зоя нахмурилась и почесала нос.

- Не то, чтобы сделал, - протянула Настя. - Вокруг него столько тёмных историй было. Говорят, в прошлом он был человеком опасным. Занимался всякими мутными делами. Потом на пенсию вышел, но дел своих не бросил.

- Всегда к нему какие-то подозрительные личности ходили, - вставила Света. – Я часто видела. И все они такие странные, всегда слишком вежливые, аж приторные. Бывало и расспрашивали меня ни с того, ни с сего.

- О чём расспрашивали? – с нескрываемым ужасом спросила Света.

- Ну, знаешь, о всяком, - Настя передёрнула плечами, словно стряхивая воспоминания, – спрашивали, как дела, сколько лет моему сыну, есть ли ещё дети, как мои родственники поживают. Такие, знаете, неприятные вопросы.

- Обычные же вопросы вроде, - недоумевала Зоя, - может, чтобы просто беседу поддержать.

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

- Герман Савельевич и сам непонятные вещи говорил, - Света махнула рукой, да так сильно, что Зое пришлось отскочить. - В лифте с ним не раз сталкивалась. Он то молчит, игнорирует меня, то вдруг спросит, на каком этаже я живу. А ещё он любил такую фразу говорить, что аж мурашки по кожи пробегали…

- Какую? – почти одновременно спросили Зоя и Настя.

- Да! Точно! – подтвердила Настя, тряся указательным пальцем. – Точно, точно! Прям кошмар!
Из этого разговора Зоя так и не поняла, чем таким ужасным занимался Герман Савельевич и почему наводил жуть на соседей. Но некий неприятный осадок поселился у неё в душе, девушка потом даже позвонила маме, которая раньше здесь жила, чтобы узнать подробности. Её мама особо ничего не рассказала. Соседа она встречала, как и его сына, но близко не общалась и странностей не замечала.

- Что? Вообще ничего такого? – переспросила Зоя.

- Не знаю даже… Он как-то за мукой приходил, потом вернул аж целую пачку и конфеты в подарок принёс. И всё. Мы с ним здоровались. Часто он был рассеянным. А так - нормальный мужчина. Мы особо не общались несмотря на то, что почти дверь в дверь живём. Сына его видела, приятный парень.

- Просто мне всякие сплетни про него рассказали, неужели ты их не слышала?

- Ну, ты же знаешь, я в основном на даче всегда. Может, и были какие сплетни, но я к ним не прислушивалась. Ты у Маргариты Семёновны спроси, из квартиры напротив. Она точно всё знает, - засмеялась мама. – И болтает, не затыкаясь.

- Ой, а ты слышала, что Герман Савельевич-то умер? Земля ему пухом! - сказала женщина со скорбным выражением лица, вяло перекрестившись.

- Да, мне говорили. Очень жаль. Правда, я не знала его совсем, - вежливо уточнила Зоя.

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

- Неспокойный? – Зою явно удивило такое определение. – Что вы имеете в виду?

- Ну, как же! Все в доме его прошлое обсуждали, сплетничали. Непонятно, чем он занимался, но дело это явно не бросил.

- Какое дело он не бросил? – Зое хотелось узнать что-то более конкретное.

- Следить за всеми! – тут же выдала Маргарита Семёновна. – У него блокнот такой был, он всё туда записывал. Кто, где, как и с кем живёт, чем занимается и всё подобное. Не очень-то это приятно, когда за тобой так откровенно следят. Кому это понравится? А всё от того, что он, как поговаривали, работал шпионом. Вот так и не бросил этого занятия и собирал информацию обо всех.

- Ааа! Вот оно что, - кивнула Зоя, понимая, что пошли уже какие-то фантазии. – А мне говорили, что он чем-то другим занимался.

- А почему ругались? – Зоя отстранённо рассматривала надписи на стене.

- Да кто ж их знает! Может, из-за квартиры. А, может, ещё из-за чего. Особенно в последнее время. Сын его, всё упрашивал отца куда-то переехать, вроде бы в санаторий. Но ты знаешь, небось, какая-нибудь больница для стариков. Вот Герман Савельевич и сопротивлялся.

- Вот оно как! - неопределённо ответила Зоя, не зная, что ещё сказать.

Судя по всему, Маргарита Семёновна могла рассказать ещё много чего, но Зоя торопилась, да и все эти истории напоминали дешёвые сплетни, и слушать их было скорее неудобно, чем интересно.

Зоя не могла понять одного, почему именно Герман Савельевич стал предметом обсуждения. Какие такие странности он вытворял, что о нём говорил весь двор? И почему она ничего такого не замечала, пока он был жив?

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

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

Через месяц, на вечеринке у соседей, девушка познакомилась с очаровательным молодым человеком по имени Филипп Германович. Он был ни кем иным, как сыном покойного и загадочного Германа Савельевича.

У молодых людей закрутился роман, и они начали встречаться. Разумеется, вскоре Зоя выяснила, что же за тёмная тайна окружала Германа Савельевича.

- Да какая уж тут загадка! - с лёгкой и немного грустной улыбкой поведал Филипп. - Отец всю жизнь проработал общественным работником в центре по борьбе с детской преступностью. Часто вызывался волонтёром и разъезжал по миру, помогая нуждающимся. Он стремился творить добро, как мог, и это у него хорошо выходило. А вот к старости у него начались проблемы с памятью, альцгеймер. Он всё в блокнот записывал, чтобы ничего не забывать. Не помогало. И знаешь, он был очень интересным человеком, пока жизнь свою не забыл.

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

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

Что придумали гномы? Если вы уже знаете эту загадку, не пишите, пожалуйста, ответ, дайте другим поугадывать)

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