Замуж за иностранца

Иногда возникает ощущение, что люди делают так, чтобы им было лучше. Это простая и естественная формулировка, которая привычно пропускает один важный момент. Люди стараются сделать так, как им кажется будет лучше. И иногда им кажется правильно.

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

Давайте попробуем разобраться в такой ситуации, где не очень ясно, что известно, а что неизвестно. Возьмём для примера женатых и холостых иностранцев, которые женились друг на друге и повыходили замуж, а теперь имеют всякие хитрые взаимоотношения. Эту забавную задачку я узнал из комментария к недавней заметке об IQ тесте:

Джек женат, но любит Анну, которая влюблена в холостого Джорджа. Верно ли, что человек, состоящий в браке, любит человека, в браке не состоящего?

Варианты ответа: «Да, это так», «Нет, это не так», «Мало данных для точного ответа», «Я уже видел эту задачку, поэтому знаю ответ». Пожалуйста, оставьте своё мнение в комментариях к заметке, не читая чужих версий.

Скорее всего, в одной из следующих заметок мы разберёмся с этой задачей, а пока я предлагаю вернуться к парадоксу раздачи подарков. Поскольку меня попросили рассказать, как найти точное решение, а изложить его в комментариях не очень легко, так как оно достаточно объёмное, то посвятим этому делу вторую половину сегодняшней заметки.

Если вам не очень интересно читать длинные и подробные математические рассуждения, то предлагаю прочесть только подведение итогов - от абзаца, начинающегося словами «Уф-ф...» :)

Сразу предупрежу, что ниже предложен не самый короткий путь, потому что у меня нет цели быстро доказать, что данная формула верна. Главная задача - показать, как до неё можно дойти. Я привожу ход мыслей, который кому-то покажется корявым, а кому-то понятным, потому что все люди разные. Надеюсь, желающие смогут прорваться сквозь лишние подробности.

Итак, есть N подарков и N людей, каждый из которых получит ровно один подарок. Это значит, что есть ровно N! способов раздать подарки этим людям (первый получает один из N подарков, второй - один из (N-1) оставшихся подарков, третьему достанется один из (N-2) подарков и так далее). Перемножаем все эти независимые случаи, получаем N*(N-1)*(N-2)*(N-3)*...*2. Запомним этот результат, он нам много раз пригодится.

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

Теперь рассмотрим ситуацию, когда второй человек получил свой подарок. Оставшиеся опять могут распределить подарки X1=(N-1)! способами. Аналогично для третьего, четвёртого,... , N-ного участника. Получается, что если сложить все эти случаи, то выйдет N*X1=N*(N-1)!, что как раз равно Y1=N!. Пока всё просто, но сейчас надо осознать одну важную вещь: некоторые возможные ситуации были посчитаны несколько раз. В самом деле, случай, когда первый и второй участники одновременно получили свои подарки, учтён дважды (в первой и во второй сумме). Поэтому для получения правильного ответа необходимо из нашего результата Y1=N! один раз вычесть дважды учтённые расклады (для парных совпадений). Более того, в этот Y1=N! случаев трижды включены расклады, в которых первый, второй и третий участники одновременно получили свои подарки на руки. Такие случаи тройных совпадений надо вычесть дважды (чтобы осталось ровно одно). Дальше аналогично: четвёрки посчитаны по четыре раза, их надо вычесть трижды, пятёрки посчитаны пять раз - их надо вычесть четыре раза. И так далее. Звучит сложно, но мы вот-вот доберёмся до результата.

Давайте разберём случай, в котором двое участников получили свои подарки на руки. Оставшиеся (N-2) участника, как мы выяснили недавно, могут распределить оставшиеся (N-2) подарка ровно X2=(N-2)! способами. Выходит, надо просуммировать все эти X2 конфигурации для всех возможных пар из N участников. А таких пар может быть ровно N*(N-1)/2! (потому что порядок не имеет значения). Выходит, что таких конфигураций ровно N*(N-1)/2 * X2, что как раз равно Y2=N!/2.

Опять важно отметить, что мы несколько раз посчитали одинаковые конфигурации: например, случай, когда первый, второй и третий участники одновременно получили свои подарки, учтён 3 раза. Поэтому для получения правильного ответа из нашего результата Y2=N!/2 необходимо два раза вычесть трижды учтённые расклады. Аналогично - для четвёрок, пятёрок и так далее.

