udowodnij szachownicę można pokryć tryminami

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
przyszly_naukowiec
Użytkownik
Użytkownik
Posty: 18
Rejestracja: 4 kwie 2010, o 16:42
Płeć: Mężczyzna
Lokalizacja: Cieszyn

udowodnij szachownicę można pokryć tryminami

Post autor: przyszly_naukowiec » 27 cze 2011, o 12:07

Witam
Próbuję rozwiązać takie zadanie:

Z szachownicy o wymiarach \(\displaystyle{ 2^{n} \times 2^{n}}\) usunięto jedno pole. Wykaż, że otrzymaną figurę można pokryć tryminami (tzn. kostkami złożonymi z trzech kwadratów, w kształcie równoramiennej elki).

To zadanie z działu "Indukcja i rekurencja". Nie mam pojęcia jak to udowodnić, więc prosiłbym o nakierowanie.
Z góry dzięki za pomoc.

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

udowodnij szachownicę można pokryć tryminami

Post autor: » 27 cze 2011, o 12:32

Dla trzech wymiarów to zadanie było kiedyś na drugim etapie Olimpiady.

Potnijmy nasz kwadrat na cztery mniejsze o wymiarach \(\displaystyle{ 2^{n-1}\times 2^{n-1}}\), w tym jeden z brakującym polem. Z założenia indukcyjnego ten z brakującym polem da się pokryć tryminami. Natomiast na trzy pozostałe połóżmy trymino w ten sposób, żeby każde pole trymina pokrywało pole innego kwadratu. W ten sposób do pokrycia pozostaną nam jeszcze trzy kwadraty \(\displaystyle{ 2^{n-1}\times 2^{n-1}}\), a to można zrobić z założenia indukcyjnego.

Q.

ODPOWIEDZ