Форум умных людей

Задача называется "Сумасшедшая старушка в самолете". Суть в следующем. Есть самолёт, в котором N пассажирских мест (N>=1). N-1 из них предназначены адекватным пассажирам, а одно - сумасшедшей старушке. Идёт посадка на рейс. Пассажиры, включая старушку, в случайном порядке заходят в салон. Если в салон заходит старушка, вне зависимости от места, указанного у неё в билете, она случайным образом занимает любое свободное место (везде в этой задаче, говоря "случайно", я подразумеваю "с равной вероятностью для каждого возможного случая"). Адекватный же пассажир всегда занимает своё собственное место, если оно свободно. В противном случае он, как и старушка, занимает случайное свободное место.
Вопрос задачи: с какой вероятностью все пассажиры сядут на свои собственные места?

В оригинале нас интересовал лишь последний пассажир, а тут ВСЕ.

Тогда вопрос сводится к более простому:

"С какой вероятностью СС займет свое место?" :)

Понеслась индукция...
Для N=1, все понятно.

Для N=2, 1/2 шанс, что СС зайдет последней, и все сведется к предыдущему варианту
Также 1/2, что зайдет первой - тогда опять 1/2. Выходит 3/4...

Для N=3, шанс 2/3, что старушка не зайдет первой (т.е. предыдущий вариант)
и 1/3 опять же в квадрате....


1/N² + ((N-1)/N)*(...) как-то так  :-\

Что ж вы так флудите, господин модератор. 5 сообщения подрят и всё об одном  :laugh:

не стоит забывать про:

Я приберу за собой :) (уже все подмел  :sing:)


Почему это? Как раз об этом лучше забыть. По условию необходимо, чтобы сели на СВОИ места ВСЕ пассажиры. Это возможно ТОЛЬКО в том случае, если Старушка "угадает" со своим местом и никому "сумасшедшее знамя" не перейдет :)

1/N²   +  ((N-1)/N)*( 1/(N-1)² + ((N-2)/N-1))*(1/(N-2)²+((N-3)/(N-2))*(...и так далее))))))))



Короче, в алгоритме для каждого следующего шага N присвоить (N-1), остановившись на единице.

Например для N=5 получается:

1/25 + (4/5)*
*(1/16+(3/4)*
*(1/9 + (2/3)*
*(1/4 + (1/2))))
=
1/25 + 20/48 = 548/1200 = 137/300

Точняк, я ошибся

Если в самолете должно быть более одного пассажира, то вероятность равна нулю.
см. Законы Мерфи

Это же число можно получить и так:

1/N * ( 1/N + 1/(N-1) + 1/(N-2) + 1/(N-3) + ... + 1/1 )

1/5 * ( 1/5 + 1/4 + 1/3 + 1/2 + 1)

по вашим расчетам, для 3 мест вероятность получается равная 11/18. Т.к. дробь не сокращается, то возможных исходов событий должно быть минимум 18 (число кратное 18). А их меньше (:

Ну-ну. Или встретим динозавра или не встретим.
Кому "должна"?

http://nazva.net/forum/index.php/topic,3057.0.html

Там другое условие  :)

Я бы сказал, что другой вопрос.

вероятность = благоприятные случаи/все случаи

разве не очевидно, что если дробь несократима, то её знаменатель является делителем всех случаев?


На то и вариация! В задаче спрашивается абсолютно другое, и решается также по-другому (:

1/N² + (1/N)*(1/N-1) + ...+ 1/N ?

их 18 14
шас...

Старушка 1
пасажиры 2,3
места соотв 1,2,3

Варианты рассадки
123  +  +  +  +  +  +
132  -   -   -   -   -   -
213  +  -   +  -   -   +
231  -   -   -   -   -   +
312  +  -   -   -   -   -
321  +  +  -   -   -   +

первый столбец - первая входит старушка, второй -2 пассажир = 4 возможных варианта рассадки (+).
(-) - невозможный вариант

второй столбец - первый входит 2, потом бабка 1 = 2 возможных варианта

третий столбец - первый входит 3 пассажир, потом бабка 1 = 2 возможных варианта

четвертый столбец - первый входит 2 пассажир, потом 3 пассажир = 1 возможный варианта

пятый столбец - первый входит 3 пассажир, потом 2 пассажир = 1 возможный вариант

шестой столбец - первая входит старушка 1, потом 3 пассажир = 4 возможных варианта

и суммируем 4+2+2+1+1+4=14 (хм неполучилос') или где то ошибка?

Показать скрытый текст

именно это я и имел ввиду


почему 36? вы же сами только что доказали обратное.

Вероятности надо не складывать, а вычислять среднюю?

вопрос адресован ко мне? (:

Ога.

не скажу :tongue:

Предложенная задача отличается от той, на которую сослался Илья только последним вопросом.
И этот вопрос имхо "портит" элегантность всей задачи.
Вероятность того, что все пассажиры сядут на свои места равна в точности вероятности того, что старушка сядет на своё место и то, что в противном случае адекватный пассажир, как и старушка, занимает случайное свободное место уже никакой роли не играет :)
Таким образом условие задачи: Какова вероятность, что старушка, находясь случайным образом в очереди на посадку, сядет на своё место, не глядя на билет? И всё. Имхо, это не так интересно как в той задаче. Но раз вопрос поставлен - отвечу.
Старушка с равной вероятностью P1 = 1/N может быть последней в очереди, предпоследней и т.д.
При этом, если она последняя, вероятность того, что она сядет на своё место равна 1, если предпоследняя - 1/2, предпредпоследняя - 1/3, ..., вторая - 1/(N-1), первая - 1/N.
Итого, общая вероятность P = (1/N) * (1 + 1/ 2 + 1/3 + ... + 1(N-1) + 1/N).
При N стремящемся к бесконечности 1 + 1/ 2 + 1/3 + ... + 1(N-1) + 1/N стремится к lnN, итого:
P =~ lnN/N
Поскольку lnN/N убывает с возрастанием N, то вероятность того, что старушка сядет на своё место тоже убывает.
Например, при N=100: ln100 =~ 4.6, следовательно, Р =~ 0.046

Я бы не спешил с выводами ;)

Для 2-х пассажиров вероятность - 3/4, хотя случаев вроде 3. Один, если старушка вошла второй, и два, если первой. Вас это не смутило?

А здесь где-то бродит призрак задачи Монти Холла, где несколько людей видят 4 варианта для версий поведения ведущего, а вероятности в знаменателе имеют тройку - 1/3, 2/3.

Вообще-то полная отчетность событий должна иметь как минимум N! (N факториал) вариантов входа в самолет, не говоря уже о выборе мест внутри. Так что там нааааамного больше цифры, чем 14 и 18.

Правил'но N! вариантов рассадки и N! вариантов входа в самолет (очередност' входа)
Итого 3! = 6 и 3! =6
6 * 6 = 36 всего вариантов (без ограничений задачи)
из них тол'ко 14 возможных (с учетом адекватных пассажиров)
с.м. мой коммент (http://nazva.net/forum/index.php/topic,5081.msg118558.html#msg118558)

эх, я окончательно осознал собственную ошибку в расчетах - вы целиком правы!
Показать скрытый текст

Расскажи, как получалось. Может, используем на "кухне".