Układanie prostokątów

W tym artykule zastanawiamy się nad pytaniem kiedy szachownicę $\text{[math]}$ można pokryć prostokątami $\text{[math]}$ ? Naturalna próba odpowiedzi to: szachownicę można pokryć, gdy $\text{[math]}$ dzieli długość któregoś z boków, czyli gdy $\text{[math]}$ lub $\text{[math]}$ Jasne jest, że w tym przypadku faktycznie można pokryć szachownicę. Ale czy są inne przypadki, w których istnieje pokrycie?

Jeżeli $\text{[math]}$ jest liczbą pierwszą, to łatwo zauważyć, że nie: jeżeli duży prostokąt jest pokryty prostokątami $\text{[math]}$ to $\text{[math]}$ dzieli jego pole, które jest równe $\text{[math]}$ Skoro $\text{[math]}$ jest pierwsza, to $\text{[math]}$ lub $\text{[math]}$

W przypadku, gdy $\text{[math]}$ nie jest pierwsza, sprawa nie jest taka prosta. Istnieje sporo klasycznych zadań z tej problematyki, dotyczących szczególnych przypadków tego pytania (patrz np. deltoid 4/2010). Okazuje się, że łatwiej dojść do rozwiązania, gdy potraktuje się problem ogólnie. Kluczem jest, jak we wspomnianym deltoidze, metoda kolorowania.

Pokolorujmy kolejne przekątne szachownicy $\text{[math]}$ kolorami (na rysunku 1 mamy $\text{[math]}$ ). Do dalszych rozważań potrzeba nam nieco oznaczeń i obserwacji. W większości przypadków znacznie łatwiej przekonać się o prawdziwości podanych stwierdzeń, np. patrząc na rysunek, niż porządnie opisać dowód, zatem uzupełnienie uzasadnień pozostawiamy Czytelnikowi.

1. Pola o tym samym kolorze leżące w tym samym rzędzie lub kolumnie są oddalone o dokładnie

\text{[math]}

Wynika stąd kluczowy wniosek: każdy prostokąt $\text{[math]}$ zakrywa dokładnie jedno pole każdego koloru.

2. Mówimy, że rząd ma kolor

\text{[math]}

jeżeli zaczyna się od pola koloru

\text{[math]}

3. Jeżeli

\text{[math]}

nie dzieli

\text{[math]}

to rzędów niektórych kolorów jest o jeden więcej, niż rzędów pozostałych kolorów. Te kolory nazywamy częstymi. Pozostałe kolory nazywamy nieczęstymi. Na rysunku 1 czerwony i jasnoszary są częste, a pozostałe nieczęste. Jeżeli

\text{[math]}

dzieli

\text{[math]}

to wszystkie kolory nazywamy częstymi.

4. Jeżeli jest dokładnie

\text{[math]}

kolorów częstych, to

\text{[math]}

daje resztę

\text{[math]}

z dzielenia przez

\text{[math]}

5. Kolorowanie pozwala rozróżniać rzędy. Jeżeli

\text{[math]}

nie dzieli

\text{[math]}

a rząd

\text{[math]}

i rząd

\text{[math]}

mają różne kolory, to istnieje taki kolor

\text{[math]}

że liczba pól pokolorowanych na

\text{[math]}

jest różna w

\text{[math]}

\text{[math]}

6. Przemalowywanie. Wybierzmy dwa kolory

\text{[math]}

\text{[math]}

i przemalujmy każdy rząd koloru

\text{[math]}

na rząd koloru

\text{[math]}

i odwrotnie. Na rysunku 2 rzędy czerwone przemalowano na ciemnoszare i odwrotnie. Następująca obserwacja jest kluczowa:
po przemalowaniu każdy prostokąt $\text{[math]}$ zakrywa dokładnie jedno pole każdego koloru.

Oczywiście, wszystkie powyższe obserwacje przenoszą się na kolumny - wystarczy zamienić $\text{[math]}$ z $\text{[math]}$ w sformułowaniach powyżej.

Możemy już przejść do rozwiązania naszego problemu.

Zadanie 1. Kiedy szachownicę $\text{[math]}$ można pokryć prostokątami $\text{[math]}$

