Блог им. imagic

Остаться в живых (или когда последние становятся первыми)

October 26, 2021

Какой шаг самый трудный на шатком мосту? Первый или последний? Тот, что я сделаю прямо сейчас,  ведь только его я могу выбрать. А первый шаг может стать для меня и последним (неизвестный даос)
«Твой номер шестнадцатый, помалкивай в трубочку! Ясно?!» из к/ф «Место встречи изменить нельзя»


В седьмой серии культового сериала “Игра в Кальмара” герои приняли участие в испытании “Хрустальный мост через реку” Каждая из ступеней (панелей) этого моста представляла собой две стеклянных пластины, одна из закалённого стекла, а другая  — из обычного. Всего таких ступеней было 18, а участников игры, оставшихся в живых к этому моменту  — 16.

Остаться в живых (или когда последние становятся первыми)


Перед началом игроки выбрали свои порядковые номера, еще не догадываясь о том, что их ждёт впереди. Ужас и растерянность, охватившие мужчину, которому выпало стать первопроходцем, совершенно понятны — число возможных траекторий составляет для него 2 в 18-ой степени, и только в одном случае ему удастся пройти весь путь невредимым. Это один шанс из 262144.

Остаться в живых (или когда последние становятся первыми)



Сделаем несколько общих замечаний. Игра устроена таким образом, что каждый участник торит дорожку для того, кто идет за ним, и даже если он в какой-то момент наступит на хрупкую пластинку, то «разблокирует» эту панель для следующего в очереди. Мы считаем, что все игроки запоминают «ходы», сделанные их предшественниками. Следовательно, игрок с номером n может быть уверен, что как минимум первые n-1 ступеней станут для него открытой книгой, т.е. он пройдет их со стопроцентной вероятностью. А если этому игроку удастся дойти до последней панели, мост автоматически пройдут и все последующие N-n участников. Самые высокие шансы выжить у последнего игрока (и об этом догадывается любой партизан, прогоняющий стадо коров через минное поле, прежде чем его перейти) Но насколько они велики? И каково ожидаемое число уцелевших игроков?


Легко заметить, что вероятность пройти мост для самого последнего игрока совпадает с вероятностью выживания хотя бы одного участника. А значит она равна 1 — P(0), где P(0) — вероятность того, что погибнут все. Легче всего рассчитать вероятности, если число панелей M равняется общему количеству игроков N (мы не рассматриваем случай, когда  N > M, так как в этом случае очевидно, что вероятность выжить для последних N — M     игроков равна единице). Несмотря на то, что наши «испытания» существенно зависимы, т.е. вероятность пройти мост для каждого из героев зависит от результата предшественников, можно показать, что в случае M=Nчисло выживших участников подчиняется биномиальному распределению  B(N,p)с вероятностью успеха  p=1/2.


Для этого удобно предварительно рассмотреть события того, что ровно k игроков будут устранены из игры к моменту ее завершения. При условии, что провалились k ≤ M игроков, существует C(M, k) способов распределить k разбитых стеклянных пластин среди M панелей, а вероятность любой отдельной комбинации равна (1/2)ᴹ (здесь мы применяем теорему умножения вероятностей зависимых событий) Затем мы воспользуемся симметрией биномиального распределения при p = 1/2.


Оказывается, что шансы для последнего номера невероятно растут с увеличением общего количества игроков (и числа панелей, соответственно) Для 16-ти игроков и 16-ти ступеней эта вероятность очень близка к 1, она равна 0.9999847. Среднее число выживших в этом случае равно N/2, т.е. 16/2=8. Это немало.

 

Если панелей больше, чем игроков (M>N), распределение вероятностей числа «победителей» можно рассчитать, используя рассуждения, аналогичные тем, что мы проводили с игроками-неудачниками.

В этом случае вероятность того, что выживут ровно n участников равна

                      P(n) = C(M, N — n)(1/2)ᴹ   если   0<n≤N;

          P(n) = sum{j=N to j=M} [C(j-1,N-1)(1/2)ʲ]   если   n =0.

 

Мы видим, что с увеличением количества панелей картина становится чуть менее радужной, но для 18 (и даже 24) ступеней шансы последнего участника победить всё равно остаются очень высокими, и он выживет с вероятностью свыше 90%.

 

