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

[bravchick]

http://elementy.ru/lib/431023

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

Comments

[ny_quant]

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

[bravchick]

Я придумал решение в один ход, но думал минут 10-15.

[ny_quant]

На интервью через минуту начинают в лучшем случае задавать наводящие вопросы, а в худшем задают следущий вопрос.

[bravchick]

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

[nadja_s]

1/2?

[vanja_y]

При N >= 2 :-)

[bravchick]

Ага

[nadja_s]

И правда красивая!

[southwest]

По-моему очень просто сразу видно что 1/2. При N=2 очевидно. Дальше по индукции. Рассмотрим второго пассажира, если он садится на своё место, то задача сводится к (N-1), если его место занято старушкой, то он сам теперь играет роль сумасшедшей старушки и задача опять сводится к (N-1) с такой же вероятностью.

[bravchick]

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

Беда в том, что у меня минут 10-15 ушло на то, чтобы это рассуждение придумать.

[southwest]

У меня две, но я представил что я на интервью у Голдмана :)

[ny_quant]

2 минуты - отличный результат для этой задачи. Попробуйте - у Вас должно получиться :)

[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]

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

[nadja_s]

Напишу на всякий случай свое решение:

Вер(последний сядет на свое место)
=Вер(кто-то из остальных сядет на место старушки)
=Вер(кто-то из остальных сядет на место последнего)
=1-Вер(последний сядет на свое место)

Средний шаг - потому что и для старушки, и для пассажиров 2, ..., N-1 место старушки и место последнего пассажира симметричны.

[avzel]

Так, по-моему, лучше всего!

[ile_eli]

то же самое, что и http://bravchick.livejournal.com/43889.html?thread=1071985#t1071985

[ile_eli]

то же самое, что и http://bravchick.livejournal.com/43889.html?thread=1071985#t1071985