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

Apr 21, 2010 13:15

http://elementy.ru/lib/431023

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

задачки, интервью

Leave a comment

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

Reply

bravchick April 21 2010, 21:24:12 UTC
Разные рассадки не развновероятны. Скажем, рассадка, когда все сидят на своих местах имеет вероятность 1/n.

Reply

sasha_br April 21 2010, 21:32:45 UTC
Не понял. Пусть f(N) количество всех возможных рассадок для данного N. Очевидно что
1) Искомая вероятность есть f(N-1)/f(N)

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

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

Reply

sasha_br April 21 2010, 21:41:35 UTC
А, я понял, что ты имеешь в виду.
А какое формальное определение вероятности?

Reply

sasha_br April 21 2010, 22:10:39 UTC
Что такое верятность я действительно не понимаю, но в любом случае вышеуказанное рассуждение влечёт биекцию между плохими и хорошими рассадками
(добавить последнего к подмножеству или вынуть его оттуда), про которую, видимо, очевидно, что она сохраняет вероятности, так что рассуждение
остаётся в силе.

Reply

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

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

Reply

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

Reply

bravchick April 22 2010, 12:43:01 UTC
Я понял, что есть биекция между подмножествами содержащими последнего и несодержащими. Но почему эта биекция сохраняет вероятность?

Reply


Leave a comment

Up