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

Apr 21, 2010 13:15

http://elementy.ru/lib/431023

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

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

Leave a comment

Comments 111

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

Reply

bravchick April 21 2010, 18:53:40 UTC
Я придумал решение в один ход, но думал минут 10-15.

Reply

ny_quant April 21 2010, 19:02:41 UTC
На интервью через минуту начинают в лучшем случае задавать наводящие вопросы, а в худшем задают следущий вопрос.

Reply

bravchick April 21 2010, 19:05:14 UTC
А в чем смысл? Мне кажется, так можно только проверить знал ли клиент задачу, или нет.

Reply


nadja_s April 21 2010, 17:54:53 UTC
1/2?

Reply

vanja_y April 21 2010, 18:18:07 UTC
При N >= 2 :-)

Reply

bravchick April 21 2010, 18:52:54 UTC
Ага

Reply

nadja_s April 21 2010, 18:54:08 UTC
И правда красивая!

Reply


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

Reply

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

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

Reply

southwest April 21 2010, 20:23:34 UTC
У меня две, но я представил что я на интервью у Голдмана :)

Reply

ny_quant April 21 2010, 21:10:08 UTC
2 минуты - отличный результат для этой задачи. Попробуйте - у Вас должно получиться :)

Reply


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


nadja_s April 21 2010, 22:52:45 UTC
Напишу на всякий случай свое решение:

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

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

Reply

avzel April 21 2010, 23:12:26 UTC
Так, по-моему, лучше всего!

Reply

ile_eli May 5 2010, 13:54:50 UTC
ile_eli May 5 2010, 13:54:31 UTC

Leave a comment

Up