У канцы кнігі "Гары Потэр і філасофскі камень" ёсць цікавая загадка. Гары і Герміёна ўваходзяць у пакой, пасля чаго ўваходы ў яе блакуе чароўны агонь, і выйсці з яе яны змогуць, толькі вырашыўшы наступную загадку:
Перад табой - небяспека, а ззаду - выратаванне,
Дапамогуць табе двое, каго знойдзеш сярод нас;
З адной з семярых наперад працягнеш ты рух
Другая ж назад цябе перанясе адразу.
У дваіх з нас знойдзеш ты толькі крапіўнае віно,
А тры нясуць пагібель, стаяць у шэрагу ўпотай.
Дык выбірай жа, з якой пакаштаваць наканавана,
Для гэтага чатыры падказкі мы даем.
Дарэмна яд спрабаваў схаваць свой смяротны жар,
Заўсёды яго знойдзеш ты налева ад віна,
І ведай, што тыя, хто па краях, розны трымаюць дар,
Але калі хочаш далей, не дапаможа ніводная.
Рознімся мы памерам усё, ад краю і да краю,
Сядзіць не ў меншай смерць твая, але і не ў большай таксама;
Другая з правага канца і з левага другая
Па гусце - нібы двайняты, хоць з выгляду непадобныя.
[з «народнага перакладу» кнігі «Гары Потэр і філасофскі камень»]
Прасцей кажучы, ім трэба зразумець, у якіх бутэльках знаходзяцца якія зеллі.
У гэтым артыкуле мы вырашым усе 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