XXXVIII OM - I - Zadanie 4

Dla danej liczby naturalnej $ n $ rozpatrujemy rodzinę $ W $ wszystkich takich zbiorów $ A $ par liczb naturalnych nie większych od $ n $, że jeżeli $ (a, b) \in A $, to $ (x, y) \in A $ dla $ 1 \leq x \leq a $, $ 1 \leq y \leq b $.

Wykazać, że rodzina $ W $ składa się z $ \binom{2n}{n} $ różnych zbiorów.

Rozwiązanie

Dla dowolnej pary liczb naturalnych $ (x,y) $ oznaczamy przez $ Q_{xy} $ kwadrat jednostkowy o wierzchołkach $ (x-1,y-1) $, $ (x,y-1) $, $ (x,y) $, $ (x-1,y) $, zaś przez $ R_{xy} $ - prostokąt o wierzchołkach $ (0,0) $, $ (x,0) $, $ (x,y) $, $ (0,y) $. Jeśli $ A $ jest dowolnym zbiorem par liczb naturalnych, to symbolem $ Z(A) $ będziemy oznaczać następujący podzbiór płaszczyzny:

\[<br /> Z(A)= \bigcup_{(x,y) \in A} Q_{xy};<br /> \]

przyjmujemy przy tym

\[<br /> Z(\emptyset)=\emptyset<br /> \]

Zgodnie z treścią zadania, zbiór $ A $ należy do rodziny $ W $ wtedy i tylko wtedy, gdy zbiór $ Z = Z(A) $ spełnia warunki:

  1. $ Z $ jest sumą skończonej liczby kwadratów $ Q_{xy} $ ($ x,y\in \mathbb{N} $),
  2. $ Z \subset R_{nn} $,
  3. $ Q_{ab} \subset Z \Longrightarrow R_{ab} \subset Z $.

W szczególności zbiór pusty (złożony z $ 0 $ kwadratów jednostkowych) spełnia te warunki.

Załóżmy chwilowo, że zbiór $ Z $ nie jest pusty. Implikacja (3) wyraża wówczas dokładnie tyle, że $ Z $ jest sumą pewnej (skończonej, dodatniej) liczby prostokątów postaci $ R_{ab} $ - czyli prostokątów o dwóch bokach położonych na dodatnich półosiach układu współrzędnych. Skończona suma takich prostokątów (zawartych w $ R_nn $) jest wielokątem ograniczonym łamaną zamkniętą $ ON_0M_1N_1\ldots M_kN_kO $, gdzie: $ k\in \mathbb{N} $; wszystkie wierzchołki mają współrzędne całkowite; $ O $ jest początkiem układu współrzędnych; $ N_0 $ jest punktem odcinka $ OK $, gdzie $ K = (0, n) $; $ N_k $ jest punktem odcinka $ OL $, gdzie $ L = (n, 0) $; wektory $ \overrightarrow{N_{i-1}M_i} $, są równoległe do osi $ Ox $ i skierowane zgodnie ze zwrotem tej osi; wektory $ \overrightarrow{M_iN_i} $ są równoległe do osi $ Oy $ i skierowane przeciwnie do zwrotu tej osi ($ i = 1, \ldots , k $) (rysunek 3).
om38_1r_img_3.jpg
Na odwrót, każdy wielokąt $ Z $ ograniczony taką łamaną spełnia warunki (1), (2), (3), a więc odpowiada pewnemu niepustemu zbiorowi $ A\in W $. Pozostaje policzyć te wielokąty.

Niech $ ON_0M_1N_1\ldots M_kN_kO $ będzie wielokątem omawianej postaci. Każdy z wektorów $ \overrightarrow{N_{i-1}M_i} $ jest sumą pewnej liczby wektorów jednostkowych $ [1,0] $, zaś każdy z wektorów $ \overrightarrow{M_iN_i} $, jest sumą pewnej liczby wektorów jednostkowych $ [0, -1] $. Weźmy pod uwagę łamaną $ KN_0M_1N_1\ldots M_kN_kL $ (może być $ K = N_0 $ lub $ N_k = L $), zorientowaną od $ K $ do $ L $. Składa się ona z $ 2n $ wektorów jednostkowych: każdy z wektorów $ [1, 0] $ i $ [0, -1] $ musi wystąpić $ n $--krotnie (idąc od $ K $ do $ L $ musimy wykonać $ n $ kroków w prawo i $ n $ kroków w dół). Wielokąt $ Z $ jest jednoznacznie określony przez drogę tego typu biegnącą od $ K $ do $ L $.

Ponieważ założyliśmy (chwilowo), że zbiór $ Z $ jest niepusty, musimy wykluczyć drogę od $ K $ do $ L $ złożoną kolejno z $ n $--krotnie powtórzonego wektora $ [0, -1] $, a następnie z $ n $--krotnie powtórzonego wektora $ [1,0] $ (czyli łamaną $ KOL $). Naturalne jest teraz dopuścić i tę drogę przyjmując, że odpowiada ona właśnie pustemu zbiorowi $ Z $ (który też trzeba włączyć do rozważań).

Ile jest więc dopuszczalnych dróg od $ K $ do $ L $? Mamy $ 2n $ wektorów jednostkowych dwóch typów. Jeśli w ciągu $ (1, 2, \ldots, 2n) $ ustalimy $ n $ miejsc, na których umieszczamy wektor $ [1, 0] $, to na pozostałych $ n $ miejscach musi wystąpić wektor $ [0, -1] $. Jest więc tyle rozważanych dróg, ile podzbiorów $ n $--elementowych zbioru $ 2n $--elementowego, czyli $ \binom{2n}{n} $. Tyle samo jest wielokątów $ Z $ spełniających warunki (1), (2), (3), tyle samo więc i zbiorów $ A $ w rodzinie $ W $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz