Интервью с Н.Н. Константиновым

[bravchick]

http://elementy.ru/lib/431023

Правда, ничего интересного, кроме нескольких олимпиадных задач я там не нашел. Из тех задач, которых я не знал, больше всего понравилась такая:
Каждый из N пассажиров купил по билету на N-местный самолет. Первой зашла сумасшедшая старушка и села на случайное место. Далее, каждый вновь вошедший занимает свое место,

Comments

[sasha_br]

Что-то тут все какие-то умные решения пишут -- а я вроде сразу понял, что вообще возможных рассадок есть 2^{N-1} штук (столько же сколько подмножесть
у множества из (N-1) элементоa), тем самым очевидно, что вероятность 1/2.

[bravchick]

Разные рассадки не развновероятны. Скажем, рассадка, когда все сидят на своих местах имеет вероятность 1/n.

[sasha_br]

Не понял. Пусть f(N) количество всех возможных рассадок для данного N. Очевидно что
1) Искомая вероятность есть f(N-1)/f(N)

2) f(N)=2^{N-1} (потому что рассадка полностью определяется тем подмножеством вменяемых пассажиров, которые сидят
не на своих местах).

Поэтому ответ 1/2. Я секунд 30 думал, наверное.

[sasha_br]

А, я понял, что ты имеешь в виду.
А какое формальное определение вероятности?

[sasha_br]

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

[bravchick]

с вероятностью все просто: при каждой рассадке для каждого числа k обозначим через p_k вероятность того, что после того как первые k-1 человек сели так, как они сели, k-ый человек сядет на то место, на которое он сел. Например, если его место было свободно, то p_k=1. Вероятность рассадки по определению равна произведению p_1p_2....p_n.

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

[sasha_br]

Как не понял: я построил биекцию между всеми рассадками и подмножествами множества вменяемых пассажиров.
При этом очевидно, что есть биекция между подмножествами содержащими последнего и несодержащими.

[bravchick]

Я понял, что есть биекция между подмножествами содержащими последнего и несодержащими. Но почему эта биекция сохраняет вероятность?