Mathematicator
Ú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.
Autor: Zbyněk K. | Poslední aktivita: 13. 10. 2018 13:18 | Zobrazeno 123x
ikonka Tomáš B. | 13. 10. 2018 13:18

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é.


Tento příspěvek byl editován |
Co si o tom myslíte vy?
Názory mohou psát jen přihlášení uživatelé. Pokud chcete napsat svůj názor, tak se prosím přihlašte z hlavní strany webu.

Mathematicator 2018 | Provozuje Marek Valášek | Technicky zajišťuje Jan Barášek | Obchodní podmínky | Ochrana soukromí