XLVII OM - III - Zadanie 6

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

\[<br />
f(i) \geq i-1 \quad \text{ dla } i=1, 2, \ldots, n<br />
\]

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

\[<br />
f(i) \leq i+1 \quad \text{ dla } i=1, 2, \ldots, n<br />
\]

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:

\[<br />
(1) \qquad  \quad f(i) \geq i-1 \ \textrm{dla} \ i=1,2,\ldots,n.<br />
\]

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

\[<br />
(2) \qquad  \quad f(i) \leq i+1 \ \textrm{dla} \ i=1,2,\ldots,n.<br />
\]

(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:

\[<br />
V_n' = \{f \in V_n: f(n)=n\}, \quad V_n'' = \{f \in V_n: f(n)=n-1 \},<br />
\]
\[<br />
U_n' = \{f \in U_n: f(n)=n\}, \quad U_n'' = \{f \in U_n: f(n)=n-1 \},<br />
\]

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

\[<br />
(3) \qquad  \quad \varphi(i)=f(i)  \quad  \textrm{dla}\  i= 1,2,\ldots,n-1<br />
\]

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

\[<br />
(4) \qquad  \quad f(i)=<br />
\left\{<br />
\begin{array}{ccl}<br />
\varphi(i) & \textrm{dla} & i \leq n-1,\\<br />
n & \textrm{dla} & i=n<br />
\end{array}<br />
\right.<br />
\]

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

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

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

\[<br />
\psi(i) \geq i-1 \quad \textrm{dla}\ i = 1,2,\ldots,n-1<br />
\]

(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

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

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:

\[<br />
(7) \qquad  \quad v_n = v'_n + v''_n = 2 v_{n-1} \quad \textrm{dla} \ n \geq 3.<br />
\]

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

\[<br />
(8) \qquad  \quad \psi(i)=f(i) \quad \textrm{dla} \  i = 1,2,\ldots,n-2;<br />
\]

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

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

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

\[<br />
(10) \qquad  \quad u_n =u'_n+u''_n = u_{n-1} + u_{n-2} \quad \textrm{dla}\ n \geq 3.<br />
\]

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

\[<br />
u_n =u_{n-1} +u_{n-2} < u_{n-1}+u_{n-1} =2u_{n-1}.<br />
\]

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

\[<br />
\frac{p_n}{p_{n-1}} = \frac{u_n}{v_n} \cdot \frac{v_{n-1}}{u_{n-1}}<br />
= \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;<br />
\]

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

Komentarze

Dodaj nową odpowiedź