Szachownica z usunietym 1 polem, pokrycie "triminami"/"L"

__m_qq · Post autor: **__m_qq** » 23 kwie 2009, o 17:33

Czesc,

prosilbym o pomoc, mam problem z jakas sensowna reprezentacja matematyczna tego cuda - moj sposob wymaga dosc duzej dozy machania rekami i... sami wiecie

W szachownicy o wymiarach \(\displaystyle{ 2^{n} \times2^{n}}\) usuwamy jedno dowolne pole. Wykaz ze pozostale pole mozna pokryc tryminami (kostki zlozone z 3 kwadratow, w ksztalcie rownoramiennej litery L)

Z gory dzieki

wilk · Post autor: **wilk** » 23 kwie 2009, o 18:02

według mnie na pierwszym miejscu trzeba sprawdzić że 2 przystaje do -1 mod 3
więc każda potega do jedynki lub minus jedynki. ale w jednym jak i w drugim przypadku iloczyn takich liczb przystaje do 1 mod 3. więc po usunięci jednej będzie liczba pozostałych podzielna przez 3. a następnie rozpatrzeć trzy przypadki gdy wyjmujemy z narożnika przy ściance i z wewnętrznej części. Uważam że po rozpatrzeniu tych przypadków można utworzyć prostkąty z tych liter L i będzie git:D
ale to tylko propozycja ...

Rodis · Post autor: **Rodis** » 28 kwie 2009, o 00:00

Najpierw inna rzecz:
Jak mamy już kwadrat \(\displaystyle{ 2^n \times 2^n}\) to jak można go uzupełnić do kwadratu \(\displaystyle{ 2^{n+1} \times 2^{n+1}}\) :
(wszystko z dokładnością do ćwiartki, w której jest nasz już uzupełniony kwadrat)
Wklejamy L-kę w środek (tak, aby zahaczał o pozostałe 3 ćwiartki). Uzupełniamy to kwadratami o wymiarach \(\displaystyle{ 2^n \times 2^n}\), które mają "puste" pole w narożnikach (to puste pole dopasowujemy do "wklejonego" L. W ten sposób pokrywamy coraz to większe i większe kwadraty.

Dzielimy sobie nasz kwadrat rekurencyjnie na coraz to 4 mniejsze równe kwadraty, w kolejnym kroku bierzemy ten kwadrat, w którym jest nasz puste (usunięte) pole, aż dojdziemy do kwadratu \(\displaystyle{ 2 \times 2}\). Wtedy dopełniamy nasz kwadrat L-ką. Teraz można zastosować uzupełniać kolejne pola kwadratu wg ww. algorytmu.