В очередь на посадку в 100-местный самолет выстроилось 100 пассажиров — в случайном порядке. Все места забронированы. Из-за технической неполадки первый пассажир получает возможность занять любое из 100 мест. Второй занимает свое место; если оно занято, выбирает любое из оставшихся. Остальные поступают аналогично. Какова вероятность, что последний пассажир займет свое, забронированное им место?
Эта задача (в ином переложении в ней фигурирует сумасшедшая старушка) — популярный вопрос на собеседованиях, которым проверяется понимание кандидатами теории вероятностей, рекурсии и методов решения задач. Он часто задается в технологических и финансовых компаниях, где востребованы аналитические способности: в Google, Facebook, Amazon, а также хедж-фондах и инвестиционных банках.
Мало найти правильный ответ — нужно объяснить, как он получен. Попробуйте сначала решить задачу самостоятельно.
Решение
Удивительно или очевидно — кому как, искомая вероятность равна 1/2. Разберемся почему.
Сначала упростим обозначение сидений, пронумеровав их от 1 до 100.
1-й пассажир выбирает любое место, обозначим это место как j¹, где 1 — это 1-й пассажир. Второй пассажир занимает:
- (a) место 2, если оно свободно, т. е. j¹≠2;
- (б) другое место, если место 2 занято 1-м пассажиром, т. е. j¹=2.
В случае (а) с каждым следующим пассажиром количество свободных мест уменьшается на одно, потому что 2-й пассажир занял свое место и о нем можно забыть. Хотя 1-й выбирает любое место, дальше логика та же: каждый пассажир, начиная с 3-го, займет забронированное им место либо, если оно уже занято, — другое, незанятое место.
В случае (б) места 1 и 100 остаются незанятыми и включаются как возможные варианты выбора 2-го пассажира. Другие свободные места — с 3 по 99 — не сказываются на результате так, как места 1 и 100. Почему? Если 2-й пассажир займет, например, место 42, все остальные пассажиры, кроме 42-го, смогут занять забронированные ими места. Когда очередь доберется до 42-го пассажира, ситуация повторится: его место занято, а место 1 и места с 43 по 100 останутся свободными. И снова возвращаемся к случаю (б), только пассажиров меньше. Сколько бы ни повторялся этот случай, места 1 и 100 по-прежнему свободны. Акцентируем на них внимание.
И заметим: какие бы места ни занимали пассажиры мест 2–99, место 1 или место 100 рано или поздно будет занято. Когда это случится, останется два варианта:
- Если выбрано место 100, последнему пассажиру останется место 1. Все остальные пассажиры до 100-го займут забронированные ими места.
- Если выбрано место 1, цикл замкнулся: 1-й и последний пассажиры меняются местами. Все последующие пассажиры займут забронированные ими места, в том числе последний пассажир № 100.
Эти два исхода равновероятны из-за симметрии задачи: каждый пассажир имеет равные шансы занять любое место, если его место занято. Поэтому вероятность того, что последний пассажир займет забронированное им место 100, равна ровно 1/2. Более того, в оставшейся 1/2 случаев он займет место 1-го пассажира.
Читайте также:
- Если вы застряли между этажами: как алгоритм лифта заставляет нас бесконечно ждать
- Добыча данных: анализ рыночной корзины с помощью алгоритма Apriori
- Структуры данных: основы алгоритмов
Читайте нас в Telegram, VK и Дзен
Перевод статьи Paolo Molignini, PhD: Can you solve this famous interview question?
