17. Решение задачи о рыцарях-близнецах

(а). Обозначим близнецов через A к B. Пусть A занимает высшую ступень турнирной лестницы. Если B занимает смежное место, что происходит с вероятностью 1/7, то они заведомо встретятся в первом туре. Вероятность того, что B находится в паре, соседней с парой A, равна 4/7, и вероятность того, что они встретятся в этом случае, равна 1/7, так как для осуществления этого события каждый должен победить в первом поединке. Наконец, вероятность того, что B находится в нижней половине, равна 4/7, и в этом случае вероятность встречи равна 1/2⁴ = 1/16, так как оба должны выиграть в двух турах. Таким образом, полная вероятность встречи равна

(б). Заметим, что в турнире двух рыцарей близнецы заведомо встретятся. При 2? = 4 участниках вероятность такого поединка равна ?, для случая 2? = 8 рыцарей, как уже было подсчитано, вероятность равна 1/4 = 1/2ⁿ. Кажется естественным предположить, что в турнире 2ⁿ рыцарей искомая вероятность равна 1/2^{n ? 1}.

Докажем справедливость этого предположения с помощью метода математической индукции. Рассмотрим сначала случай, когда рыцари находятся в разных половинах турнирной лестницы. Как известно из задачи о теннисных турнирах, эта вероятность равна 2^{n ? 1}/(2ⁿ ? 1). Если A и B находятся в разных половинах турнирной лестницы, то они могут встретиться лишь в финальном поединке. Вероятность выйти в финал для каждого рыцаря есть 1/2^{n ? 1}, так как для осуществления этого события необходимо выиграть во всех предыдущих турах. Вероятность того, что A и B достигнут финала, равна (1/2^{n ? 1})? = 1/2^{2n ? 2}. Итак, вероятность встречи рыцарей из разных половин таблицы равна

[2^{n ? 1}/(2ⁿ ? 1)]·(1/2^{n ? 2}).

К этой вероятности следует прибавить вероятность поединка близнецов, которые оказались записанными в одну и ту же половину таблицы. Вероятность последнего события равна (2^{n ? 1} ? 1)/(2ⁿ ? 1), и, согласно индукционному предположению, вероятность схватки между близнецами в турнире из n ? 1 тура равна 1/2^{n ? 2}. Итак, вероятность встречи равна

что и доказывает наше утверждение.