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.
udowodnij szachownicę można pokryć tryminami
-
przyszly_naukowiec
- Użytkownik
- Posty: 18
- Rejestracja: 4 kwie 2010, o 16:42
- Płeć: Mężczyzna
- Lokalizacja: Cieszyn
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
udowodnij szachownicę można pokryć tryminami
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.
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.