| НГУ http://forum.nsu.ru/ |
|
| Неграмотная старушка в самолете (тервер) http://forum.nsu.ru/viewtopic.php?f=18&t=3986 |
Страница 3 из 3 |
| Автор: | Коба [ Вт июн 01, 2010 2:53 am ] |
| Заголовок сообщения: | |
Anonymous писал(а): Какова вероятность, что человек номер к, сядет на свое место?
Чему равно среднее количество людей которые сядут на свои места? Без ограничения общности можно считать, что пассажиры заходят в самолёт в том же порядке, в каком указаны их места в билетах. То есть у первого пассажира-бабки в билете значится место номер [tex]1[/tex], у второго заходящего в самолёт в билете указано место номер [tex]2[/tex] и т. д. Допустим, бабка садится на место [tex]n_2[/tex]. Пассажир, у которого в билете значится место [tex]n_2[/tex], садится на место [tex]n_3[/tex]. Пассажир с местом [tex]n_3[/tex] в билете садится на место [tex]n_4[/tex] и т. д. Для некоторого [tex]m \leqslant N[/tex] будем иметь [tex]n_{m+1} = 1 = n_1[/tex]. Если рассмотреть перестановку [tex]\sigma[/tex], сопоставляющую номеру каждого билета номер места, на которое сел пассажир с этим билетом, то [tex]\sigma[/tex] будет состоять из одного цикла [tex](n_1, n_2, \ldots, n_m)[/tex]. Ясно, что [tex]1 = n_1 < n_2 < \ldots < n_m \leqslant N[/tex]. Пусть [tex]i \geqslant 1[/tex] и [tex]\bar{k}[/tex] - строго возрастающая последовательность натуральных чисел [tex]1 = k_1 < k_2 < \ldots < k_i \leqslant N[/tex] длины [tex]i[/tex], начинающаяся с [tex]1[/tex] и состоящая из чисел, не превосходящих [tex]N[/tex] (через [tex]U_i[/tex] обозначим множество всех таких последовательностей). Пусть [tex]A_\bar{k}[/tex] - событие, заключающееся в том, что [tex]m = i[/tex] и [tex]n_j = k_j[/tex] при всех [tex]j \in [1,i][/tex]. Тогда [tex]P(A_{\bar{k}}) = \frac{1}{N-k_1+1} \cdot \frac{1}{N-k_2+1} \cdot \ldots \cdot \frac{1}{N- k_i +1}[/tex]. Получаем, что [tex] P(m=i) = \sum_{\bar{k} \in U_i} \prod_{j=1}^i \frac{1}{N-k_i+1} [/tex] При [tex]i \neq 1[/tex] данная вероятность соответствует тому, что ровно [tex]i[/tex] человек сядут не на свои места. И как это, спрашивается, считать? Может, есть какие-нибудь хитрые способы? Что видно сразу? [tex]P(m=1) = 1/N[/tex] (бабка села на своё место и все сели на свои места), [tex]P(m=N) = 1/N![/tex] (все сели не на свои места в том и только в том случае, если каждый человек садится на следующее за его местом). Ещё [tex]P(m=2) = H_{N-1}/N[/tex], где [tex] H_k = \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{k} [/tex] есть [tex]k[/tex]-ая частичная сумма гармонического ряда. И при [tex]N \to \infty[/tex] получается, что [tex]P(m=2) \approx \ln(N-1) / N[/tex]. |
|
| Автор: | N.Ch. [ Ср июн 02, 2010 10:41 pm ] |
| Заголовок сообщения: | |
Ох уж мне эти некрофилы :) Вероятность, что [tex]k[/tex]-й человек из [tex]N[/tex] сядет на своё место, равна [tex]p_k=\dfrac{N-(k-1)}{N-(k-2)}[/tex], если [tex]k\geq 2[/tex], и равна [tex]p_1=1/N[/tex] при [tex]k=1[/tex]. Если [tex]I_k[/tex] - индикатор того, что [tex]k[/tex]-й человек сел на своё место, то математическое ожидание числа севших на свои места равно [tex]E\left(\sum_{k=1}^N I_k\right) = \sum_{k=1}^N p_k = \dfrac{1}{N}+\dfrac{N-1}{N}+\ldots+\dfrac12 = N-\sum_{k=1}^{N-1}\dfrac1k.[/tex] |
|
| Страница 3 из 3 | Часовой пояс: UTC + 7 часов |
| Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |
|