šifra: Vlak

Nápověda

• Tajenka začíná "JDINA". Jednou za 30 minut se můžete zeptat orga sedícího v La Gambě, kde je ve vašem řešení logická chyba.

Postup řešení

Šifra vypadá jako počítačová hra Vlak, můžeme si tedy zkusit představit, jak bychom asi mapu projeli, pokud bychom skutečně hráli Vlak. Poměrně rychle bychom měli dojít ke 2 závěrům:
Jelikož mapa nevypadá příliš prostorně, pravděpodobně vezmeme většinu předmětů z posledních dvou řádků až úplně na konci těsně před výjezdem z mapy.
Předmětů je stejně jako políček v posledních dvou řádcích.
Mohli bychom tedy nějak projet celou mapu a na konci přečíst tajenku v posledních dvou řádcích, nicméně to by vyžadovalo, aby byl průjezd mapou jednoznačný a to zjevně není – dort v malé místnosti 2×2 budeme muset vzít nejpozději jako druhý a cestou k němu je zjevně jedno, zda vezmeme zmrzlinu, nebo žirafu. Tato nejednoznačnost, společně s obrázkem xylofonu, který není z originální hry, by nás měla vést na myšlenku, že jsou důležitá jen první písmena obrázků. To je z šifrovací části šifry v podstatě vše, nyní přichází na řadu logická úloha, jak projet celou mapu, pobrat všechny předměty a nikdy do sebe nenarazit. Tato úloha má (až na zmíněnou nejednoznačnost u 2 předmětů, které mají stejné první písmeno, která se v šifře objeví hned na 6 místech) skutečně jediné řešení (důkaz viz níže), které nás vede na tajenku “JDI NA NAM SNP HESLO VLNA”.
Pojmenování všech předmětů (po řádcích v zadání):
Slon, koruna, strom, kráva, diamant, auto, letadlo, žirafa, jablko, balónek, xylofon, dort, třešně, počítač, zmrzlina, peníze, rybník, budík, víno.
Důkaz jednoznačnosti řešení:
Lemma:
Pokud obarvíme jednotlivá políčka jako na šachovnici, zřejmě vlak každým svým pohybem změní barvu políčka. Má-li se tedy vlak vytočit v místnosti o obsahu k světlých a l tmavých políček (stručně k+l), musí mít délku nejvýš 2*min(k, l) – 1, tj. sebrat nejvýš 2*min(k, l) – 2 věcí. Tedy aby se vlak vytočil v obdélníkové místnosti o obsahu n, musí sebrat nejvýš n – 2 věcí pro sudé n
a dokonce nejvýš n – 3 věcí pro liché n.
V důkazu používáme několik zkratek. (x) znamená, že se bavíme o předmětu, který je v přiložené bitmapě označen číslem x. Tato čísla znamenají pořadí ze správného řešení, pokud tedy píšeme “tím jsme dokázali (x)”, je tím myšleno, že jsme dokázali, že tento předmět musí být ve správném řešení sebrán jako x-tý. Pokud píšeme, že nějaká místnost má obsah “x+y”, je tím myšleno, že pokud bychom ji obarvili jako šachovnici, budeme mít x černých a y bílých políček (nebo naopak), a tedy se odvoláme na Lemma, které říká, že při odjezdu z takové místnosti jsme mohli sebrat nejvýše 2*min(x, y) – 2 předmětů.
(2) je v místnosti 2*2, z čehož plyne horní odhad.
Navíc po cestě k (2) je nutné sebrat (1) nebo (32) (BÚNO to první), což dokazuje (1) a (2).
(7,8) jsou v místnosti 5*2, z čehož plyne horní odhad (BÚNO koruna je 7). Podobně horní odhad pro (9) – pro spor kdyby (9) byl sebrán později, pak pokud vlak přijíždí zespodu, už se nemá kde vytočit, a nemohl přijet zprava, protože se svými předpokládanými aspoň 9 předměty by se tam nevytočil.
Část obsahující předměty (5,6,10..17) označme [A].
Dokážeme nyní pro všechny tyto předměty horní odhad 17. (11,12) jsou v místnosti 5*3, z čehož plyne horní odhad (BÚNO drahokam je 11). Jelikož toto je největší místnost v [A], stejnou
argumentací jako pro (9) dostáváme horní odhad pro (13) a (14) ((6) musel být sebrán už po cestě tam), a kdyby měl některý z předmětů (5,10,15,16,17) být sebrán jako aspoň 18., musel
by vlak při jednom průjezdu vzít aspoň 4 z (5,10,15,16,17), což při předpokládané délce (aspoň 14 předmětů před sebráním oněch 4) zřejmě není možné.
Máme tedy horní odhad 17 pro všechny předměty z [A], což dohromady s (1,2,7,8,9) dává 15 předmětů s horním odhadem 17.
Část obsahující předměty (18..22,25,26,29..31) označme [B].
Jelikož vstup do [B] implikuje sebrání aspoň 3 předmětů, musí nastat až po sebrání oněch 15 předmětů s horním odhadem 17. To už tedy bude vlak mít takovou délku, že při průjezdu částí [B] (ať už zleva doprava, nebo naopak) vezme nejvýš jeden z (20,25,31).
Vlak tedy musí projet částí [B] aspoň 3x (a jelikož začíná i musí skončit vlevo, tak dokonce aspoň 4x). Po druhém průjezdu (tj. prvním návratu vlevo) tak má aspoň 18 předmětů, a může se tak vytočit jedině úplně dole, kde navíc musí sebrat aspoň 2 předměty.
Zřejmě před posledním vjezdem do části [B] v ní vlak musel sebrat aspoň 7 předmětů (lze nechat nejvýš 3 předměty sebratelné posledním průjezdem), což znamená, že těsně před posledním vjezdem do [B] má vlak (spolu s (27,28)) aspoň 26 předmětů. Navíc (27,28) jsou v místnosti o obsahu 15+19, z čehož plyne horní odhad 2*15-2=28.
(4,33..35) nelze vzít jedním průjezdem, aspoň jeden z nich tedy musí být sebrán dřív. Předpokládejme nyní pro spor, že při tom vlak sebral aspoň 3 předměty z (3,4,33..36). Pak to tedy muselo být až po všech průjezdech místností [B] (jinak by měl vlak při posledním
vjezdu do [B] aspoň 29 předmětů, a nemohl se tak vytočit). Po sebrání oněch 3 předmětů má tedy vlak aspoň 29 předmětů a může prodloužit svůj život už jedině tím, že se vytočí úplně dole, ale po návratu pro to, co zbývá z (4,33..35), už se nemá kde vytočit.
Z (3,4,33..36) tak napoprvé musely být sebrány nejvýš 2 předměty. Zřejmě jedním musí být (3) nebo (36) a z (4,33..35) lze samostatně sebrat jen (4). Sebrat (36) a (4) by šlo, jen kdyby to byly první dva sebrané předměty, což už víme, že nelze. Musí to tedy být (3) a (4), navíc tyto předměty jsou v pomyslné místnosti 3*2, z čehož plyne horní odhad, a tak máme (3) a (4) dokázáno.
Co tedy nyní víme: Máme dokázáno (1..4), horní odhad pro (7..9) a horní odhad 17 pro (1..17). Jakmile tedy vlak sebere v [A] aspoň 3 předměty, musí už sebrat vše v [A], jinak by se neměl vně [A] kde vytočit. Na druhou stranu při vjezdu do [A] má vlak aspoň 4 předměty a
s takovou délkou zřejmě nelze vzít (5,10,15..17) na dva průjezdy. Vlak tedy musí vjet do [A] před (7..9) a sebrat tam nejvýš dva předměty.
Kdyby sebral dva z (5,10,15..17), pak už se bez sebrání dalšího předmětu v [A] nevytočí. Musí tedy sebrat jen jeden z (5,10,15..17), a to tedy nutně (5) nebo (10) (BÚNO 5), a poté se vytočit při sebrání (14) nebo (6) (již potřebuje místnost s obsahem větším než 6). Pak musí jet pro (7..9) a následně se vrátit do [A] a sebrat tam vše. Před vstupem k (11,12) tak smí sebrat jen jeden další předmět a to musí být (10) (z (10,15..17) je (10) jediný předmět, který lze vzít samostatně; pokud vlak sebral (10) místo (5), pak obdobně nyní musí sebrat (5), jelikož z (5,15..17) je (15..17) jediná trojice sebratelná na jeden průjezd).
Vlak tedy při předchozím otočení v [A] musel sebrat (6), a ne (14), jinak by musel sebrat (6) nyní. Pak tedy vlak musí sebrat (11..17) a zřejmě (až na prohození 11,12) to musí být přesně v tomto pořadí. Máme tedy dokázáno (1..17).
Nyní se tedy musí stát, že vlak vjede do [B], vpravo se vytočí, vrátí se do [B], úplně dole se vytočí, opět vjede do [B], vpravo se vytočí a vrátí se do [B]. Jelikož při vytočení dole vezme aspoň 2 předměty, může před posledním vjezdem do [B] mít z [B] sebráno nejvýš 7 předmětů
(jinak by se vpravo nevytočil). Aspoň 3 předměty z [B] tedy musí být sebrány až při posledním průjezdu, a jediná možnost je (29..31). Vlak tedy při prvním vjedzu do [B] sebere aspoň 5 předmětů. Aby se vytočil úplně dole a sebral přitom jen 2 předměty, nesmí už nic dalšího vzít. To tedy dokazuje horní odhad 24 pro (18..24). Navíc aby se vytočil vpravo, aniž by sebral (27) nebo (28), musí mít nejvýš 22 předmětů (obsah místnosti bez nenavštívitelných políček
je 12+14), což dokazuje (18..22). Jediné místo, kde se vlak může dole vytočit při sebrání jen 2 předmětů, je sebráním (23) a (24) (BÚNO balonek je 23). Již víme, že před posledním vjezdem do [B] (zprava) musí být sebráno (25..28) a po sebrání kteréhokoli předmětu už vlak nemá kde se dole vytočit, aniž by sebral další předmět, což dokazuje (25..28) (BÚNO 27 je slon). Nutnost sebrat (29..40) přesně v tomto pořadí je již zřejmá.

Řešení

• JDI NA NAM SNP HESLO VLNA