Dowód. Wiemy, że jeśli $\text{[math]}$ lub $\text{[math]}$ to pokrycie istnieje. Wykażemy, że zachodzi również implikacja odwrotna: jeżeli istnieje pokrycie, to $\text{[math]}$ lub $\text{[math]}$

Załóżmy, że szachownicę $\text{[math]}$ można pokryć prostokątami $\text{[math]}$ oraz liczba $\text{[math]}$ nie dzieli ani $\text{[math]}$ ani $\text{[math]}$ Pokolorujmy szachownicę $\text{[math]}$ kolorami, podobnie jak na rysunku 1. Z obserwacji 1 wynika, że pól każdego koloru jest tyle samo.

Skoro $\text{[math]}$ nie dzieli $\text{[math]}$ to istnieje przynajmniej jeden kolor nieczęsty. Wybierzmy dowolny kolor częsty $\text{[math]}$ i dowolny kolor nieczęsty $\text{[math]}$ i przemalujmy rzędy $\text{[math]}$ na $\text{[math]}$ i odwrotnie (jak w przykładzie na rysunku 2).

Na mocy obserwacji 6 po przemalowaniu każdy prostokąt zawiera $\text{[math]}$ pól o różnych kolorach, więc pól każdego koloru jest nadal tyle samo. Z drugiej strony, ubył jeden rząd $\text{[math]}$ przybył zaś jeden rząd $\text{[math]}$ Z obserwacji 5 wynika, że liczba pól pokolorowanych na pewien kolor $\text{[math]}$ zmieniła się, zatem mamy sprzeczność.

Można zastanawiać się też, kiedy istnieje pokrycie szachownicy z wyciętymi polami: rogami, polem środkowym itp. Przyjrzyjmy się najprostszej modyfikacji zadania, czyli szachownicy z wyciętym jednym polem.

Zadanie 2. Uzasadnij, że szachownicę $\text{[math]}$ z wyciętym polem o współrzędnych $\text{[math]}$ jak na rysunku 3, można pokryć prostokątami $\text{[math]}$ wtedy i tylko wtedy, gdy zachodzi jeden z warunków:

1.: $\text{[math]}$ dzieli każdą z liczb $\text{[math]}$ $\text{[math]}$ $\text{[math]}$
2.: $\text{[math]}$ dzieli każdą z liczb $\text{[math]}$ $\text{[math]}$ $\text{[math]}$

Dowód. Jak zwykle Czytelnikowi pozostawiamy udowodnienie, że gdy któryś z warunków zachodzi, to pokrycie istnieje; prostokąty można wtedy ułożyć w cztery duże "bloki", patrz rysunek 4 dla pokrycia z $\text{[math]}$ oraz $\text{[math]}$

Załóżmy zatem, że pokrycie prostokąta istnieje. Na początek chcemy rozważyć rzędy i stwierdzić, że

liczba $\text{[math]}$ dzieli liczby $\text{[math]}$ i $\text{[math]}$ lub liczba $\text{[math]}$ dzieli liczby $\text{[math]}$ i $\text{[math]}$ .

Niech $\text{[math]}$ będzie kolorem rzędu zawierającego wycięte pole. Załóżmy, że $\text{[math]}$ jest częsty. Jeżeli istnieje inny kolor częsty $\text{[math]}$ to przemalowujemy $\text{[math]}$ na $\text{[math]}$ i $\text{[math]}$ na $\text{[math]}$ jak w obserwacji 6. Pomijając wycięte pole, przemalowanie to nie zmienia liczby pól danego koloru na szachownicy, gdyż szachownica zawiera tyle samo rzędów koloru $\text{[math]}$ i $\text{[math]}$ Skoro rzędy $\text{[math]}$ i $\text{[math]}$ są różnych kolorów, to pole w kolumnie $\text{[math]}$ miało w tych rzędach różny kolor. Wobec tego po przemalowaniu liczba pól pewnego koloru zmniejszy się o jeden.

