Úloha s šachovnicí a kostkami domina obráceně
Ve skvělém videu na youtube O matematice s docentem Mirko Rokytou byl mj. i podán důkaz, že nejde pokrýt beze zbytku šachovnici kostkami domina, pokud z ní odstraníme kterákoli dvě pole stejné barvy. Zajímalo by mne, jestli z toho lze analogicky vyvodit, že pokud z jakkoli velké šachovnice odstraníme kterákoli dvě pole odlišných barev, půjde taková šachovnice beze zbytku kostkami domina pokrýt? Nebo to tak jednoduché není...? Díky za Vaše úvahy.
Zbyněk K.
13. 10. 2018 13:18
1 odpověď
Je to docela jednoduché, protože můžeme provést redukci libovolně velké šachovnice jen na dva případy.
Šachovnice nemůže mít lichý počet sloupců a řádků (důkaz je triviální).
Bez újmy na obecnosti předpokládejme, že je počet sloupců sudý (v opačném případě ji můžu otočit).
Řekněme, že odstraním dvě pole v řadách M a N.
Část šachovnice, která není mezi M a N (včetně) dokážeme zaplnit snadno.
Takže můžeme šachovnici zmenšit a ptát se, jestli se dá zaplnit, pokud vyhodím pole pouze v horní a dolní řadě.
To stejným postupem znovu zjednodušíme, protože pokud bych dokázal vyplnit okraj šachovnice, vnitřek už zaplním snadno.
Tím se problém opět zmenší, tentokrát na případy, kdy má šachovnice jen 2 nebo 3 řady.
Dál už je to jednoduché.