Кто пылесосит по ночам?

Представьте, что каждую ночь вы слышите не стук перфоратора, не уроки игры на пианино, не весёлую пьянку (потому что живёте в хорошем доме, жильцы которого отличаются повышенной вменяемостью), а... работающий пылесос. Вроде бы никто новый в дом не вселился, но почему-то один из соседей внезапно начал пылесосить каждую ночь примерно с 2:00 до 2:30. Нельзя сказать, что это нестерпимо громко, так как спать особо не мешает. Но интригу-то создаёт! Как тут спокойно уснёшь, если шесть месяцев каждую ночь повторяется одна и та же загадка — что они делают пылесосом по ночам? А через полгода всё прекратилось, как будто и не было ничего. И даже не понятно, кого спросить о причине странных ночных звуков.

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

Ну а если вы любите ясные формулировки, не подразумевающие нескольких толкований, то следующая математическая часть заметки для вас. Вернёмся к последней задачке об общей цели группы людей. Напомню, что вопрос был в том, с какой вероятностью группа из 2N человек побеждает в игре, если все люди умные и умеют договариваться. Другими словами, надо предъявить функцию P(N), которая описывает вероятность победы группы, а также доказать, что группа не может действовать лучше.

В самой заметке мы доказали, что P(1) = 1/2. Более того, для N>1 очевидно, что P(N) <= 1/2 (так как первый игрок не может обеспечить вероятность выше, чем 1/2, а остальные игроки выше 100% тоже не прыгнут.

Легко понять, что P(N) >= 1/2^(2N), так как каждый игрок, если будет действовать случайным образом, вытянет свой номер с вероятностью 1/2, а всего участников 2N. Так мы сделали оценку снизу.

Далее в комментариях к заметке было предложено несколько подходов для игроков:
- сначала открывать коробочку со своим номером на борту, а дальше (пока не нашёл табличку со своим номером) открывать коробочку с тем номером, который был на табличке из прошлой коробочки. Это интересный способ, но как было показано в комментариях ниже, если в нашей перестановке есть циклы, то игроку придётся открывать одни и те же коробочки несколько раз, что, очевидно, неэффективно.
- ещё можно игрокам с чётными номерами открывать только чётные коробочки, а игрокам с нечётными номерами — только нечётные коробочки.
- очень похожий подход: чётные игроки открывают коробочки с 1 по N, а нечётные — с N+1 до 2N.

Можно нафантазировать ещё несколько подходов, но что с ними делать дальше? Надо научиться корректно считать вероятность победы для предложенных стратегий. Давайте определимся, что такое вероятность победы группы в этой игре.

Определим функцию вероятности победы P(N, S), где S — стратегия группы из 2N игроков:
P(N, S) = W(N, S) / C(N).
В этой формуле W(N, S) — это количество побед для группы из 2N человек, пользующихся стратегией S, на всех возможных входных данных (наборах табличек в коробочках). А C(N) — это количество всех возможных входных данных (т.е. количество способов поместить 2N разных табличек в 2N разных коробочек). Здесь мы исходим из того, что размещение табличек по коробочкам является полностью случайным (т.е. мы можем считать, что все эти элементарные события равновероятны).

Как определиться C(N)? Очень легко — C(N) = (2N)! (т.е. 2N(2N-1)(2N-2)(2N-3)...3*2*1). Это одна из первых формул, которую доказывают студенты, начинающие заниматься комбинаторикой.

А как определить W(N, S)? Простейший способ — честно посчитать. Надо всего лишь проверить для всех перестановок, позволяет ли стратегия S выиграть всей группе (за каждый случай победы надо увеличивать W на единицу).

Давайте, например, разберёмся с этой задачкой для N=2 (раз уж с N=1 мы всё поняли в прошлой заметке):
C(2) = 4! = 24. Действительно, у нас есть следующие 24 перестановки табличек в коробочках:
1234,
1243,
1324,
1342,
1423,
1432,
...
...
4312,
4321.

Теперь для каждой стратегии S, которую мы хотим проверить, надо попробовать её применить на всех 24 возможных входных данных. Соответственно, вероятность P(2, S) = W(2, S) / 24.

Зачем все эти сложности? Во-первых, далеко не все задачи получается решить сразу в общем виде. Часто бывает эффективно поиграть с частными случаями, чтобы лучше понять суть. Во-вторых, в теории вероятностей есть масса тонкостей, поэтому очень легко допустить ошибку в рассуждениях (особенно, если не иметь регулярной практики решения вероятностных задач). А предложенный подход хоть и требует аккуратности при переборе случаев, но позволяет избавиться от ошибок в рассуждениях о вероятностях, что на начальном этапе очень нужно.

Далее, имея в руках какие-то надёжно насчитанные равенства и неравенства, можно будет увереннее продвигаться в решении этой задачки. Предлагаю в комментариях к этой заметке добить случай N=2, чтобы в скором времени попробовать ответить на вопрос: если N стремится к бесконечности, то P(N) стремится к нулю? И если не к нулю, то к чему?

Пользуясь случаем, удивлюсь малому количеству ответов к задачке о выворачивании кубика. Что случилось? Вы не пьёте молоко и соки? Или не имеете ножниц, бумаги и скотча? ;) Задачка же хорошая! А пропадает почему-то...

Хороших выходных!