Для ясности рассмотрим следующий шаг: считаем, сколько возможно случаев, в которых трое получили свои подарки. Поскольку трёх человек из N можно выбрать N*(N-1)*(N-2)/3! способами, то получаем результат N*(N-1)*(N-2)/6, что равно Y3=N!/6. Но опять же в нём посчитаны лишние четвёрки, пятёрки... Их тоже надо будет вычесть.

Соберём получившийся «хаос»: заметим, что выражение T(N)=Y1-(Y2-(Y3-(Y4-(Y5-...)))) нам очень удобно. Оно как раз обладает замечательным свойством: многократно учтённые случаи благополучно вычитаются нужное количество раз, поэтому все возможные расклады остаются в количестве ровно одной штуки (надо посмотреть на эту строчку несколько десятков секунд, чтобы почувствовать это). Другими словами, T(N) - это как раз и есть идеальный ответ. T(N) - это количество ситуаций без повторов, в которых хотя бы один участник получил свой подарок обратно. Если из общего количества возможных раскладов N! вычесть T(N), то мы получим количество случаев, в которых никто не получил свой подарок обратно.

Подставим Yi в формулу и раскроем скобки: выходит T(N)=N!-(N!/2!-(N!/3!-(N!/4!-...)))=N!-N!/2!+N!/3!-N!/4!+N!/5!-...-(-1)^N.

Теперь найдём Z(N) - количество ситуаций, в которых каждый получил чужой подарок: Z(N)=N!-T(N)=N!/2!-N!/3!+N!/4!-N!/5!+...+(-1)^N.

Ну а теперь найдём P(N) - вероятность того, что никто не получит свой подарок обратно. Для этого надо разделить количество интересных нам элементарных исходов на количество всех возможных элементарных исходов N!.

P(N)=Z(N)/N! = 1/2! - 1/3! + 1/4! - 1/5! + ... + (-1)^N/N!.

Уф-ф... Длинно вышло. Поздравляю всех дочитавших до этого места :)
Если хотите предложить более короткое и ясное решение, то это будет очень интересно! Приглашаю в комментарии к заметке, посвящённой задачке о подарках. Вопросы о данном решении, пожалуйста, задавайте там же.

Ну а тот факт, что P(N) стремится к 1/e при N стремящемся к бесконечности, легко понять, так как разложение в ряд Тейлора функции экспонента как раз совпадает с P(N) при параметре -1 (exp(-1)=Sum{k=0..inf}(-1)^k/k!). Интересно вот что: P(N) стремится к 1/e очень быстро. Уже для семи участников P(N) приблизительно равно 0.3679 (то есть, совпадает с 1/e с точностью до четырёх знаков после запятой). Мне кажется, это вообще очень важно осознать: если вероятность каждого конкретного события всего лишь 1/N, но этих событий N штук, то вероятность того, что хотя бы одно произойдёт, получается около 2/3. То есть, хотя бы одно событие скорее произойдёт, чем ничего не произойдёт.

Если вам эта тема показалось такой интересной, что хочется прочитать ещё что-то, то рекомендую поискать статьи с распределением Пуассона в главной роли (сейчас мы рассматривали распределение с параметром λ=1). Оно известно человечеству с 1837 года - тогда Симеон Денис Пуассон издал книгу со своими размышлениями о различных последовательностях испытаний Бернулли. В то время эти исследования не нашли себе применения, но после 1894 года распределение Пуассона пригодилось при изучении одного странного феномена: германская армия анализировала статистику трагических случаев, когда солдат был убит ударом копыта. Согласно наблюдениям, 196 солдат погибли таким образом за 280 наблюдений (20 лет умножить на 14 кавалерийских корпусов). Это значит, что можно ожидать, что события будут подчинены распределению Пуассона с параметром λ=0.7. Другими словами, должно было быть 139 случаев без смерти участника, 97 наблюдений с одной смертью, 34 наблюдения с двумя смертями и так далее. Реальность оказалось такой: 140 случаев без жертв, в 91 случае был один убытый копытом, в 32 случаях - двое. Реальные наблюдения очень хорошо совпали с теоретическими размышлениями, что очень поддержало теоретиков, хотя солдат, конечно, жалко.

В реальной жизни мы сталкиваемся с распределением Пуассона почти везде. Например, если N - количество доступных телефонных линий, то число занятых линий приблизительно подчинено распределению Пуассона. Это распределение всюду вокруг нас, поэтому бывает полезно примерно понимать его природу :)

Напишите, пожалуйста, свой ответ о женатых иностранцах и замужних иностранках в комментариях, если ещё этого не сделали.

Хорошей вам недели!