о старушке и диме флаассе

[avva]

Есть хорошо известная - в узких кругах любителей математических задач - задача про "сумасшедшую старушку", которая звучит так

Comments

[re_camcew]

Задача решается следующим практическим образом.
Как её решил мой дед в 87году.
Нужно было срочно летом перелететь из Иркутска в Мин-Воды, билетов естественно нет, в кассы очередь в километр.
Ну, с очередью легко,- прошёл как ветеран войны, кассирша ему,- билетов нет, он,- дайте на любое число, и с этим билетом идёт на посадку, спокойно проходит контроль и садится в самолёте на первое подвернувшееся ему место.
До самых Мин-Вод его никто не побеспокоил.
Вот так нужно чисто конкретно решать задачи с тремя классами церковно-приходской и с тремя войнами за спиной.

[serge_kond]

Сейчас не прокатит. Автоматика проверяет всё практически. Только на подсадку, если нет овербукинга.

[re_camcew]

Это ещё чё, он до 75года вообще с наганом в кармане летал, пока не потерял по пьянке, и опять вовремя, на посадке позднее уже стали через рамки пропускать.
Так что старички они были ещё те старички.

[olegnet]

Это видимо как-то связано с системами бронирования того времени, которые оставляли какие-то места "про запас". У меня есть многократный опыт поездок в 90е из одного уральского города к морю.
Поскольку купить на любой поезд из этого города билет от Москвы было нельзя, покупали на один из тех, на который продавали, а в Москве на Курском вокзале была касса, где билеты можно было без проблем поменять (летом! к морю!) и не ждать в Москве до вечера своего поезда.

[ants_aunt]

У меня получилось, что шансы последнего не получить своё место стремятся к 1%.

[livelight]

Как только хоть один не-последний пассажир займёт по рандому место той старушки - на этом всё устаканится для всех последующих. То есть, с вероятностью ровно 1% последнее незанятое место окажется местом той самой старушки, и последнему пассажиру придётся сесть не на своё место, а на него.

[rezkiy]

Смотрите, с вероятностью 1% старушка сразу же займет место последнего пассажира. В 98% случаев она займет что-то ещё, и тот другой пассажир тоже может занять место последнего. То есть 1% явно мало.

[livelight]

Проверил Монте-Карлой-Марлой, получилось 50%.
Там ниже это математически обосновали.

[norian]

та же, что встретить на улице жывого динозавра - 50%

[firanx]

Обратная индукция. Пусть P(n) - вероятность последнего пассажира сесть на свое место при общем числе мест в салоне n. P(2) = 1/2, P(n) = 1/n [старушка села на свое место] + 0 [старушка села на место последнего пассажира] + Σ_{1 < k < n} P(k) / n [k - номер в очереди пассажира, чье место она заняла]. Если P(k) = 1/2 для всех k, 1 < k < n, то P(n) = 1/n + 1/2 * (n-2)/n = 1/2.

[trump_donald]

Простите, а почему P(2) = 1/2 ?
Вероятность второго пассажира сесть на свое место равна 1 минус вероятность того, что старушка сядет на его место - 0.01.
Итого - 0.99

[0242]

n в P(n) - это не номер пассажира, а число мест

Совершенно верно.

[clovis3]

Я тоже так решил: посчитал P(2), потом P(3) и P(4), и возникла гипотеза, что P(n) = 1/2, если n>1, а уж дальше, конечно, индукция, потому что если старушка села на место k-того пассажира из очереди, то перед ним все сядут на свои места, а этот k-тый пассажир, сам окажется "старушкой". Но поздно добрался до ЖЖ. В общем, задача нетрудная.

[mr_numeraire]

Задачка наоборот. Про строгую старушку (в оригинале был "жлоб", в автобусе). Первые 99 absent-minded пассажиров заполняют самолет случайно, не глядя что там у них в билете. Последняя - наша старушка, и она (вполне законно) хочет сидеть на своем месте. Если оно свободно, отлично. Если нет, то согнанный пассажир теперь все-таки посмотрит на свой билет и пойдет к своему сидению. Если оно свободно, отлично. Если нет, то тогда второй пассажир пойдет искать свое место. И т. д. Вопрос. Вы - один из этих первых 99 оболтусов. Какого верятность, что вас тоже заставят пересесть?

[stanislav_demba]

Еще один вариант той же задачи - n-ый посетитель ресторана генерирует случайное число от 1 до n, если выпало k

[onodera]

А вот тут звучит неочевидно, начинают мерещиться циклы, которые могут не достать и т.п.

Две места, вероятность пересесть 50%

Три места:

- 1/3 вероятность, что всё норм.
- 1/3 вероятность, что старушка подошла к нашему месту
- 1/3 вероятность, что старушка подошла к месту третьего пассажира, пассажир превращается в старушку, а задача в задачу про два места

Четыре места:
- 1/4 вероятность, что всё норм
- 1/4 вероятность, что старушка подошла к нашему месту
- 1/2 вероятность, что старушка подошла к другим пассажирам, пассажир превращается в старушку, а задача в задачу про три места

[mr_numeraire]

Если вы согласны с stanislav_demba, что все что нам надо, это посчитать перестановки, где 1 и 2 в одном цикле, то проверка для n=3, 4 легко делается руками. Он так же прав, что самое простое решение не требует ни комбинаторики, ни индукции. Записываете перестановки как произведение циклов, ведущий элемент цикла - самый маленький элемент в цикле, циклы записывате в порядке возрастания ведущих элементов. Тогда биекция - просто стирание скобок перед 2. Например, (13)(2) становится (132), (1)(2)(3) - (12)(3).