В конце книги «Гарри Поттер и философский камень» есть интересная загадка. Гарри и Гермиона входят в комнату, после чего входы в неё блокирует волшебный огонь, и выйти из неё они смогут, только решив следующую загадку:
[из «народного перевода» книги «Гарри Поттер и философский камень»]Перед тобой — опасность, а позади — спасенье,
Помогут тебе двое, кого найдешь средь нас;
С одной из семерых вперёд продолжишь ты движенье
Другая же назад тебя перенесёт тотчас.
В двоих из нас найдёшь ты лишь крапивное вино,
А три несут погибель, стоят в ряду тайком.
Так выбирай же, из какой отведать суждено,
Для этого четыре подсказки мы даём.
Напрасно яд пытался скрыть свой смертоносный жар,
Всегда его найдёшь ты налево от вина,
И знай, что те, кто по краям, различный держат дар,
Но если хочешь дальше, не поможет ни одна.
Разнимся мы размером все, от края и до края,
Сидит не в меньшей смерть твоя, но и не в большей тоже;
Вторая с правого конца и с левого вторая
По вкусу — словно близнецы, хоть с виду непохожи.
Проще говоря, им нужно понять, в каких бутылках находятся какие зелья.
В этой статье мы решим все 42 возможных варианта этой головоломки при помощи программирования и нарисуем диаграмму результатов (как на картинке выше, только гораздо большего размера).
Секундочку, а откуда взялось 42 варианта?
Всё оттого, что местоположения «меньшего» и «большего» зелий не указаны. Большая может находиться на одном из семи мест, что даёт 6 оставшихся вариантов для меньшей, итого 7 * 6 = 42. Узнать, какую именно расстановку имела в виду Джоан Роулинг, придумывая эту загадку, не получится, если только она не расскажет об этом в своём твиттере. Ну а пока этот неотвратимый день не наступил, мы можем выбрать случайную версию и поработать с ней. Однако гарантий её решаемости не будет, поэтому мы и работаем на общее благо, решая все 42 варианта загадки (или доказывая их нерешаемость).
ДА РЕШАЙ УЖЕ
Во-первых, вот все ограничения загадки, переформулированные в простом виде:
- Есть два безобидных зелья, 3 отравленных, одно, позволяющее пройти вперёд, и одно, позволяющее вернуться назад.
- С левой стороны от каждого из двух безобидных зелий стоит ядовитое.
- Зелья с обоих краёв разные, и ни одно из них не даёт пройти вперёд.
- Самая большая и самая маленькая бутылки не содержат яда.
- Вторая бутылка слева и вторая бутылка справа содержат одно и то же зелье.
Как с этим быть? Рассмотрим следующий вариант. Отметим, что, как говорится в загадке, в ряду есть 1 бутылка меньше всех остальных по размеру, и 1 бутылка больше всех остальных.
Попробуем тупо перебрать все варианты – брать по одной бутылке и подбирать все возможные варианты содержимого.
К примеру, в первой бутылке не может содержаться зелье, продвигающее нас вперёд из-за ограничения №3. Также она не содержит безопасного зелья из-за ограничения №2 – слева от неё не может находиться отрава. Это оставляет нам варианты с отравленным зельем и зельем, возвращающим назад. Попробуем оба варианта.
В последующих изображениях зелёные зелья обозначают яд, оранжевые – безопасные напитки, синие – зелье, двигающее назад, пурпурное – двигающее вперёд.
Повторим этот процесс для обоих рабочих вариантов – возьмём вторую бутыль и попеременно попробуем все допустимые варианты содержимого. Это даст нам следующее:
Продолжая действовать в этом ключе, и отбрасывая все рабочие варианты, в которых какую-то бутыль нельзя заполнить зельем, не нарушив перечисленных ограничений, мы придём к единственному допустимому варианту:
Естественно, у нас не было гарантий найти решение. Решения могло не быть, или их могло быть несколько (а если у вас есть несколько решений, это равнозначно тому, что загадку решить нельзя, поскольку неизвестно, какое из зелий верное).
Применение алгоритма ко всем вариантам даёт нам следующие решения. 8 вариантов загадки решаемы, у 8 нет решений и у 26 есть несколько решений.
Подробнее о решениях
Есть ли что-то общее у всех решаемых вариантов загадки? Да! Обратите внимание, что в них самая маленькая или самая большая бутылки стоят на 2-м или 6-м местах. Это позволяет нам сделать вывод, что 2-я и 6-я бутылка содержат безопасные зелья из-за ограничений №4 и №5. Без этого шага мы не можем устранить возможность того, что в этих бутылках яд, и в итоге приходим к нескольким возможным решениям. Также решаемые варианты требуют, чтобы вторая «особая» бутылка (самая маленькая или самая большая) стояли на 3-м или 4-м месте. Иначе точное местоположение зелья, двигающего нас вперёд, найти не получается.
Итоги
Закончу цитатой из книги.
Гермиона с шумом выдохнула, и Гарри изумлённо заметил, что она улыбалась – это было последнее занятие, которое могло бы прийти ему в голову. «Гениально, — сказала Гермиона. – Это не магия – это логика, загадка. У множества величайших магов не наберётся и грамма логики, и они застряли бы здесь навечно».
Но, погодите-ка – может, мы сумеем понять каноническую версию загадки на основе диалога из книги:
«Поняла, — сказала она. – Самая маленькая бутылка проведёт нас через чёрный огонь, и к Камню».
…
«А какая даст тебе вернуться через пурпурный огонь?»
Гермиона указала на округлую бутыль с правой стороны ряда.
Чёрт возьми. Этот вариант всё равно даёт нам несколько решений. Пишите твиты, ДР.
Код
Если вам интересен код для решения этой загадки и рисования диаграмм, его можно .
Источник: habr.com