Na konci Harryho Pottera a kameňa mudrcov je zaujímavá hádanka. Harry a Hermiona vstúpia do miestnosti, potom sú vchody do nej zablokované magickým ohňom a môžu ju opustiť iba vyriešením nasledujúcej hádanky:
Pred tebou je nebezpečenstvo a za tebou spása,
Dvaja ľudia, ktorých medzi nami nájdete, vám pomôžu;
S jedným zo siedmich budete pokračovať v napredovaní
Ten druhý vás okamžite vezme späť.
V nás dvoch nájdete len žihľavové víno,
A tri prinášajú skazu, stojace v rade tajne.
Vyberte si teda, ktorý ste predurčený ochutnať,
Na tento účel uvádzame štyri tipy.
Márne sa jed snažil skryť svoje smrteľné teplo,
Vždy ho nájdeš naľavo od vína,
A vedzte, že tí na okrajoch majú iný darček,
Ale ak chcete pokračovať, nikto vám nepomôže.
Všetci sa líšime veľkosťou, od okraja po okraj,
Tvoja smrť nesedí v menšom, ale ani vo väčšom;
Druhý z pravého konca a druhý zľava
Chutia ako dvojčatá, aj keď sa na seba nepodobajú.
[z "ľudového prekladu" knihy "Harry Potter a kameň mudrcov"]
Jednoducho povedané, musia pochopiť, ktoré fľaše obsahujú ktoré elixíry.
V tomto článku vyriešime všetkých 42 možných variácií tohto hlavolamu pomocou programovania a nakreslíme diagram výsledkov (ako obrázok vyššie, len oveľa väčší).
Počkaj chvíľu, odkiaľ sa vzalo 42 možností?
Je to preto, že umiestnenie „menších“ a „väčších“ elixírov nie je uvedené. Väčší môže byť na jednom zo siedmich miest, čo dáva 6 zostávajúcich možností pre menšie, spolu 7 * 6 = 42. Nebude možné presne zistiť, aké usporiadanie mala JK Rowlingová na mysli, keď prišla s touto hádankou, pokiaľ o tom nehovorí na vašom Twitteri. Kým nepríde ten nevyhnutný deň, môžeme si vybrať náhodnú verziu a pracovať s ňou. Nebude však zaručená jeho riešiteľnosť, preto pracujeme pre spoločné dobro, vyriešením všetkých 42 variantov hádanky (resp. preukázaním ich neriešiteľnosti).
ROZHODNITE SA UŽ
Po prvé, tu sú všetky obmedzenia hádanky, zjednodušene povedané:
- Existujú dva neškodné elixíry, 3 jedovaté, jeden, ktorý vám umožní ísť vpred, a jeden, ktorý vám umožní vrátiť sa späť.
- Na ľavej strane každého z dvoch neškodných elixírov je jeden jedovatý.
- Lektvary na oboch stranách sú rozdielne a žiadny z nich vám nedovolí pohnúť sa vpred.
- Najväčšie a najmenšie fľaše neobsahujú jed.
- Druhá fľaša naľavo a druhá fľaša napravo obsahujú rovnaký elixír.
Ako sa s tým vysporiadať? Zvážme nasledujúcu možnosť. Všimnite si, že ako hovorí hádanka, v rade je 1 fľaša menšia ako všetky ostatné a 1 fľaša väčšia ako všetky ostatné.
Skúsme hlúpo prejsť všetky možnosti - vezmite si jednu fľašu naraz a vyberte všetky možné možnosti pre obsah.
Napríklad prvá fľaša nemôže obsahovať elixír, ktorý nás posúva vpred kvôli obmedzeniu č.3. Neobsahuje ani bezpečný elixír kvôli obmedzeniu č.2 – naľavo od neho nemôže byť jed. To nám ponecháva možnosti elixíru jedu a elixíru návratu. Skúsme obe možnosti.
Na nasledujúcich obrázkoch zelené elixíry predstavujú jed, oranžové sú bezpečné nápoje, modré sú elixíry, ktoré sa pohybujú dozadu, a fialové sú elixíry, ktoré sa pohybujú vpred.
Zopakujme tento postup pre obe pracovné možnosti – vezmite druhú fľašu a striedavo vyskúšajte všetky prijateľné možnosti obsahu. Získame tak nasledovné:
Ak budeme pokračovať v tomto duchu a zahodíme všetky pracovné možnosti, v ktorých niektorú fľašu nemožno naplniť elixírom bez porušenia uvedených obmedzení, dospejeme k jedinej prijateľnej možnosti:
Prirodzene, nemali sme žiadnu záruku, že nájdeme riešenie. Nemôže existovať žiadne riešenie, alebo ich môže byť niekoľko (a ak máte niekoľko riešení, je to to isté, ako keď hádanku nemožno vyriešiť, pretože neviete, ktorý elixír je správny).
Aplikovaním algoritmu na všetky možnosti získame nasledujúce riešenia. 8 verzií hádanky je riešiteľných, 8 nemá riešenia a 26 má viacero riešení.
Viac o riešeniach
Majú všetky vyriešené verzie hádanky niečo spoločné? Áno! Upozorňujeme, že v nich sú najmenšie alebo najväčšie fľaše na 2. alebo 6. mieste. To nám umožňuje dospieť k záveru, že 2. a 6. fľaša obsahuje bezpečné elixíry kvôli obmedzeniam #4 a #5. Bez tohto kroku nemôžeme vylúčiť možnosť, že tieto fľaše obsahujú jed, a tak máme niekoľko možných riešení. Tiež riešené možnosti vyžadujú, aby sa druhá „špeciálna“ fľaša (najmenšia alebo najväčšia) umiestnila na 3. alebo 4. mieste. Inak sa presné umiestnenie elixíru, ktorý nás posúva vpred, nedá nájsť.
Výsledky
Zakončím citátom z knihy.
Hermiona nahlas vydýchla a Harry si s úžasom všimol, že sa usmieva - to bolo to posledné, čo ho mohlo napadnúť. "Skvelé," povedala Hermiona. - To nie je mágia - to je logika, hádanka. Veľa najväčších kúzelníkov nemá ani štipku logiky a uviazli by tu navždy."
Ale počkajte chvíľu – možno sa nám podarí prísť na kanonickú verziu hádanky na základe dialógu z knihy:
"Rozumiem," povedala. "Najmenšia fľaša nás povedie cez čierny oheň a ku kameňu."
...
"A ktorý ti umožní vrátiť sa cez fialový oheň?"
Hermiona ukázala na okrúhlu fľašu na pravej strane radu.
Dočerta. Táto možnosť nám stále ponúka niekoľko riešení. Tweet, DR.
kód
Ak máte záujem o kód na vyriešenie tejto hádanky a nakreslenie diagramov, môžete .
Zdroj: hab.com