Zadanie
Zlovestné mračná sa preháňali oblohou nad tmavým lesom. Slnko nebolo vidno, nedalo sa však povedať, či je noc, alebo deň. Temnotu preťal blesk. Na krátky moment osvietil mohutný hrad na vrchu zradného útesu. K nemu sa po úzkej cestičke približovalo malé svetielko…
Keď Sherlock s Watsonom prišli do hradnej záhrady, nad telom už stála skupinka postáv. Vo svetle lampáša rozoznali \(5\) osôb. Mŕtvolou bol hradný záhradník. Nikto z hradu od vraždy neodišiel, takže jedna z piatich osôb je vrah.
Sherlock si zapálil fajku a vypustil obláčik dymu. Ten mal tvar kocky \(n \times n \times n\), kde \(n\geq 2\). Táto kocka bola vyskladaná z kvádrikov \(1 \times 1 \times n\). Je možné, že obsahovala kvádrik otočený v každom z troch možných smerov? Svoju odpoveď zdôvodnite.
Skúsme riešenie začať čo najjednoduchšie - pozrime sa na kocku \(2\times 2 \times 2\). Skúsme do nej uložiť kvádriky tak, aby obsahovala kvádrik otočený v každom z troch možných smerov. Nakoľko sa do tejto kocky zmestia iba \(4\) kvádriky, veľa možností na ich uloženie nemáme. Uložme teda prvé tri, každý v inom smere. Rýchlo prídeme na to, že sa to dá iba jedným spôsobom (ak odhliadneme od rotácii kocky).
Isto si rýchlo všimneme aj to, že nám takto vzniknú dve \(1 \times 1 \times 1\) kocky, ktoré nevieme našimi kvádrikmi už zaplniť. A keďže neexistuje iný spôsob, ako tieto tri kvádriky uložiť, kocku \(2 \times 2 \times 2\) takýmto spôsobom vyplniť nevieme.
Poďme sa teraz pozrieť na kocky väčších rozmerov. Predstavme si, že sa kocka \(n \times n \times n\) dá vyskladať tak, že sa v nej nachádzajú kvádriky otočené všetkými troma smermi. Vyberme si z takejto kocky tri ľubovoľné kvádriky, ktoré sú otočené každý do iného z troch smerov. Situácia, ktorá nastane, je veľmi podobná situácii pri kocke \(2 \times 2 \times 2\). V kocke \(n \times n \times n\) s takto rozloženými troma kvádrikmi vieme takisto nájsť dve kocky \(1 \times 1 \times 1\), cez ktoré už žiadny kvádrik prechádzať nemôže, lebo vo všetkých troch smeroch prechádzajúcich týmito kockami narazíme na už položené kvádriky. Sú to presne tie dve kocky, ktorých projekcia vo všetkých troch smeroch pretína projekciu jedného z kvádrikov.
Ako by sme vedeli tieto dve kocky \(1 \times 1 \times 1\) nájsť? Predstavme si, že kvádriky v kocke "zhrnieme" do jedného rohu tak, že nezmeníme ich orientáciu ani poradie. Keď sa pozrieme na \(2 \times 2 \times 2\) výsek v tomto rohu, určite si všimneme, že tu presne nastáva tá istá situácia, ako pri kocke \(2 \times 2 \times 2\), a tieto dve problémové \(1 \times 1 \times 1\) kocky nájdeme ľahko. Teraz postupne posúvame kvádriky spolu s problémovými \(1 \times 1 \times 1\) kockami naspäť na ich pôvodnú pozíciu.
Pri tomto postupe sme si zvolili úplne všeobecné rozpoloženie kvádrikov v kocke. Tým pádom nezáležiac od toho, aké \(n\) zvolíme, tieto dve malé kocky by sme vedeli nájsť v hocijakej kocke \(n \times n \times n\), v ktorej sa nachádzajú tri rôzne otočené kvádriky. To nám však hovorí, že žiadnu z týchto kociek nevieme vyskladať celú tak, aby obsahovala kvádrik otočený v každom z troch možných smerov.
Poznámka
Pri riešení tejto úlohy bolo dôležité dávať pozor na všeobecnosť riešenia. Nestačí ukázať len jeden príklad rozpoloženia z jednej kocky, v ktorom to nejde. Z riešenia musí byť jasné, že takto nevieme vyskladať žiadnu kocku \(n \times n \times n\).
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ť.