XXXI - I - Zadanie 10

Płaszczyzną podzielono dwiema rodzinami prostych równoległych na przystające kwadraty. jest zbiorem złożonym z takich kwadratów. Udowodnić, że istnieje podzbiór zbioru , w którym liczba kwadratów jest nie mniejsza niż i żadne dwa kwadraty nie mają wspólnego wierzchołka.

Rozwiązanie

Zbiór kwadratów utworzonych na płaszczyźnie można podzielić na dwa podzbiory w ten sposób, że dwa kwadraty mające wspólny bok należą do różnych podzbiorów (por. podział szachownicy na pola białe i czarne). Podział taki można opisać w następujący sposób. Wprowadzamy na płaszczyźnie układ współrzędnych, którego osie są równoległe do prostych wyznaczających podział płaszczyzny na kwadraty, przy czym jednostka długości równa jest długości boku kwadratu oraz początek układu jest środkiem pewnego kwadratu. Wobec tego środek każdego kwadratu jest punktem kratowym (tzn. ma obie współrzędne będące liczbami całkowitymi). Do jednego podzbioru-zaliczamy wszystkie kwadraty, dla których suma współrzędnych środka jest liczbą parzystą, do drugiego - te kwadraty, dla których suma współrzędnych środka jest liczbą nieparzystą.

Do co najmniej jednego z tych podzbiorów należy nie mniej niż kwadratów zbioru . Bierzemy pod uwagę ten właśnie podzbiór zbioru kwadratów wyznaczonych na płaszczyźnie i dzielimy go na takie dwa podzbiory i , by dwa kwadraty mające wspólny wierzchołek należały do różnych podzbiorów. Podział ten zrealizujemy zaliczając do jednego podzbioru kwadraty, których środki mają pierwszą współrzędną parzystą, do drugiego zaś podzbioru kwadraty, których środki mają pierwszą współrzędną nieparzystą.

Do co najmniej jednego z podzbiorów i należy nie mniej niż połowa kwadratów zbioru , a więc nie mniej, niż kwadratów zbioru . Z konstrukcji podzbiorów wynika, że żadne dwa różne kwadraty tego podzbioru nie mają punktów wspólnych.