XXXI - II - Zadanie 5

Zawody matematyczne:

XXXI OM, 1979-1980

Etap:

Wypisujemy kolejno wyrazy ciągu $(n_1, n_2, \ldots, n_k)$ , gdzie $n_1 = 1000$ , zaś $n_j$ dla $j > 1$ jest liczbą całkowitą wybraną losowo z przedziału $[0, n_{j-1} - 1]$ (wybór każdej liczby z tego przedziału jest jednakowo prawdopodobny). Kończymy wypisywanie, gdy wybrana liczba jest zerem, tzn. $n_{k-1}$ , $n_k = 0$ , Długość $k$ ciągu $(n_1, n_2, \ldots, n_k)$ jest zmienną losową. Udowodnić, że wartość oczekiwana tej zmiennej losowej jest większa od 7.

Rozwiązanie

Dla danej liczby całkowitej nieujemnej $n$ rozważmy zmienną losową $X_n$ będącą długością $k$ ciągu ( $n_1, n_2, \ldots, n_k$ ), gdzie $n_1 = n$ , $n_j$ dla $j > 1$ jest liczbą całkowitą wybraną losowo z przedziału $[0, n_{j-1} - 1]$ , $n_k = 0$ . Oznaczmy przez $E_n$ wartość oczekiwaną tej zmiennej losowej. Oczywiście $E_0 = 1$ , gdyż dla $n = 0$ istnieje tylko jeden ciąg mający długość $1$ , którego jedynym wyrazem jest $0$ . Niech $n$ będzie liczbą naturalną. Przypuśćmy, że wyznaczyliśmy wartości oczekiwane $E_m$ dla wszystkich $m < n$ . Rozważamy ciągi $(n_1, n_2, \ldots, n_k)$ , w których $n_1 = n$ . Możliwe są dwa następujące zdarzenia.

1) Albo $n_2 = n - 1$ (prawdopodobieństwo tego zdarzenia wynosi $\frac{1}{n}$ )
i wtedy wartość oczekiwana długości ciągu ( $n_2, \ldots, n_k$ ) wynosi $E_{n-1}$ , więc wartość oczekiwana długości ciągu ( $n_1, n_2, \ldots, n_k$ ) wynosi w tym przypadku $E_{n-1} + 1$ ,

2) albo $n_2 < n - 1$ (prawdopodobieństwo tego zdarzenia wynosi $\frac{n-1}{n}$ ) i wtedy wartość oczekiwana długości ciągu $(n_1, n_2, \ldots, n_k)$ jest dokładnie taka, jak wartość oczekiwana długości ciągu $(m_1, m_2, \ldots, m_k)$ , w którym $m_1 = n - 1$ ; ta wartość wynosi $E_{n-1}$ .

Wobec tego

$ E_n = \frac{1}{n} \left( E_{n-1} + 1 \right) + \frac{n-1}{n} E_{n-1} = E_{n-1} + \frac{1}{n}. $

Ponieważ $E_0 = 1$ , więc $E_1 = 1 + \frac{1}{1} = 2, E_2 = 2 + \frac{1}{2}, \ldots, E_n = 2 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n}$ .

Interesująca nas w zadaniu wartość oczekiwana wynosi

$ \begin{split} E_{1000} & = 2 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{1000} = 2 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \left(\frac{1}{5} + \ldots + \frac{1}{8}\right)+ \\ &\quad+\left(\frac{1}{9} + \ldots + \frac{1}{16}\right) +\left(\frac{1}{17} + \ldots + \frac{1}{32}\right) + \left(\frac{1}{33} + \ldots + \frac{1}{64}\right) +\\ &\quad + \left(\frac{1}{65} + \ldots + \frac{1}{128}\right) + \left(\frac{1}{129} + \ldots + \frac{1}{256}\right) + \left(\frac{1}{257} + \ldots + \frac{1}{512}\right) +\\ &\quad+\left(\frac{1}{513} + \ldots + \frac{1}{1024}\right) - \left(\frac{1}{1001} + \frac{1}{1002} + \ldots + \frac{1}{1024}\right). \end{split} $

Liczba w ostatnim nawiasie jest mniejsza od $\frac{24}{1000}$ natomiast każda
z liczb w poprzednich nawiasach (których jest osiem) jest większa od $\frac{1}{2}$ gdyż w $k$ -tym nawiasie jest liczba

$ \frac{1}{2^k+1} + \frac{1}{2^k+2} + \ldots + \frac{1}{2^{k+1}} $

będąca sumą $2^k$ składników, z których wszystkie są mniejsze (tylko ostatni równy). Wobec tego

$ \begin{split} E_{1000} &> 2 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + 8 \cdot \frac{1}{2} - \frac{24}{1000} = 6 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} - \frac{24}{1000} = \\ &= 6 + \frac{1500 + 1000 + 750 - 72}{3000} = 6 + \frac{3178}{3000} > 7 \end{split} $

Uwaga. Przybliżona wartość liczby $E_{1000}$ wynosi $8,48547$ .