задачка по вероятности

недавно рассказали забавную задачку по теории вероятностей:

в самолете 257 мест, которые должны занять 257 пассажиров (у каждого в посадочном талоне указано его место). Однако, первый пассажир весьма рассеян, и садится на случайно выбранное место. Каждый следующий пассажир, как вежливый и тактичный человек, делает так: если его место свободно, то он туда садится, если нет, садится на случайно выбранное место из свободных. Вопрос: какова вероятность того, что последний пассажир сядет на свое место?

 

1/2

 

Что-то мне подсказывает, что не сядет с вероятностью 1/256. Это как раз тот случай, если последний садится на место первого. Сядет, соответственно, с вероятностью 255/256.




Хотя 1/2 тоже возможно

 

1/2 - по соображениям симметрии

 

Даю ответ: вероятность равна (1/257).

Решение. Рассмотрим вход последнего пассажира. Он занимает свое место если остальные 256 мест заняты. Количество размещений 256 пассажиров по 256 местам равно (256!) (факториал). Количество всех возможных размещений 257 пассажиров равно (257!). Так что делим первое на второе и получаем ответ: (1/257).

Подобно поручику Ржевскому из анекдота, удивляюсь тому, какую важную роль играет 257 в этой задаче. Для n пассажиров ответ (1/n) получается гораздо проще.

 

1/2 - без вариантов

 

Вообще, да. В условии сказано, что

, так что он может сесть случайно на своё место. Не учёл
Только не 1/257, а 256/257.

 

чисто интуитивно, ничего не считая - 1/2

 

1/257 - это вероятность, что первый сядет на место последнего. А ещё он может сесть на место второго, а второй сядет на место последнего. А ещё он может сесть на место третьего, а третий на место последнего. И ещё много чего может быть.

1/2 получается.

 

Вы не учитываете. что размещение не случайно, все кроме 1-ого по возможности садятся на своё место. В частности, 1 /257 - вероятность того, что 1-ый сел на своё место. Тогда и последний сядет на своё.
Если 1-ый сел на 256 место, то тогда вероятность что и последний - 1/2. т е сразу получаем 3/514, а ведь ещё и другие выборы.
Вообще то задача известная, можно прочитать, и ясно, как делать, но я пока не нашёл времени собраться
А ответ, если мне память не изменяет, как то связан с е. Что-то вроде 1- 1/е

 

Хотя нет...:/
Блин, не такая уж и простая задачка...
Похоже, правда 1/2.

 

Вряд ли. Очевидно, верно одно из двух:
-ответ фиксирован при любом n
-ответ зависит от n.
Я проверил при n=2,3,4 получается 1/2. Разумеется, это не значит, что при 257 получится 1/2. Но зато значит, что в ответе не получится числа е.
Кстати, когда DM написал 1/2, я думал это шутка: либо сядет, либо не сядет А оказывается, правда.

 

А Вы попробуйте её по индукции решить. То есть доказать, что если вероятность для n равна 1/2, то и для n+1 она будет равна 1/2. По-моему это довольно несложно должно быть.

 

Да, похоже, что действительно 1/2, но насчёт е Вы не поняли. Это конечно в пределе имелось ввиду.

 

Если е и может получиться, то только в пределе.

 

Я, наверно, непонятно выразился. На счёт е я понял так:

Вы хотели сказать, что в ответе получается функция, зависящая от n. Например, f(n)=1-1/(1+1/n)^n)
И тогда при n= бесконечность получается ответ с е.

Поэтому я и написал, что ответ не зависит от n, т.е в ответе е быть не может.

 

Да, действительно, очень легко доказывается по индукции(т е я конечно сразу пытался, но у меня был заскок). 1/2
Но хотелось бы понять, как это можно увидеть сразу.

 

С вероятностью 1/n первый пассажир сел на свое место, с такой же вероятностью - на место последнего зашедчего в салон пассажира. Остальные случаи сведутся к задаче меньшей размерности с той же симметрией. Т.е. действительно пополам.

 

Всё. А я ведь делал так же, но не "с той же симетрией", а "с той же вероятностью" 1/2. И не было видно.

 

а ведь я соврал, похоже

 

Нет, все было правильно: только в "средних" случаях симметрия состоит не в свое место или место последнего, а место первого или последнего.

 

Да. Именно в этом у меня был заскок - долго не видел, что в дальнейшем 1-ое занимает место "своего"

 

