XLII OM - III - Zadanie 2

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

III

Niech $X$ będzie zbiorem punktów płaszczyzny $(x.y)$ o obydwu współrzędnych całkowitych. Drogą długości $n$ nazywamy każdy taki ciąg $(P_0, P_1,\ldots, P_n)$ punktów zbioru $X$ , że $|P_{i-1}P_{i}|=1$ dla $i \in \{1,2,\ldots,n\}$ . Niech $F(n)$ będzie liczbą różnych dróg $(P_0,P_1,\ldots,P_n)$ o początku $P_0 = (0,0)$ i końcu $P_n$ położonym na prostej o równaniu $y = 0$ . Udowodnić, że

$ F(n) = \binom{2n}{n}. $

Rozwiązanie

Dowolnej drodze długości $n$ , o początku $P_0 = (0,0)$ , przyporządkujemy ciąg $2n$ symboli, z których każdy jest zerem lub jedynką. Czynimy to w sposób następujący. Jeżeli droga ma postać $(P_0,P_1,\ldots,P_n)$ , to odpowiadający jej ciąg zero-jedynkowy

$ (c_1,c_2,\ldots,c_{2n-1} ,c_{2n}), $

zwany kodem tej drogi, określamy zespołem reguł:

$ \begin{array}{lcll} \textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [ 1,0], & \textrm{to} & c_{2j-1} = 1, c_{2j} = 0;\\ \textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [ 0,1], & \textrm{to} & c_{2j-1} = 1, c_{2j} = 1;\\ \textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [-1,0], & \textrm{to} & c_{2j-1} = 0, c_{2j} = 1;\\ \textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [0,-1], & \textrm{to} & c_{2j-1} = 0, c_{2j} = 0. \end{array} $

Mówiąc obrazowo: krok w prawo kodujemy przy pomocy pary $10$ ; krok w górę: $11$ ; krok w lewo: $01$ ; krok w dół: $00$ .

Na odwrót: każdy ciąg zero-jedynkowy długości $2n$ wyznacza drogę, której jest kodem.

Różnym drogom odpowiadają różne ciągi zero-jedynkowe; kodowanie jest wzajemnie jednoznaczne.

Zauważmy teraz, że jeżeli punkt $P_n$ , koniec drogi, leży na prostej o równaniu $y = k$ , to znaczy, że wykonaliśmy $g$ kroków w górę i $d$ kroków w dół, gdzie $g$ i $d$ są liczbami o różnicy $g - d = k$ . Pozostałe ruchy (w liczbie $n-g-d$ ) były poziome, i jest bez znaczenia, które z nich wykonaliśmy w prawo, a które w lewo.

Liczba jedynek w kodzie takiej drogi wynosi

$ 2g + (n-g-d) = n + g-d = n + k. $

A zatem kodami dróg kończących się na prostej $y = 0$ są ciągi złożone dokładnie z $n$ jedynek i $n$ zer. Numery miejsc, na których występują jedynki, mogą tworzyć dowolny $n$ -elementowy podzbiór zbioru $\{1,2,\ldots,2n\}$ . Liczba takich podzbiorów wynosi $\binom{2n}{n}$ . Tyle jest więc i dróg długości $n$ o końcu położonym na prostej $y = 0$ .