XXI OM - III -Zadanie 4

Na płaszczyźnie danych jest $ n $ prostokątów o bokach odpowiednio równoległych do dwóch danych prostych prostopadłych. Udowodnić, że jeżeli każde dwa z tych prostokątów mają co najmniej jeden punkt wspólny, to istnieje punkt należący do wszystkich prostokątów.

Rozwiązanie

Obierzmy dane proste za osie układu współrzędnych (rys. 14). Wtedy wierzchołki $ i $-tego prostokąta $ P_i $ będą miały współrzędne $ (x_i,y_i) $, $ (x_i,y'_i) $, $ (x'_i,y'_i) $, $ (x'_i,y_i) $, gdzie $ x_i < x'_i $, $ y_i <y'_i $. Punkt $ (x, y) $ należy więc do prostokąta $ P_i $ wtedy i tylko wtedy, gdy $ x_i \leq x \leq x'_i $ oraz $ y_i \leq y \leq y'_i $.

Z założenia każde dwa prostokąty $ P_i $ i $ P_j $ mają punkt wspólny. Zatem istnieją liczby $ x $, $ y $ takie, że

\[<br />
x_i \leq x \leq x'_i \textrm{ i } x_j \leq x \leq x'_j<br />
\]

oraz

\[<br />
y_i \leq y \leq y'_i \textrm{ i } y_j \leq y \leq y'_j.<br />
\]

Stąd

\[<br />
(1) \qquad  x_i \leq x'_j \textrm{ oraz } y_i \leq y'_j \textrm{ dla } i, j = 1,2, \ldots, n.<br />
\]

Oznaczmy przez $ a $ największą z liczb $ x_i $, a przez $ b $ - największą z liczb $ y_i $. Wtedy z określenia

\[<br />
(2) \qquad  x_j \leq a \textrm{ oraz } y_j \leq b \textrm{ dla } j = 1,2, \ldots, n,<br />
\]
\[<br />
(3) \qquad  a \leq x'_j \textrm{ oraz } b \leq y'_j \textrm{ dla } j = 1,2, \ldots, n.<br />
\]

Nierówności (2) i (3) dowodzą, że punkt $ (a, b) $ należy do każdego z prostokątów $ P_j $.

Uwaga 1. W przytoczonym rozwiązaniu nie korzystaliśmy w sposób istotny z tego, że liczba danych prostokątów jest skończona. Gdyby dana była pewna nieskończona rodzina prostokątów o analogicznych własnościach, to rozwiązanie przebiegałoby podobnie, z tym, że liczby $ a $ i $ b $ należałoby określać jako kresy górne zbioru liczb $ x_j $ i odpowiednio $ y_j $.

Uwaga 2. Podobne twierdzenie jest prawdziwe, jeśli zamiast prostokątów rozpatrywać dowolne figury wypukłe. Mianowicie zachodzi następujące

Twierdzenie Helly'ego. Jeśli na płaszczyźnie dana jest pewna niepusta rodzina zbiorów wypukłych taka, że każde trzy zbiory tej rodziny mają punkt wspólny, to istnieje punkt należący do wszystkich zbiorów tej rodziny.

Komentarze

Dodaj nową odpowiedź