Zadanie
Kamilka už dojedla obed, ale musí ešte čakať, kým pani učiteľka donúti Jurka aspoň čosi zjesť. Našťastie si na jedálenskom obruse našla štvorčekovú mriežku rozmerov \(2 \times 13\). Zobrala si svojich \(13\) lístkov na obed s číslami \(1,\, 2,\, \dots,\, 13\) a uložila ich do spodného riadku mriežky v tom istom poradí, na každé políčko práve jeden lístok. Potom začala lístky presúvať. V jednom ťahu môže presunúť lístok do niektorého vedľajšieho prázdneho políčka (hore, vľavo, vpravo alebo dole). Koľko najmenej ťahov potrebuje Kamilka spraviť, aby sa všetky lístky nachádzali v spodnom riadku a v opačnom poradí (\(13,\, 12,\, \dots,\, 1\))?
V úlohách ako je táto sa riešenie zvyčajne rozdeľuje na dve časti: je potrebné ukázať, ako úlohu čo najefektívnejšie riešiť, a čo je nemenej podstatné – aj to, že to už lepšie nejde. Prípadne naopak: najprv ukázať, že lepšie úloha riešiť nejde, a potom ukázať svoje riešenie. My začneme tým, že si minimálny počet ťahov zdola ohraničíme.
Na to, aby sme posunuli lístok číslo \(13\) na správnu pozíciu, teda na pozíciu číslo \(1\), potrebujeme určite minimálne \(12\) ťahov, pretože ho potrebujeme posunúť minimálne \(12\)-krát doľava. Podobne potrebujeme \(12\) ťahov aj pre posun lístka číslo \(1\) na pozíciu číslo \(13\). Ak sa takto pozrieme na všetky lístky, zistíme, že na takéto posúvanie v riadku potrebujeme aspoň \(12+12+10+10+8+8+6+6+4+2+2+0 = 84\) ťahov.
Lenže podľa zadania na jednom políčku nesmú byť naraz dva lístky, čo znamená, že budeme potrebovať aj nejaké ďalšie ťahy na to, aby sa lístky obišli. Koľko takých ťahov potrebujeme? Vieme, že v každej dvojici lístkov sa poradie v riadku zmení, teda ak na začiatku bol jeden lístok naľavo od toho druhého, teraz bude napravo. To znamená, že nemôže existovať dvojica lístkov, ktoré sa navzájom nevyhnú, teda existuje maximálne jeden lístok, ktorý nespraví žiadny ťah nahor. Z toho vyplýva, že \(12\) lístkov takýto pohyb urobí. Samozrejme, ak sa raz lístok pohne hore, tak sa niekedy musí aj vrátiť, takže spraví v konečnom dôsledku dva ťahy. Celkovo nám teda k \(84\) ťahom v riadku pribudne ešte aspoň \(12 \cdot 2 = 24\) ťahov, čím si minimálny počet ťahov určíme na \(108\).
Ukážme si teraz, ako možno úlohu vyriešiť pre počet ťahov \(108\): Najprv posunieme všetky čísla okrem \(1\)-ky o riadok vyššie – \(12\) ťahov. Potom \(1\)-ku presunieme na pozíciu číslo \(13\) – \(12\) ťahov. Následne začneme každý z lístkov v poradí od \(2\) po \(13\) umiestňovať na svoju pozíciu. Pre lístky s číslom \(2\) až \(6\) to budú len pohyby dole a vpravo, \(7\)-ka sa posunie len dole a pre lístky s číslom \(8\) až \(13\) to budú pohyby vľavo a dole. Môžeme si všimnúť, že okrem \(1\)-ky spraví každý lístok presne \(1\) pohyb nahor, \(1\) pohyb nadol a zvyšný počet ťahov bude rovnaký ako v prvej časti riešenia, keďže sa lístky budú hýbať len jedným smerom v riadku tak, aby sa posunuli na pozíciu, kde majú byť. Celkovo teda využijeme \(12+12+(12+1)+(10+1)+\cdots +(10+1) = 108\) ťahov.
Týmto sme splnili obidve potrebné podmienky na to, aby sme dostali riešenie. Teda Kamilka musí spraviť najmenej \(108\) ťahov.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.