Zadania 3. zimného kola - Ahojte, Rieškari! Skončilo sa nám druhé letné kolo, a teda prichádzajú zadania tretieho kola aj s pokračovaním príbehu! Môžete ich nájsť v sekcii zadania máte na nich čas do 26. … Prejsť na článok
×9. príklad - Vzorové riešenie
Zadanie
Kachličky na stene v kúpeľni boli kedysi v mriežke 5 x 5. Časom však kachličky odpadli.
Viktor a Leci sa snažili na stenu nalepiť novú vrstvu kachličiek pozostávajúcu z väčších kachličiek v tvare L, tak, aby zakryli miesta po odpadnutých kachličkách. Žiadna z týchto nových kachličiek však nemohla vyčnievať mimo 5 x 5 mriežku.
Po chvíli zistili, že ak by si vybrali niekoľko konkrétnych políčok, na ktoré by kachličky určite museli položiť, tak by stenu vykachličkovať nevedeli.
Nájdite najmenší počet políčok, ktoré si Viktor s Lecim mohli vybrať a vysvetlite, prečo si menej políčok vybrať nemohli.
Vzorové riešenie
V tomto príklade bolo pomerne náročné dobre nájsť spôsob, ako dokázať to čo chceme.
To jest, že pre nejaký počet kachličiek existuje aspoň jedno rozostavenie také, že všetky tieto políčka vykachličkovať nevieme.
Dokázať, aby tento počet kachličiek bol najmenší možný je tiež výzva. Venujme sa však nájdeniu aspoň jednej takej konfigurácie, že sa nedajú všetky políčka zakryť.
Jedna vec čo si môžeme o mriežke všimnúť je, že sa do nej zmestí najviac 8 L-dielikov. Ako to?Každý dielik zaberá 3 políčka. Keby sme chceli do mriežky napchať dielikov 9, potrebovali by sme aspoň 3\times 9 = 27 políčok.
To je viac ako 25 políčok ktoré sa v mriežke nachádzajú, takže sa to nedá.
Vieme teda prísť na nasledovnú myšlienku: ak by sme dokázali vybrať 9 nejakých políčok v mriežke tak, že žiadne dve sa nedajú zakryť jedným dielikom, vieme, že všetkých 9 políčok sa nedá zakryť.
No a takéto políčka sa naozaj vybrať dajú, a to nasledovne:
Na zakrytie týchto políčok by bolo potrebných aspoň 9 dielikov, čo vieme, že sa do mriežky nezmestí. Teraz prichádza však náročná úloha. Musíme ukázať, že vybrať 8 políčok naozaj nestačí.
Vieme použiť nasledovný argument: Vyššie sme našli prípad, kde sme vybrali 9 políčok. Ak vyberieme 8 políčok, aspoň jedno políčko z tých, ktoré sme vyššie vybrali, musí byť prázdne. No, a tvrdím, že nech je prázdne ľubovoľné políčko z tých vyššie, vieme zakryť celú mriežku okrem toho políčka. Ako?
Jedným z nasledovných spôsobov, alebo ich rotáciou:
Pre ľubovoľný menší počet vieme použiť rovnaký argument, a preto sme dokázali, že je potrebných vybrať aspoň 9 políčok.