XLVII OM - III - Zadanie 6

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

III

Spośród wszystkich permutacji $f$ zbioru $\{1,2, \ldots , n\}$ spełniających warunek

$ f(i) \geq i-1 \quad \text{ dla } i=1, 2, \ldots, n $

wybieramy jedną (każdy wybór jest jednakowo prawdopodobny). Niech $p_n$ będzie prawdopodobieństwemtego, że wybrana permutacja spełnia warunek

$ f(i) \leq i+1 \quad \text{ dla } i=1, 2, \ldots, n $

Wyznaczyć wszystkie liczby naturalne $n$ , dla których $p_n > \frac{1}{3}$ .

Rozwiązanie

Oznaczmy przez $V_n$ zbiór tych permutacji zbioru $\{1,2,\ldots,n\}$ (czyli różnowartościowych funkcji $f: \{1,2,\ldots,n\} \to \{1,2,\ldots,n\}$ ), które spełniają pierwszy z podanych warunków:

$ (1) \qquad \quad f(i) \geq i-1 \ \textrm{dla} \ i=1,2,\ldots,n. $

Oznaczmy ponadto przez $U_n$ zbiór tych permutacji $f$ , które spełniają oba podane warunki: (1) oraz

$ (2) \qquad \quad f(i) \leq i+1 \ \textrm{dla} \ i=1,2,\ldots,n. $

(Oczywiście $U_n$ jest podzbiorem zbioru $V_n$ .) Niech $v_n$ będzie liczbą permutacji w zbiorze $V_n$ i niech $u_n$ będzie liczbą permutacji w zbiorze $U_n$ . Wówczas $p_n=u_n/v_n$ .

Rozpatrzymy najpierw przypadki banalne: $n = 1$ , $n = 2$ . W zbiorze jednoelementowym można określić tylko jedną permutację; w zbiorze dwuelementowym dwie. Każda z nich spełnia warunki (1), (2). Zatem $u_1 =v_1 = 1$ , $u_2=v_2 = 2$ .

Ustalmy $n \geq 3$ . Jeśli permutacja $f$ zbioru $\{1,2,\ldots,n\}$ spełnia warunek (1), to w szczególności $f(n) \geq n - 1$ , co oznacza, że $f(n) = n$ lub $f(n) = n - 1$ . Tak więc zarówno zbiór $V_n$ , jak i $U_n$ , jest sumą dwóch podzbiorów, złożonych (odpowiednio) z tych permutacji, które spełniają pierwszy bądź drugi człon tej alternatywy. Oznaczmy te podzbiory, jak następuje:

$ V_n' = \{f \in V_n: f(n)=n\}, \quad V_n'' = \{f \in V_n: f(n)=n-1 \}, $

$ U_n' = \{f \in U_n: f(n)=n\}, \quad U_n'' = \{f \in U_n: f(n)=n-1 \}, $

i przyjmijmy, że w zbiorach tych jest (odpowiednio): $v'_n$ permutacji, $v''_n$ permutacji, $u'_n$ permutacji, $u''_n$ permutacji. Wówczas $v_n = v'_n + v''_n$ , $u_n = u'_n+u''_n$ .

Weźmy dowolną permutację $f \in V'_n$ : spełnia ona równość $f(n) = n$ , a zatem $f(i) \leq n - 1$ dla $i \leq n - 1$ . Przyjmując

$ (3) \qquad \quad \varphi(i)=f(i) \quad \textrm{dla}\ i= 1,2,\ldots,n-1 $

określamy permutację $\varphi: \{1,2, \ldots, n-1\} \to \{1,2, \ldots,n-1\}$ . Warunek (1) jest spełniony przez permutację $f$ , więc także przez permutację $\varphi$ . To znaczy, że $\varphi \in V_{n-1}$ .

Na odwrót, jeśli $\varphi$ jest dowolną permutacją zbioru $\{1,2,\ldots,n-1\}$ należącą do zbioru $V_{n-1}$ , to przyjmując