у меня получилось такое решение:

пусть p_n - искомая вероятность в задаче с n пассажирами,
А - событие {последний пассажир сел на свое место},
К - порядковый номер пассажира, чье место занял первый.

Тогда, если k не равно 1 или n, имеем P[ A | K=k] =p_{n-k+1}, и значит по формуле полной вероятности p_n=(1/n)(p_2+...+p_{n-1}+1).
Так как p_2=1/2, по индукции легко получить p_n=1/2 для любого n. Однако, строго решить эту задачу совсем без индукции я не знаю как, если кто подскажет, буду благодарен. Замечу только что решение MS (пост N. 18) уже в неявном виде использует предположение что p_n=1/2 для любого n.

 

Serge_P, я ничего неявно не использую. Могу переформулировать: сколько бы случайных выборов за время рассадки не произошло, вероятность выбора места первого пассажира равна вероятности выбора места последнего пассажира. Чему они равны - не суть важно, важно что равны друг другу. Вполне строго, мне кажется.

 

т.е., рассуждение такое: если при произвольном случайном выборе соответствующий пассажир сел на место первого пассажира, то событие А произойдет, а если на место последнего пассажира, то событие А не произойдет. Да, это, видимо, работает, спасибо!

 

Если задуматься, то несложно: есть 2 особенных места - первого и последнего пассажира. Если делающий выбор пассажир занимает место первого, то цепочка заканчивается и далее все садятся на свои места. Если же занимается кресло последнего пассажира, то по условиям задачи (вежливые пассажиры) последний занять его уже не может. В каждом случае выбор равновероятно случаен и из симметрии получается 1/2. По-моему так.

 

Ну, с помощью индукции – это абсолютно строгое доказательство. Попробую его воспроизвести. Итак, легко убедиться, что p(2) =1/2.
Теперь докажем, что p(n) также равно 1/2; если нам известно, что p(n-1), p(n-2) и т.д=1/2
Будем считать для удобства, что первый пассажир должен занять место 1, второй – место 2 и т.д. Первый пассажир с вероятностью 1/n может занять любое место. Есть два особых случая. Если он занимает первое место (то есть своё); то все остальные пассажиры (и последний в том числе) также гарантировано займут свои места. Если же он занимает последнее, n-oe место, то наоборот ясно, что последний пассажир на него уже никак не сможет попасть. Теперь рассмотрим промежуточные случаи. Пусть, он занимает 2-ое место. Тогда вошедший второй пассажир обнаруживает своё место занятым и .... у нас получается исходная задача, только для n=n-1. (В самом деле – у этого второго пассажира осталось n-1 мест (все кроме второго), и он с равной вероятностью занимает любое из них, то есть точно то же самое, что в исходной задаче). Пусть он занимает третье место. Тогда входит второй пассажир, садится на своё свободное место, затем входит третий пассажир, обнаруживает своё место занятым, и ... получается исходная задача, только n=n-2. Ну и так далее. Наконец, если он занимает n-1ое место, то в конце получаем задачу для n=2. И таким образом получаем вероятность:
P(n)=1/n*1+1/n*p(n-1)+1/n*p(n-2)+….+1/n*p(2)+1/n*0 или 1/n(1+p(n-1)+p(n-2)+….+p(2)+0)
Всего у нас n слагаемых, первое и последнее в сумме дают 1, все остальные равны 1/2 (как мы в самом начале договорились по методу индукции). В итоге получаем p(n)=1/n*(1/2 n)=1/2

 

stirlitz, ну да, я согласен, что по индукции получается вполне строгое доказательство. Мне именно было интересно, как его получить без индукции. Но теперь я знаю, как это делается

 

Решите следующую задачу:

"Берется 2 колоды карт, размешиваем и открываем попарно - по одной карте из каждой колоды.
С какой вероятностью будет открыта хотя бы одна пара одинаковых карт?"

 

очень хорошая задачка, люблю ее студентам давать
Обычно еще, кроме этой вероятности, прошу посчитать мат. ожидание (это просто) и дисперсию (чуть посложнее) количества пар одинаковых карт

 

Крутые у вас студенты. Это они на экзамене делают, да еще и дают абсолютно точный ответ?

 

насчет посчитать вероятность - либо на дом задам, либо сам на лекции расскажу. А посчитать мат. ожидание и дисперсию - это можно и на экзамене