Z drugiej strony, prostokąt pokryty był prostokątami $\text{[math]}$ więc pól każdego koloru przed i po przemalowaniu jest tyle samo: $\text{[math]}$ Zatem przemalowanie nie może zmieniać liczby pól żadnego koloru.

Sprzeczność pokazuje, że tylko kolor $\text{[math]}$ jest częsty. Z obserwacji 4 wynika, że $\text{[math]}$ Zauważmy ponadto, że $\text{[math]}$ -ty rząd ma kolor częsty, a więc kolor $\text{[math]}$ Wobec tego $\text{[math]}$ czyli $\text{[math]}$

Podobnie rozumujemy, gdy $\text{[math]}$ jest nieczęstym kolorem: stwierdzamy, że jest on jedynym nieczęstym kolorem, więc częstych kolorów jest $\text{[math]}$ stąd $\text{[math]}$ Ponadto rząd $\text{[math]}$ -ty ma kolor nieczęsty, więc $\text{[math]}$ czyli $\text{[math]}$

Popatrzmy teraz na kolumny. Podobnie jak w przypadku rzędów stwierdzamy, że

liczba $\text{[math]}$ dzieli $\text{[math]}$ i $\text{[math]}$ lub liczba $\text{[math]}$ dzieli $\text{[math]}$ i $\text{[math]}$ .

Mamy łącznie cztery możliwości: dwie na mocy rozumowania "o rzędach" i dwie "o kolumnach". Chcemy teraz wyeliminować możliwości $\text{[math]}$ i $\text{[math]}$ oraz $\text{[math]}$ i $\text{[math]}$ Załóżmy najpierw, że $\text{[math]}$ Skoro prostokąty o polu $\text{[math]}$ pokrywają szachownicę z wyciętym polem, która ma pole powierzchni $\text{[math]}$ to $\text{[math]}$ Gdyby $\text{[math]}$ i $\text{[math]}$ to $\text{[math]}$ więc $\text{[math]}$ co daje sprzeczność. Podobnie przypadek $\text{[math]}$ i $\text{[math]}$ prowadzi do sprzeczności. To kończy rozumowanie w przypadku $\text{[math]}$

Na koniec rozważmy przypadek $\text{[math]}$ i załóżmy, że $\text{[math]}$ dzieli liczby $\text{[math]}$ $\text{[math]}$ Wobec tego liczby $\text{[math]}$ i $\text{[math]}$ są nieparzyste. Nazwijmy kolor pola narożnego białym, zaś drugi kolor czarnym. Na pełnej szachownicy o nieparzystych długościach boków pól białych jest więcej niż czarnych. Zatem, jeżeli istnieje pokrycie szachownicy z wyciętym polem $\text{[math]}$ to pole to ma kolor biały. To znaczy, że $\text{[math]}$ i otrzymujemy sprzeczność z podzielnościami $\text{[math]}$ oraz $\text{[math]}$ To samo rozumowanie eliminuje przypadek, gdy $\text{[math]}$ dzieli liczby $\text{[math]}$ $\text{[math]}$

Jak widać, przedstawiona metoda jest ogólna, w tym znaczeniu, że przy odrobinie czasu i cierpliwości można ją zastosować, na przykład, do szachownicy z rozsądną liczbą wyciętych pól. Na zachętę pozostawiamy Czytelnikowi kilka problemów.

Zadanie 3. Uzasadnić, że jeżeli $\text{[math]}$ to szachownicę $\text{[math]}$ z usuniętymi dwoma przeciwległymi rogami można pokryć prostokątami $\text{[math]}$ wtedy i tylko wtedy, gdy $\text{[math]}$ dzieli każdą z liczb $\text{[math]}$ $\text{[math]}$ lub $\text{[math]}$ dzieli każdą z liczb $\text{[math]}$ $\text{[math]}$ Wskazówka

Zadanie 4. Dla których całkowitych $\text{[math]}$ szachownicę $\text{[math]}$ z wyciętym środkowym polem można pokryć prostokątami $\text{[math]}$ Wskazówka

Zadanie 5. Dla których całkowitych $\text{[math]}$ szachownicę $\text{[math]}$ z wyciętym narożnym polem można pokryć prostokątami $\text{[math]}$ Wskazówka