Задача по теории вероятностей: сумасшедшая старушка

[ggg]

В автобус дальнего следования, имеющий n мест, проданы все билеты. На каждом билете написан номер места пассажира.. Для посадки в автобус пассажиры выстроились в очередь (не обязательно по номерам билетов). Среди пассажиров есть сумасшедшая старушка, которая очень боится, что ей не хватит места. Именно поэтому она растолкала всех локтями и стоит в очереди первой. Ворвавшись в салон, она садится на первое понравившееся ей место. Нормальный пассажир садитсяна свое место, если оно не занято; если оно занято, то пассажир садится произвольным образом на любое свободное.
а) Какова вероятность, что старушка сядет на свое место?
б) Какова вероятность, что последний в очереди пассажир сядет на свое место?

В пункте а ответ $ \frac {1}{ n} $, а пункт б досчитать не могу. Есть идея использовать формулу полной группы несовместных событий. $ P(A) = P(A|H_1)P(H_1) + P(A|H_2)P(H_2) $, где A - последний в очереди пассажир сядет на свое место, $ H_1 $ - бабушка села на свое, $ H_2 $ - бабушка села не на свое место

тут $ P(A|H_1) = 1 $, $P(H_1)=\frac {1} {n}$, $P(H_2) = \frac {n-1}{n}$ однако как быть с $ P(A|H_2 ) $ ведь если она сядет на чужое место то может быть куча вариантов. Что-то не могу смоделировать. Помогите решить плз!

[мат-ламер]

А эту задачу на форуме рассматривали. Может кто даст ссылку? Попробуйте воспользоваться индукцией.

[ggg]

Да. Дайте плз ссылку или скажите как искать задачу что в поиск вводить

[mihailm]

вроде на турнире городов ее видел только там кинотеатр был, год где-то 2000 плюс минус несколько лет

[ewert]

ggg в сообщении #364496 писал(а):

то может быть куча вариантов.

Варианты будут, но вовсе не куча; в чём-то -- даже просто один.

Допустим, несколько товарищей уже сели. Назовём любое из занятых ими мест правильным, если оно соответствует номеру билета одного из уже севших (не важно куда) пассажиров. И неправильным, если соотв. билет принадлежит кому-то из ещё не севших. Текущую рассадку назовём правильной, если в ней все места -- правильные. Так вот, принципиальны два момента:

1) если в какой-то момент рассадка правильна, то она и дальше будет правильной;

2) на каждом шаге количество неправильных мест в рассадке может лишь уменьшиться (т.е. к-во неправильных мест может быть только нулём и единицей).

Это означает, что в любой возможной цепочке рассадок сначала идёт некоторое (возможно, нулевое) количество неправильных, с единственным неправильным местом в каждой, а потом -- некоторое (возможно, нулевое) количество правильных. Последнему товарищу достанется чужое место, если все рассадки в цепочке неправильны. Ну это уже считается.

[ggg]

Цитата:

Это означает, что в любой возможной цепочке рассадок сначала идёт некоторое (возможно, нулевое) количество неправильных, с единственным неправильным местом в каждой, а потом -- некоторое (возможно, нулевое) количество правильных. Последнему товарищу достанется чужое место, если все рассадки в цепочке неправильны. Ну это уже считается.

Поясните этот абзац, плз. Цепочка рассадок? Сначала идет некоторое количество неправильных (неправильных ... чего?)?

[Dan B-Yallay]

Цитата:

Последнему товарищу достанется чужое место, если все рассадки в цепочке неправильны. Ну это уже считается.

Бабка может занять место последнего пассажира, а он - сесть на бабкино место. При этом все остальные сядут правильно.

[ewert]

Текущая рассадка "правильна", если множество номеров занятых на данный момент мест совпадает со множеством номеров билетов у всех рассевшихся. Тогда все последующие пассажиры будут садиться уже на ровно свои места.

Если же она "неправильна", то расхождение между этими множествами может составлять не более одного элемента (в ту и в другую сторону, естественно). Это -- некая лемма, довольно простая. Вначале это так безусловно, а дальше -- поддерживается по индукции.

[Cash]

Всё гораздо проще. Последний пассажир сядет либо на своё место, либо на чужое.
А значит искомая вероятность равна $1/2$
Если серьезно, то подумайте - какие места могут быть свободны перед посадкой последнего пассажира?

[ggg]

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

[TOTAL]

Бабка с вероятностью $1/n$ садится на своё место, либо на место $k$-го пассажира, превращая его в бабку.
Отсюда $P_n=\frac{1}{n}+\frac{1}{n}(P_{n-1}+P_{n-2}+ \cdots + P_{2})$
Поэтому $P_n=P_{n-1}=P_{n-2}= \cdots = P_{2}=\frac{1}{2}$

[ewert]

Cash в сообщении #364622 писал(а):

Если серьезно, то подумайте - какие места могут быть свободны перед посадкой последнего пассажира?

Либо его личное, либо любое другое. Притом заранее не известно с какой вероятностью.

TOTAL в сообщении #364689 писал(а):

либо на место $k$-го пассажира, превращая его в бабку.

Ну это понятно, а дальнейшая логика -- нет. С какой стати все вероятности одинаковы -- да и с какой стати складываются-то?

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

Конечно, спорить с тем, что ответ 1/2 -- трудно. Однако аргументация -- непонятна.

[Cash]

Цитата:

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

Цитата:

Либо его личное, либо любое другое. Притом заранее не известно с какой вероятностью.

Ответ неправильный.
Свободное место может быть либо только его, либо старушки.
Если какое-то другое, то возникает вопрос - почему его не занял пассажир с билетом на это место?
Дальнейшее мне кажется уже очевидно...

[ggg]

Запутался.


Cash, по Вашей логике: последнее свободное место будет за последним пассажиром, если старушка села не на его место. Если она села на его место, то он не сможет на свое место.
Вероятность, что она сядет не на его место $\frac {n-1}{n}$ и в таком случае это и будет вероятностью того, что последний сядет на свое место. Но это ведь неправильный ответ.

[Cash]

ну почему же его место может занять только старушка? Его место может занять любой(!) из предыдущих. Я лишь утверждал про свободные места.