9. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Koľko najviac tetromín tvaru "S" sa zmestí do tabuľky:

  1. 5 \times 5
  2. 6 \times 6
  3. 7 \times 7

Pričom tieto tetrominá môžeme ľubovoľne otáčať a preklápať, avšak žiadne dve tetrominá sa nesmú prekrývať, vyčnievať z tabuľky a ani prekrývať necelé štvorčeky tabuľky. Tetromino "S" vyzerá nasledovne:

Vzorové riešenie

Opravovali: Danko, Tamarka_Krivosikova

a)

Keď sa snažíme dávať S tetrominá do tabuľky 5\times5​, nepodarí sa nám ich umiestniť viac ako 4. A to aj napriek tomu, že nám ešte ostali voľné políčka. Môžeme si všimnúť, že keď ľubovoľne umiestnime 4​ tetrominá, tak niektoré políčka budú vždy zabraté. Sú to tieto políčka:


​A nebola to iba náhoda. Keby sme odstránili tieto políčka, do tabuľky by sa nezmestilo ani jedno tetromino. Inak povedané, každé tetromino musí obsahovať niektoré z týchto políčok. Keďže v tabuľke 5 \times 5​​ existujú 4​ takéto políčka, môžeme tam zmestiť najviac 4​ tetrominá. To sa nám aj podarí a tabuľka môže vyzerať napríklad takto:


c)

Rovnako ako v tabuľke 5\times5​, aj v tabuľke 7\times7​ chceme nájsť čo najmenej políčok bez ktorých nedokážeme umiestniť žiadne tetromino. Keď ich nájdeme n​ tak vieme, že tetromín sa tam zmestí najviacn​. V tabuľke 7\times7​ existuje 9​ takýchto políčok (označených x). Ale ako vieme, že sa tam naozaj zmestí až 9​ tetromín? Stačí, keď nájdeme príklad umiestnenia deviatich tetromín do tabuľky. Tabuľka 7\times7​ vyplnená 9​ tetrominami môže vyzerať napríklad takto:


Vieme, že tetromín sa tam zmestí najviac 9​. Zároveň sa nám tam podarilo všetkých 9​ umiestniť. Odpoveď je teda 9​.

b)

V tabuľke ​ je 36​ políčok. Teoreticky by sa tam teda zmestilo 36:4=9​ tetromín. To by ale znamenalo, že každé políčko v tabuľke musí byť využité. To znamená, že zabraté musí byť aj políčko v ľavom hornom rohu. Umiestnime tam teda zelené tetromino. Môžeme ho umiestniť tak, aby smerovalo doprava alebo nadol. Je to ale jedno, pretože nám vznikne rovnaká situácia, iba preklopená. Tak či tak nám vznikne jedno políčko pri kraji, na ktoré vieme tetromino umiestniť iba jedným spôsobom. V našom prípade to je modré tetromino ako na obrázku. Teraz ale na políčko označené krížikom nevieme umiestniť žiadne tetromino.

Týmto sme ukázali, že keď sa snažíme pokryť všetky políčka, určite sa nám to nepodarí. To znamená, že do tabuľky 6\times6​ sa nezmestí 9​ tetromín. Najviac teda vieme umiestniť 8​ tetromín, čo môže vyzerať napríklad takto:

​

Odpoveď:

a) Do tabuľky 5\times5​ sa zmestia najviac 4​ tetrominá.

b) Do tabuľky 6\times6​ sa zmestí najviac 8​ tetromín.

c) Do tabuľky 7\times7​ sa zmestí najviac 9​ tetromín.​​