Riešky výlet - Ahojte Rieškari, jar je v plnom prúde, vonku je pekne a my sa chystáme na výlet! Zoberte batohy, hry, frisbee, kamarátov a hlavne dobrú náladu a poďte sa s nami … Prejsť na článok
×4. príklad - Vzorové riešenie
Zadanie
Majme tabuľku rozmerov 2\times5. Existuje 5 dlaždičiek s hodnotami 1, 2, 3, 4, 5. Každá hodnota je na nejakej dlaždičke práve raz. Tieto dlaždičky uložíme do horného riadku našej tabuľky v náhodnom poradí.
Dlaždičkami môžeme po políčkach tabuľky ľubovoľne hýbať tak, že nevychádzame z tabuľky, a zároveň sa dlaždičky nikdy neprekrývaju, čiže neležia jedna na druhej. Ak pohneme dlaždičku na ľubovoľné susedné voľné políčko, nazývame to ťah.
- Dokážte, že nech dlaždičky na začiatku uložíme do tabuľky v ľubovoľnom poradí, vždy ich vieme zoradiť od najmenšej po najväčšiu tak, že najmenšia je dlaždička vľavo a najväčšia je dlaždička vpravo.
- Nech sú v tabuľke 2\times5 zoradené dlaždičky 3,5,1,4,2. Koľko najmenej ťahov potrebujeme, aby sme ich zoradili do horného riadka do poradia 1,2,3,4,5? Nezabudnite dokázať, že sa použiť menej ťahov nedá.
Vzorové riešenie
Keď sa trošku pohráme s "hlavolamom" v zadaní, zdá sa, že by nemal byť problém preusporiadať čísla akokoľvek si vymyslíme. Aby sme dokázali prvú podúlohu, bude nám stačiť vysvetliť jeden z mnohých spôsobov ako z hociakého usporiadania dostaneme zoradenie 1 2 3 4 5. Dáme ho ako návod, z ktorého bude jasne vidno, že výsledkom bude vždy správne zoradenie:
Čísla budeme umiestňovať na ich cieľové pozície postupne od najmenšieho. Zoberieme jednotku, a presunieme ju do spodného riadka. Ten je celý prázdny, takže ju môžeme posunúť pod jej cieľovú pozíciu. Ak je na tejto pozícii iné číslo, posunieme doprava všetky čísla vo vrchnom riadku ktoré môžeme. To sa dá, pretože jednotka v ňom niekde uvoľnila miesto (okrem prípadu kedy už bola na svojom mieste, vtedy nič posúvať nepotrebujeme). Máme teda voľné a môžeme jednotku dať na cieľovú pozíciu.
To isté teraz budeme robiť s ďalšími číslami. Zoberieme číslo, dáme ho pod jeho cieľovú pozíciu, uvoľníme ju posunom doprava (nie doľava lebo tam sú všetky miesta zaplnené už "vybavenými" číslami) a posunieme na cieľovú pozíciu.
Pri konkrétnom rozložení 35142 je veľa možností čo robiť, pravdepodobne sa nám pomerne ľahko podarí aj viacerými rôznymi spôsobmi popresúvať všetko na správne miesta za 16 ťahov.
Zadanie sa pýta, koľko je najmenej. Keďže lepšie sa nám nepodarilo, skúsme predpokladať že odpoveď je naozaj 16. Vyskúšame nejak dokázať, že na menej sa to nedá. Ak sa nám podarí povedať, že ťahov musí byť aspoň 16, tak máme odpoveď, lebo vieme že 16 je naozaj možné, a teda najnižšie. Alebo, ak aj nie, tak po ceste asi objavíme, čo lepšie ako 16 ťahov by sa dalo spraviť.
Skúsme začať tým, že nájdeme aspoň nejaký, kľudne aj o dosť menší počet ťahov, o ktorom vieme určite povedať že toľko potrebujeme. Predstavme si, že by každé číslo išlo priamo na svoje miesto - nemuseli by sa vôbec vyhýbať. Číslo jeden sa musí pohnúť o 2 doprava, dvojka o 3, trojka o 2, štvorka o 0, päťka o 3. Spolu je to 2+3+2+3=10 ťahov. Tým máme vybavené minimum vodorovných ťahov, no my vieme, že aby sa čísla vyhli, musia sa hýbať aj zvislo - medzi riadkami.
Poďme sa presnejšie pozrieť na to, ako to funguje. Ak sú na začiatku nejaké dve čísla v opačnom poradí ako majú byť na konci, tak jedno z nich bude musieť uhnúť do spodného riadka, lebo nemôžu prejsť cez seba. To nás stojí aspoň 2 ťahy navyše, lebo prinajlepšom pôjde (iba raz) dole a potom späť hore. Takýto prípad sú trojka a jednotka. Potom tu máme napríklad aj päťku a štvorku, a tu je to ešte zložitejšie, lebo päťka sa zároveň musí obísť aj s dvojkou a aj štvorka sa musí obísť s dvojkou. Čísla 5, 4 a 2 teda tvoria taký "trojuholník" kde každý sa musí obísť s každým. Nestačí teda, aby sa uhlo iba jedno z týchto troch čísel, lebo to by v hornom riadku boli celý čas tie zvyšné dve, ktoré sa nevedia vymeniť. Preto z tejto trojice musia ísť do dolného riadku minimálne dve. Zo zvyšných čísel, 3 a 1 musí ísť do dolného riadku jedno číslo, a každé číslo v dolnom riadku nám pridá 2 ťahy navyše. Ku pôvodným 10 ťahom na vodorovný presun teda musíme pridať minimálne 3\cdot2=6 ťahov, dva presuny pre tri rôzne čísla, a tým dostávame práve 16 ťahov.
Nemuseli sme teda podrobne preskúmať všetky dvojice ktoré sa potrebujú obísť, už len z tých čo sme tu popísali vieme, že aspoň 3 čísla musia ísť dole, a to dá dokopy minimálne 16 ťahov. A riešiť, či nebudú potrebovať náhodou ešte viac ťahov nemusíme, ak vieme nájsť nejaký príklad, kedy sa to na 16 ťahov zvládne. Napríklad to môže vyzerať takto:
Odpoveď: Čísla vieme vždy zoradiť, a v zadanom prípade na to budeme potrebovať najmenej {16} ťahov.