На рис. 1 показаны примеры распределения числа выживших игроков для 16-32 панелей, где точками обозначены вероятности, что мост пересекут ровно n игроков. Видно, что с ростом числа панелей центр распределения едет влево, и его левый хвост наливается кровью разбившихся жертв.

 Остаться в живых (или когда последние становятся первыми)


 

 

Вероятность выживания для участника с номером n это кумулятивная вероятность того, что   n — 1 остальных будут устранены из игры, т.е. это сумма Q(0) +...Q(n-1), где Q(i) — вероятность того, что погибших окажется ровно i. Из рис. 2 видно, что даже если число панелей вдвое превышает общее количество игроков, вероятность выживания для последнего номера составляет немногим менее 50%

Остаться в живых (или когда последние становятся первыми)

 

На последнем рисунке представлена зависимость среднего числа E(n) выживших от количества стеклянных панелей:

Остаться в живых (или когда последние становятся первыми)


Например, для 18 панелей (как это устроено в сериале) матожидание практически равно 7. Это почти в два раза больше числа спасшихся в 7-й серии (их оказалось 3 человека) Такая разница легко объясняется несовершенным поведением людей в сериале: часть забывала путь, по которому уже прошли другие, а кто-то решил покончить с собой и прихватить на тот свет своего врага.

 
Игра «Хрустальный мост через реку» крайне несправедлива — участник с большим номером имеет лучшие шансы на выживание. Но можно провозгласить социализм и ввести уравниловку. Дело в том, что одна закалённая пластина может выдержать вес двух игроков. Поэтому игроки могут пропускать очередь вперёд: например, если 1-й номер прыгнул и не разбился, он приглашает на свою пластину номер 2 и уже тот прыгает на следующую панель. Если не разбился и он, приглашается 3-й, который перепрыгивает 1-ю и 2-ю закаленную пластины, чтобы «проверить» 3-ю. Таким образом, первые в очереди игроки получают равные шансы на выбывание. Понятно, что в реальной игре на такое никто не согласится. Или же свое место в очереди можно продать? Какова стоимость места для игрока с номером n, если он нейтрален к риску? Предлагаю читателю самостоятельно поразмыслить над этой несложной проблемой.

★8
19 комментариев
зачем в оффтоп то?
Тимофей Мартынов, Ну мало ли)
avatar
DR. LECTER, да ты че, прикольный пост такой
DR. LECTER, твой пост похоже еще и 5000 рублей заработал)
Тимофей Мартынов, это боты накрутили или произошло народное признание?  
avatar
DR. LECTER, не знаю, никто не крутил😁
х.з. чё делать… то ли забанить автора, то ли застрелиться… не, куплю-ка я йену
avatar
Топик гораздо интереснее и полезнее большинства тут публикуемых.
avatar
darkcorp, ага
Тимофей Мартынов, очень симпатизирует тот факт, что пост признан победителем в конкурсе. Значит, на СЛ еще не все потеряно :)
avatar
Какова стоимость места для игрока с номером n, если он нейтрален к риску? 

Тут точнее сказать нейтрален к смерти))
avatar
Спойлеры, в бан его!
avatar
учтена ли вероятность сделать 2 и более угадываний подряд?
Логарифм Интегралыч, вы знаете теорию вероятностей?
avatar
вопросом на вопрос: могут ли делать 3 успешных хода подряд?

очевидно в теме ходы успешные подряд «случайно» забыты
Логарифм Интегралыч, если отвечать кратко, то конечно же «всё включено» И два, и три и все вместе подряд. Это учитывается биномиальными коэффициентами (они как бы впитывают в себя перебор всех этих вариантов) В этом и состоит прелесть комбинаторики.
avatar
по моим данным: 16 участников сделают 26 ходов
плюс-минус 2 хода

значит теоретически на 19-ю клетку попадут 7
однако посчитано за 5 минут и нужна визуализация

секретная визуализация эксцель показала: 4 дошли
ни разу 3-жды не угадав

значит угадав хоть раз 3-жды подряд как пишу час назад: дойдут 5

теги блога Рахманинов

....все тэги



UPDONW
Новый дизайн