Zadania 2. zimného kola - Ahojte, Rieškari! Prvé zimné kolo máme úspešne za sebou. Čaká nás teda druhé kolo a s ním aj pokračovanie príbehu! Úlohy môžete nájsť tu a máte na ne čas do … Prejsť na článok
×8. príklad - Vzorové riešenie
Zadanie
Magická kocka má rozmery 3 \times 3 \times 3 a je zlepená z 27 jednotkových kociek.
Viktor z nej chce odstrániť čo najviac malých kociek tak, aby zostávajúce kocky spĺňali obe podmienky:
- Pri pohľade z každej zo šiestich strán zostane celý štvorec 3 \times 3 bez ľubovoľnej diery cez ktorú by bolo vidieť skrz kocku.
- Zvyšné kocky tvoria jeden súvislý kus, pričom dve kocky považujeme za spojené iba vtedy, ak sa dotýkajú celou stenou.
Koľko malých kociek môže Viktor najviac odstrániť?
Dokážte, že viac odstrániť nemôže, a ukážte rozloženie, pri ktorom sa tento počet dosiahne.
Vzorové riešenie
V tomto príklade sa nám naskytli dve rôzne výzvy. Prvá z nich bola ukázať a dokázať nejakú spodnú hranicu pre počet kociek, ktoré mohli vo veľkej kocke zostať. Potom sa pokúsiť pre túto spodnú hranicu nájsť nejakú konštrukciu.
V zásade by sme vedeli proces obrátiť, teda najprv nájsť nejaké rozpoloženie malých kociek a potom dokázať, že je optimálne. Ja však začnem s tým, že ukážem, koľko najmenej malých kociek muselo vo veľkej kocke byť.
V tomto príklade sa dá veľmi pekne využiť technika zvaná počítanie dvoma spôsobmi. Ide o kombinatorickú techniku, kde sa na počet nejakej veci pozrieme z dvoch uhlov pohľadu. V tomto konkrétnom príklade to bude počet viditeľných stien (malých kociek).
Vieme, že veľká kocka musí mať pri pohľade z každej strany viditeľných práve 9 stien malých kociek.
Veľká kocka má 6 strán, a teda viditeľných stien malých kociek musí byť aspoň 6 * 9 = 54.
Teraz sa na počet viditeľných kociek pozriem z iného uhla pohľadu. Opýtam sa: Koľko malých kociek musí určite existovať, aby som mal 54 viditeľných stien a malé kocky boli zároveň súvislé?
Toto sa dá spočítať niekoľko spôsobmi, nasledovný mi však príde najjednoduchší. Predstavme si, že máme k kociek a postupne z nich staváme finálny útvar tak, že po jednom kocky lepíme na už existujúcu štruktúru (aby bola súvislá). Prvá kocka nám pridá 6 viditeľných stien. Každá ďalšia kocka nám pridá maximálne 4 viditeľné steny, pretože najprv pridáme 6 viditeľných stien, ale potom ďalšie 2 zakryjeme, pretože ich na seba "nalepíme".
Teda každý súvislý útvar skladajúci sa z k kociek bude mať maximálne 6 + (k-1)*4 stien, čo sa dá napísať aj ako 4*k + 2 stien.
Pre dolný odhad kociek v našej 3 \times3 \times3 kocke chceme teda vedieť, aké je najmenšie také k, že 54 \leq k*4 +2. Po chvíle skúšania vieme dosadiť k = 13 a zistíme, že 13 * 4 +2 = 54. To znamená, že malých kociek musí byť vo veľkej kocke najmenej 13.
No, a veľa z vás už vie, že takúto konštrukciu ide spraviť, a teda musí byť optimálna. Tu je jedna možná konštrukcia v troch vrstvách:
Čo nám mohlo pomôcť pri hľadaní je aj fakt, že keďže je nerovnosť na počet viditeľných stien tesná (teda pre 13 kociek je viditeľných najviac 54 stien, a aspoň 54 stien viditeľných byť musí), musí byť každá stena malej kocky viditeľná z niektorého uhla pohľadu veľkej kocky.