Сегодня мы с вами разберём одну интересную задачку, которая на первый взгляд, кажется не решаемой! Мы часто смотрим голливудские фильмы про маньяков. Но частенько бывает, что жертва вызывает стыд, так как, НУ НЕ МОГУТ БЫТЬ АМЕРИКАНЦЫ НАСТОЛЬКО ТУПЫМИ!
Так вот, а теперь поставим себя на место жертвы, проверим как вы справитесь. Только маньяк наш уже не обычный, а повёрнутый на всяких головоломках.
Меня украли
В общем, ситуация такая: маньяк крадёт тебя и ещё 4-х ребят, ну, уж никак не знакомых тебе. Но маньяк не хочет просто так убивать, ему нужна игра.Вот он отвёз вас в Кызыл, чтоб вам не было смысла сбегать(поверьте, лучше не надо). Селит вас в своей деревне и тут начинается игра. Каждому из вас наш маньяк помечает лоб красной или зелёной краской, связывает руки и затыкает рот.
Правила в игре такие:
- Перед каждой ночью вас собирают в одной комнате. Вы видите друг друга и, соответственно, цвет каждого из вас. Но свой вы не видите. Так как ваши руки связаны, а рот закрыт, то как-то передавать друг другу сигналы вы не можете
- После каждого собрание вы снова отправляетесь по своим комнатам. При этом каждую ночь вы имеете право прийти к маньяку. Но просто так на свободу он вас не высвободит. Его условия таковы:
- Если лоб у тебя зелёный, то можешь выходить на свободу
- Если красный-то кирдык
- Если же все зелёные вышли на свободу, то они точно настучат полицейским, поэтому маньяку проще отпустить красных в 5-й день отпустить оставшихся красных ребят
- При этом есть важное условие! Хотя бы одна из жертв должна быть зелёной и остальные об этом условии знают
При этом, наш псих живёт на прожиточный минимум-поэтому кормить он вас не будет. Так как человек без еды где-то дней 5 протянет, то времени на спасения немного. И вот задача:
Смогут ли все наши жертвы спастись за 5 дней?
На первый взгляд, кажется, что нет. Так как они даже коммуницировать не могут. И вообще зачем нам эти лбы, придётся рисковать...
Но математическое мышление поможет нашим товарищем!
Аоаооааа что делать?!?!!!
Давайте также допустим, что среди нас нет самоубивц, то есть человек не пойдёт к маньяку, зная, что он красный. Также среди нас нет тупых! То есть как-то догадавшись, что он зелёный, он той же ночью уйдет. Чтобы решить задачу, надо мыслить как участник. То есть как участник реагирует на события
Один зелёный
Вот на рисунке снизу представлена их 1-я встреча. Теперь рассмотрим поведения участников:
- Зелёный: перед ним только красные. Но так как он знает, что среди них есть только один зелёный, то значит он им и является.
- Красные: емае, передо мной сидит один зелёеный. Значит уже не факт, что я красный. Посмотрю чо будет потом
Вот наш единственный зелёный уходит и тут начинается самое интересное. Как же нашим красным понять? Оказывается, факт того, что зелёный, ушёл сразу даёт им понять, что каждый из них красный!
- Красные: На следующий вечер их на одного чела меньше. А ушёл именно зелёный. И тут они думают, почему же он ушёл в первую же ночь? "Значит он ушёл с твёрдой уверенностью, что он зелёный. Если бы я был зелёным, то он бы перед собой в 1-й вечер тоже увидел бы 1-го зелёного и значит не был бы уверен, что он зелёный. Получается, что я красный:(((("
В итоге, красные поняли, что они красные и просто сидят не рыпаются, пока их не спасут.
Применим ту же логику для остальных случаев
Два зелёных и больше
Рассмотрим случай, когда зелёных два. Если разберём его, то будет понятно как действовать в таком случае. Как же мыслят наши рябзи
- Красные: Ой-ёй, два зелёных, посмотрим, что будет дальше
- Зелёные: Ой-ёй, один зелёный, посмотрим, как он себя поведёт.
На следующий вечер:
- Зелёные: "Такс, этот один зелёный-остался на месте. Если бы я был красным, то он бы сразу ушёл, так как вокруг него одни красный(случай одного зелёного). Значит зелёных два, а так как я вижу только одного, то получается, что второй зелёный-я"
- Красные: "Такс, два зелёных остались на месте. Посмотрим чо дальше"
В итоге, наши зелёные поняли, что они зелёные, то они уходят этой ночью. Так как на следующий вечер наши зелёные ушли, то наши красные думают:
Красные: "Такс, двое зелёных ушли. Если бы я был красным, то мысля, как зелёный, догадался бы, что я зелёный. Если я зелёный, то они бы не догадались, что они зелёные проводя те жи рассуждения. Значит, я красный("
То есть стратегия каждого участника такова: он предугадывает поведение других жертв в зависимости от того, какого он цвета. Как бы это на 1-й взгляд, не показалось странным, но поведение зелёных напрямую зависит от вашего цвета.
Разберём на всякий случай ещё случай с 3-мя зелёными и сможет чётко сформулировать стратегию каждой жертвы
Если зелёных три, то это значит, что во 2-ю ночь они не уйдут, так как не будут уверены.
Зелёный: "Такс, я вижу перед собой двоих зелёных и они не ушли во вторую ночь. Если бы я был красным, то их было бы только двое и продумав случай для двух зелёных понял бы, что они должны были бы уйти во 2-ю ночь. Значит я зелёный"
Ну, красные дальше уж поймут, что они красные.
Стратегия
Разобрав подробно случаи с одним, двумя, тремя зелёными можем описать стратегию участников, которая обобщается на неограниченное кол-во участников:
Допустим вы видите перед собой n зелёных, то я жду n ночей:
Если они ушли в n-ю ночь, то значит, что я красный
Если они остались-то я зелёный
Вся суть, повторюсь, заключается в том, что мы моделируем поведение зелёных в двух вариантах: предполагая, что ты зелёный и предполагая, что я красный. Дальше мы сверяем обе наши модели поведения с действительной ситуацией и исходя из этого понимаем, кто мы есть на самом деле
Главное, чтобы никто из участников не тормозил! Вот мы и надурили нашего сельского маньяка.
Не думайте, что это какая-то абстрактная задача. Такие ситуации постоянно встречаются в жизни, когда вам приходиться принимать решения исходя из поведения других участников, которое зависит от вашего положения. Всякие финансовые рынки, ваша любимая политота-всё это строиться на подобных моделях. Допустим, принятие нового закона в думе или какие-нибудь крупные сделки с партнёрами в банке. О подобных играх я расскажу позже в другой статье.