Вероятности и подарки

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

Какие рассуждения при этом используются?

Если у нас N участников и N подарков, то вероятность того, что лично мне достанется тот же подарок, что я положил под ёлку, равна 1/N (и это же можно сказать про остальных людей). Чем больше N, тем меньше вероятность вытянуть своё же (и при N стремящемся к бесконечности эта вероятность вообще стремится к нулю). Поэтому в больших группах очень мало шансов, что кто-то уйдёт со своим же подарком.

Недавно мы уже говорили о том, что словами «бесконечность» и «предел» нужно пользоваться очень осторожно, чтобы не обмануть самого себя. А про любые «очевидные» логические переходы надо уметь в течение 30 секунд детально и корректно объяснить, почему они очевидны. Но сегодня я предлагаю начать с обратной стороны: поставить эксперимент.

Проще всего для этого воспользоваться языком программирования javascript, потому что он есть под рукой почти у всех читателей (да и традицию не будем нарушать). Создайте файл presents.html со следующим содержимым и откройте его браузером:

<script type="text/javascript">
N = 100;     // quantity of presents (and participants)
nbIt = 1000; // quantity of iterations
okIt = 0;    // OK situaions
for (iter = 0; iter < nbIt; iter++) {
  var a = new Array(N); // create array
  for(i=0; i<N; i++)
    a[i] = i; // fill it by numbers 0, 1, 2,... , N-1

  // shuffle array
  i = N;
  while(i) {
   j = Math.floor( (i--) * Math.random() );
   t = a[i];
   a[i] = a[j];
   a[j] = t;
  }

  // calculate number of self-presents
  selfp = 0;
  for(i=0; i<N; i++)
    if (a[i] == i)
      selfp++;

  if (selfp == 0) // if there are no self-presents
    okIt++;       // increase OK-counter
}

document.write('Probability of OK-situation: ' + (100*okIt/nbIt) + '%');
</script>

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

Оказывается, что только примерно в трети случаев каждый участник эксперимента получает что-то новое, а в остальных ситуациях кто-то оказывается не очень довольным. Попробуйте увеличить или уменьшить количество участников (конечно, не делая его слишком малым - больше 5 уже достаточно). Результат всё равно будет больше похож на температуру (потом мы поймём, что он колышется вокруг 36.8%).

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

Зачем это надо? Для калибровки своей интуиции! Редкий человек обладает достаточной дисциплиной ума, чтобы проверять каждый шаг всех выкладок. Иногда приходится полагаться на ощущение «это верное утверждение, потому что оно не может быть ошибочным»... Но чтобы чего-нибудь достичь, позволяя себе такие вольности, необходима тренированная интуиция, а не умение переспорить. Эти глубокие интуитивные шаги необходимы, чтобы не погрязать в рутине маленьких простых этапиков в размышлениях, а сразу выделять важные и серьёзные идеи (которые потом, конечно, надо будет детально обосновать, если они покажутся интересными).

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