*Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Andrejovi na *

Egypťania sa tento rok rozhodli spraviť rozsiahlu rekonštrukciu pyramíd. Potrebujú preto premiestniť všetkých faraónov do jednej veľkej spoločnej pyramídy. Na samý vrch tejto pyramídy uložia ich najobľúbenejšieho faraóna a zvyšných dajú do miestností pod ním. Keďže nová pyramída ešte nestojí a my nevieme, koľko poschodí bude mať, poschodia budeme číslovať od vrchu, začínajúc poschodím číslo 1.

Ich cieľom je uložiť do tejto pyramídy čo najviac faraónov. Rozhodli sa preto, že len čo ju postavia, začnú ju zvrchu postupne napĺňať. Tu však narazili na dva problémy. Z dôvodu hmostnosti starovekých sarkofágov môžu do ktorejkoľvek miestnosti vložiť faraóna, len ak sa priamo nad ním nenachádzajú dvaja iní faraóni. Navyše faraóni sú spoločenské bytosti, preto musí priamo nad každým faraónom (s výnimkou hlavného faraóna na vrchu pyramídy) ležať aspoň jeden iný faraón.

Postup napĺňania teda vyzerá nasledovne: prechádzame postupne po poschodiach všetky izby, pričom začíname najvyšším poschodím. Ak sa priamo nad danou izbou nachádzajú dvaja faraóni, alebo tam naopak žiaden faraón nie je, izba ostane prázdna. V opačnom prípade (teda priamo nad izbou je jeden faraón) tam vložíme ďalšieho faraóna.

Na nasledujúcom obrázku je príklad pyramídy so šiestimi poschodiami, ktorá bola zaplnená práve takýmto spôsobom.

Vidíme, že v izbe 2 na 3. poschodí nie je umiestnený faraón a to preto, že obe izby nad ním sú plné. Toto nastalo aj v troch izbách na 5. poschodí. V izbe 3 na 6. poschodí taktiež nie je faraón a to preto, že mu nad ním v izbách 2 a 3 na 5. poschodí chýba spoločnosť. Toto platí aj o izbe 4 na 6. poschodí.

V izbe 2 na štvrtom poschodí však faraón je, lebo nad ním je práve jeden iný faraón (izba 1, 3. poschodie). Takisto si všimnite, že v izbe 1 je na každom poschodí faraón, lebo nad ním môže byť iba jeden faraón a ten tam vždy je.

Uvedeným spôsobom vieme vyplniť ľubovoľne veľkú pyramídu. Odporúčame vám si to vyskúšať napríklad na papier a nakresliť si, ako by vyzerala pyramída, ktorá by mala o niečo viac poschodí.

Úloha

1. (4 body) Na obrázku vyššie môžeme vidieť, že na 4. poschodí ja každá izba obsadená faraónom. Ešte pred postavením pyramídy by architektov zaujímalo, či je počet takýchto plne obsadených poschodí obmedzený alebo nie. Vyššie uvedenú pyramídu by sa totiž rozhodne neoplatilo postaviť 3 poschodovú keďže práve 4. poschodie vieme celé naplniť.

Vašou úlohou je zistiť, či sa podobný riadok v pyramíde vyskytuje aj na spodnejších poschodiach. Pre zjednodušenie si predstavte, že túto pyramídu sme postavili nekonečne vysokú. Platí, že sa tam pri plnení zhora vždy po istej dobe takéto poschodie plné faraónov znova vyskytne? Ak áno, vedeli by ste nájsť pravidlo, ktoré určí, či poschodie s poradovým číslom $x$ je práve takéto poschodie? Obe svoje tvrdenia sa pokúste dokázať.

2. (6 bodov) Akonáhle bude pyramída dostavaná, bude staviteľov zaujímať, či do konkrétnej izby majú niekoho nasťahovať alebo nie. Z tohto dôvodu si musia byť istí, že viete o každej izbe správne určiť, či bude alebo nebude obývaná. Inak vám takúto dôležitú úlohu do rúk určite nemôžu zveriť.

Vašou úlohou je zistiť, či bude izba číslo 10 na 20. poschodí obývaná alebo nie. Toto isté zistite aj o izbe číslo 266 na poschodí 276. K vašej odpovedi by ste mali napísať aj popis vášho riešenia, teda ako ste sa k tomuto výsledku dopracovali.

3. (5 bodov) Po preverení vašich schopností sa už môžete pustiť do práce. Pyramída sa medzičasom postavila a vy ste dostali za úlohu vymyslieť postup, vďaka ktorému vieme o ľubovolnej izbe povedať, či bude alebo nebude obývaná. Egypťanom však došiel papyrus a tak by boli veľmi radi, ak by ste vymysleli šetrnejší spôsob ako kreslenie si celej pyramídy.

Vašou úlohou je vymyslieť postup, ktorý určí pre ľubovolné poschodie a izbu na tomto poschodí, či v nej bude alebo nebude faraón a to v čo najmenšom počte krokov. Vzorové riešenie by bolo schopné zistiť zaplnenosť ktorejkoľvek izby aj na poschodí s číslom rádovo okolo $1\,000\,000$ (a aj omnoho viac) a to len s použitím papiera a rozumného množstva času. Upozorňujeme, že okrem vysvetlenia tohto postupu na nejakom príklade musíte uviesť jednoznačný postup, ktorý vie opravovateľ na ktoromkoľvek inom poschodí a izbe zopakovať a dopracovať sa k správnemu výsledku.