XXXVIII OM - I - Zadanie 4

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

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:

$Z$ jest sumą skończonej liczby kwadratów $Q_{xy}$ ( $x,y\in \mathbb{N}$ ),
$Z \subset R_{nn}$ ,
$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).

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$ .