$ (4) \qquad \quad f(i)= \left\{ \begin{array}{ccl} \varphi(i) & \textrm{dla} & i \leq n-1,\\ n & \textrm{dla} & i=n \end{array} \right. $

dostajemy permutację zbioru $\{1,2,\ldots,n\}$ spełniającą warunek (1) wraz z równością $f(n) =n$ , czyli permutację należącą do zbioru $V'_n$ .

Wzór (3) określa operację zawężenia $f$ do zbioru $\{1,2,\ldots,n-1\}$ ; wzór (4) określa operację rozszerzenia $\varphi$ do zbioru $\{1,2,\ldots,n\}$ . Te dwie operacje są wzajemnie odwrotne, więc ustalają wzajemnie jednoznaczną odpowiedniość pomiędzy elementami zbioru $V'_n$ i elementami zbioru $V_{n-1}$ . Stąd wniosek, że zbiory te liczą tyle samo elementów (są równoliczne): $v'_n = v_{n-1}$ .

Weźmy dowolną permutację $f \in V''_n$ : spełnia ona równość $f(n) = n-1$ . Istnieje w zbiorze $\{1,2,\ldots,n-1\}$ dokładnie jeden element $i_0$ taki, że $f(i_0) = n$ . Przyjmując

$ (5) \qquad \quad \psi(i) = \left\{ \begin{array}{lll} f(i) & \textrm{dla} & i \ne i_0, 1 \leq i \leq n-1,\\ n-1 & \textrm{dla} & i=i_0 \end{array} \right. $

określamy permutację $\psi: \{1,2,\ldots,n-1\} \to \{1,2,\ldots,n-1\}$ . Przy tym

$ \psi(i) \geq i-1 \quad \textrm{dla}\ i = 1,2,\ldots,n-1 $

(dla $i \ne i_0$ wynika to z warunku (1), a dla $i = i_0$ mamy $\psi(i_0) = n- 1 \geq i_0 - 1$ ). To znaczy, że $\psi \in V_{n-1}$ .

Na odwrót, jeśli $\psi$ jest dowolną permutacją zbioru $\{1,2,\ldots,n-1\}$ należącą do zbioru $V_{n-1}$ , to istnieje element $i_0 \in \{1,2,\ldots,n-1\}$ , dla którego zachodzi równość $\psi(i_0) = n - 1$ . Przyjmując

$ (6) \qquad \quad f(i) = \left\{ \begin{array}{ccl} \psi(i) & \textrm{dla} & i \ne i_0,\ 1 \leq i \leq n-1,\\ n & \textrm{dla} & i=i_0\\ n-1 & \textrm{dla} & i=n \end{array} \right. $

dostajemy permutację zbioru $\{1,2,\ldots,n\}$ . Spełnia ona warunek (1) oraz równość $f(n) = n - 1$ , więc należy do zbioru $V''_n$ .

Jak poprzednio, operacje wyznaczania $\psi$ przez $f$ (wzór (5)) oraz wyznaczania $f$ przez $\psi$ (wzór (6)) są wzajemnie odwrotne. Ustalają zatem wzajemnie jednoznaczną odpowiedniość pomiędzy elementami zbioru $V''_n$ i elementami zbioru $V_{n-1}$ . Tak więc $v''_n = v_{n-1}$ . W połączeniu z poprzednią konkluzją otrzymujemy związek:

$ (7) \qquad \quad v_n = v'_n + v''_n = 2 v_{n-1} \quad \textrm{dla} \ n \geq 3. $

Uzyskaliśmy wzór rekurencyjny dla ciągu $(v_n)$ .

Podobne rozumowanie da nam wzór rekurencyjny dla ciągu $(u_n)$ .

Weźmy permutację $f \in U'_n$ (zatem $f(n) = n$ ) i niech $\varphi$ będzie zawężeniem $f$ do zbioru $\{1,2,\ldots,n-1\}$ ; to znaczy, definiujemy $\varphi$ wzorem (3). Warunki (1) i (2) są spełnione przez permutację $f$ , więc także przez $\varphi$ . To znaczy, że $\varphi \in U_{n-1}$ .

Na odwrót, jeśli $\varphi$ jest permutacją zbioru $\{1,2,\ldots ,n-1\}$ należącą do $U_{n-1}$ , to możemy ją rozszerzyć do permutacji $f$ zbioru $\{1,2,\ldots,n\}$ , przyjmując $f(n) = n$ . Rozszerzona permutacja spełnia warunki (1) i (2) oraz $f(n) = n$ , więc należy do zbioru $U'_n$ .

Wzajemnie odwrotne operacje rozszerzania i zawężania dają odpowiedniość między elementami zbiorów $U'_n$ i $U_{n-1}$ . Zatem $u'_n = u_{n-1}$ .

Weźmy wreszcie dowolną permutację $f \in U''_n$ (zatem $f(n) = n-1$ ). Wobec warunku (2), element $n$ nie może być równy $f(k)$ dla żadnego $k < n - 1$ ; musi być równy $f(n - 1)$ . Permutacja $f$ zamienia więc miejscami elementy $n-1$ i $n$ . Zawężamy ją do zbioru $\{1,2,\ldots,n-2\}$ ; to znaczy, przyjmujemy

$ (8) \qquad \quad \psi(i)=f(i) \quad \textrm{dla} \ i = 1,2,\ldots,n-2; $

dostajemy permutację $\psi$ zbioru $\{1,2,\ldots,n-2\}$ . Warunki (1) i (2) są spełnione przez $f$ , więc i przez $\psi$ . Zatem $\psi \in U_{n-2}$ .

Na odwrót, jeśli $\psi$ jest permutacją zbioru $\{1,2,\ldots,n-2\}$ należącą do $U_{n-2}$ , to rozszerzamy ją do permutacji $f$ zbioru $\{1,2,\ldots,n\}$ , przyjmując

$ (9) \qquad \quad f(i)=\left\{ \begin{array}{ccc} \psi(i) & \textrm{dla} & i \leq n-2,\\ n & \textrm{dla} & i=n-1,\\ n-1 & \textrm{dla} & i=n. \end{array} \right. $

Rozszerzona permutacja spełnia warunki (1) i (2) oraz $f(n)=n-1$ , czyli należy do zbioru $U''_n$ .

Także i teraz operacje zawężania (wzór (8)) i rozszerzania (wzór (9)) są wzajemnie odwrotne i dają odpowiedniość między elementami zbiorów $U''_n$ i $U_{n-2}$ . Zatem $u''_n=u_{n-2}$ . W konsekwencji

$ (10) \qquad \quad u_n =u'_n+u''_n = u_{n-1} + u_{n-2} \quad \textrm{dla}\ n \geq 3. $

Mamy wzór rekurencyjny dla ciągu $(u_n)$ .

[Jak widać, $(u_n)$ jest ciągiem Fibonacci'ego; podobnie wzór (7) pozwala wywnioskować, że $(v_n)$ jest ciągiem kolejnych potęg dwójki; nie będziemy jednak w tym rozwiązaniu korzystać z jawnych przedstawień tych ciągów.]

Ze wzoru (10) wynika, że $u_n>u_{n-1}$ dla $n \geq 3$ ; a skoro $u_2 = 2$ , $u_1 = 1$ , zatem $u_n >u_{n-1}$ dla $n\geq 2$ . W takim razie dla $n \geq 3$ zachodzi nierówność $u_{n-1} >u_{n-2}$ . Wzór (10) daje więc oszacowanie

$ u_n =u_{n-1} +u_{n-2} < u_{n-1}+u_{n-1} =2u_{n-1}. $

Stąd oraz z zależności (7) wnosimy, że

$ \frac{p_n}{p_{n-1}} = \frac{u_n}{v_n} \cdot \frac{v_{n-1}}{u_{n-1}} = \frac{v_{n-1}}{v_n} \cdot \frac{u_n}{u_{n-1}} < \frac{1}{2} \cdot 2 = 1 \quad \textrm{dla}\ n \geq 3; $

ciąg $(p_n)$ jest malejący (począwszy od drugiego wyrazu).

Korzystając ze wzorów (10) i (7) obliczamy początkowe wyrazy ciągów $(u_n)$ i $(v_n)$ i stwierdzamy, że $u_6=13$ , $u_7 = 21$ , $v_6 = 32$ , $v_7 = 64$ . Wobec tego $p_6= \frac{13}{32} > \frac{1}{3}$ , $p_7 = \frac{21}{64} < \frac{1}{3}$ , i z monotoniczności ciągu $(p_n)$ wynika odpowiedź: nierówność $p_n > \frac{1}{3}$ zachodzi tylko dla $n =1, 2, 3, 4, 5, 6$ .