1. Práca v továrni dláždení

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Michalovi Žabovi Anderlemu na [email protected]

V školskom bufete opäť dvihli ceny a vreckové vám nestačí ani na kúpu vašej obľúbenej sladkej maškrty. Nadišiel čas nájsť si brigádu! Pozreli ste si teda inzeráty v novinách a zaujala vás ponuka v “Továrni dláždení” – mzda slušná, podmienky prijateľné a riešenie PRASKu výhodou. Po krátkom pohovore ste boli razom prijatí.

Postavili ste sa k pásu, poblíž boli štyri škatule, v každej bolo neobmedzene veľa dlaždíc veľkostí \(1 \times 1\), \(2 \times 2\), \(3 \times 3\) a \(4 \times 4\). Asi ich budete baliť do menších zásielok… Po páse k vám však prišla iba obálka s listom, na ktorom bola napísaná nasledovná otázka: “Koľko existuje rôznych dláždení plochy \(4 \times 3\) pomocou dlaždíc \(1 \times 1\), \(2 \times 2\), \(3 \times 3\) a \(4 \times 4\)?”

Ostali ste zaskočení, pokrčili ste však plecami nad touto zvláštnosťou¹ a pustili ste sa do práce. Rýchlo ste zistili, že hľadanou odpoveďou je 13. Na obrázku nižšie si môžete pozrieť štyri z týchto možností, zvyšné si môžete nakresliť sami. Na list ste teda napísali odpoveď, poslali ste ho ďalej a čakali na ďalšiu požiadavku.

Po prvom dni vám bolo jasné, že cieľom továrne je odpovedať na otázky o počte rôznych dlaždení plochy \(4 \times n\), výška dotazovanej plochy je vždy 4, pomocou spomenutých štyroch typov dlaždíc.

Úloha

1. (2 body) Vypočítajte, koľko existuje rôznych možností dláždenia plochy \(4 \times 4\). Skúste stručne popísať, ako ste pri počítaní postupovali a prečo ste nevynechali žiadnu možnosť.

Pomerne rýchlo váš však táto práca omrzela a začali ste rozmýšľať, ako si ju uľahčiť. A veru ste vymysleli výborný trik. Jednoducho sa spýtate svojich kolegov! Samozrejme, nemôžete to spraviť priamo, lebo by vám určite nepomohli. Stačí ale, že spravíte list s požiadavkou a zamiešate ju medzi doručenú poštu. Potom si počkáte na odpoveď a bude. Má to však jeden háčik. Ak sa spýtate tú istú otázku ako prišla vám, bude to pôsobiť podozrivo. Pýtať sa teda môžete iba na menšie problémy.

Na riešenie zvyšných podúloh môžete využívať nasledovnú operáciu. Ak máte zistiť počet možností pre plochu \(4 \times n\), môžete sa spýtať ľubovoľne veľa otázok, ktoré sú typu “Koľko existuje rôznych dláždení plochy \(4 \times m\)?”, pričom musí platiť, že \(m\) je menšie ako \(n\). Následne predpokladajte, že na tieto otázky vám prišla správna odpoveď a takto získané odpovede môžete použiť na riešenie svojho problému.

2. (2 body) Dostali ste mierne upravenú otázku: “Koľko existuje rôznych dláždení plochy \(4 \times n\) takých, že v poslednom stĺpci sa nachádzajú iba dlaždice \(1 \times 1\)?”. Popíšte spôsob, akým zistíte odpoveď na túto otázku s využitím vyššie uvedeného triku.

3. (4 body) Popíšte postup, akým zistíte odpovede na nasledovné tri otázky:
   • Koľko existuje rôznych dláždení plochy \(4 \times n\) takých, že v poslednom stĺpci je aspoň jedna dlaždica \(2 \times 2\)?
   • Koľko existuje rôznych dláždení plochy \(4 \times n\) takých, že v poslednom stĺpci je aspoň jedna dlaždica \(3 \times 3\)?
   • Koľko existuje rôznych dláždení plochy \(4 \times n\) takých, že v poslednom stĺpci je aspoň jedna dlaždica \(4 \times 4\)?

4. (2 body) Popíšte postup, ktorý použijete na odpovedanie otázky “Koľko existuje rôznych dláždení plochy \(4 \times n\)?”.

5. (3 body) Po továrni sa rozniesol váš postup z podúlohy d), ktorý využívate na zjednodušenie práce. A samozrejme ho začali používať aj všetci vaši kolegovia. Väčšina správ v továrni je teraz od jej vlastných zamestancov. Vašou najnovšou úlohou je zistiť, koľko existuje dláždení plochy \(4 \times 7\). Nakreslite, ako bude prebiehať zisťovanie odpovede na túto otázku. Zaznačte všetky správy, ktoré bude v továrni poslané pre jej vyriešenie.

6. (2 body) Pozorne si prezrite svoj obrázok z podúlohy e). Je takýto postup efektívny? Robí sa tam niečo navyše a ak áno, ako by ste to vedeli zlepšiť.

   V továrni je okrem iného aj obrovská korková tabuľa, na ktorú sa pripínajú rôzne odkazy a momentálne je prázdna. S kolegami by ste si chceli prácu ešte viac uľahčiť. Skúste navrhnúť spôsob akým môže fungovať odpovedanie na nové otázky tak, aby nikto z vás nerobil zbytočnú robotu.