Разделы 
Дополнительно
Задача по математике - 3870
2019-06-23 
(а) Король Артур проводит рыцарский турнир, в котором, так же как и в теннисе, порядок состязания определяется жребием (см. задачу 3869) Среди восьми рыцарей, одинаково искусных в ратном деле, два близнеца. Какова вероятность того, что они встретятся в поединке?
(б) Каков ответ в случае $2^n$ рыцарей?
Решение:
(а) Обозначим близнецов через $A$ и $B$. Пусть $A$ занимает высшую ступень турнирной лестницы. Если $B$ занимает смежное место, что происходит с вероятностью $\frac{1}{7}$, то они заведомо встретятся в первом туре. Вероятность того, что $B$ находится в паре, соседней с парой $A$, равна $\frac{4}{7}$, и вероятность того, что они встретятся в этом случае, равна $\frac{1}{7}$, так как для осуществления этого события каждый должен победить в первом поединке. Наконец, вероятность того, что $B$ находится в нижней половине, равна $\frac{4}{7}$, и в этом случае вероятность встречи равна $ \frac {1}{2^4} = \frac{1}{16}$ так как оба должны выиграть в двух турах. Таким образом, полная вероятность встречи равна
$\frac{1}{7} \cdot 1 + \frac{2}{7} \cdot \frac{1}{4} + \frac{4}{17} \cdot \frac{1}{16} = \frac{1}{4}$.
(б) Заметим, что в турнире двух рыцарей близнецы заведомо встретятся. При $2^2 = 4$ участниках вероятность такого поединка равна $\frac{1}{2}$, для случая $2^3 = 8$ рыцарей, как уже было подсчитано, вероятность равна $\frac{1}{4} = \frac{1}{2^2}$. Кажется естественным предположить, что в турнире $2^n$ рыцарей искомая вероятность равна $ \frac {1}{2^{n - 1}}$.
Докажем справедливость этого предположения с помощью метода математической индукции. Рассмотрим сначала случай, когда рыцари находятся в разных половинах турнирной лестницы. Как известно из задачи о теннисных турнирах, эта вероятность равна $ \frac {2^{n - 1}}{2^n - 1}$. Если $A$ и $B$ находятся в разных половинах турнирной лестницы, то они могут встретиться лишь в финальном поединке. Вероятность выйти в финал для каждого рыцаря есть $ \frac {1}{2^{n - 1}}$, так как для осуществления этого события необходимо выиграть во всех предыдущих турах. Вероятность того, что $A$ и $B$ достигнут финала, равна $( \frac {1}{2^{n - 1}})^2 = \frac {1}{2^{2n - 2}}$. Итак, вероятность встречи рыцарей из разных половин таблицы равна
$ \frac {2^{n - 1}}{2^n - 1} \cdot \frac {1}{2^{2n - 2}}$.
К этой вероятности следует прибавить вероятность поединка близнецов, которые оказались записанными в одну и ту же половину таблицы. Вероятность последнего события равна $ \frac {2^{n - 1} - 1}{2^n - 1}$, и, согласно индукционному предположению, вероятность схватки между близнецами в турнире из $n-1$ тура равна $\frac {1}{2^{2n - 2}}$. Итак, вероятность встречи равна
$ \frac {2^{n - 1}}{2^n - 1} \cdot \frac {1}{2^{2n - 2}} + \frac {2^{n - 1} - 1}{2^n - 1} \cdot \frac {1}{2^{n - 2}} = \frac {1}{(2^n - 1) 2^{n - 2}} \left ( \frac{1}{2} + 2^{n - 1} - 1 \right ) = \frac {1}{2^{n - 1}}$,
что и доказывает наше утверждение.
(а) Король Артур проводит рыцарский турнир, в котором, так же как и в теннисе, порядок состязания определяется жребием (см. задачу 3869) Среди восьми рыцарей, одинаково искусных в ратном деле, два близнеца. Какова вероятность того, что они встретятся в поединке?
(б) Каков ответ в случае $2^n$ рыцарей?
Решение:
(а) Обозначим близнецов через $A$ и $B$. Пусть $A$ занимает высшую ступень турнирной лестницы. Если $B$ занимает смежное место, что происходит с вероятностью $\frac{1}{7}$, то они заведомо встретятся в первом туре. Вероятность того, что $B$ находится в паре, соседней с парой $A$, равна $\frac{4}{7}$, и вероятность того, что они встретятся в этом случае, равна $\frac{1}{7}$, так как для осуществления этого события каждый должен победить в первом поединке. Наконец, вероятность того, что $B$ находится в нижней половине, равна $\frac{4}{7}$, и в этом случае вероятность встречи равна $ \frac {1}{2^4} = \frac{1}{16}$ так как оба должны выиграть в двух турах. Таким образом, полная вероятность встречи равна
$\frac{1}{7} \cdot 1 + \frac{2}{7} \cdot \frac{1}{4} + \frac{4}{17} \cdot \frac{1}{16} = \frac{1}{4}$.
(б) Заметим, что в турнире двух рыцарей близнецы заведомо встретятся. При $2^2 = 4$ участниках вероятность такого поединка равна $\frac{1}{2}$, для случая $2^3 = 8$ рыцарей, как уже было подсчитано, вероятность равна $\frac{1}{4} = \frac{1}{2^2}$. Кажется естественным предположить, что в турнире $2^n$ рыцарей искомая вероятность равна $ \frac {1}{2^{n - 1}}$.
Докажем справедливость этого предположения с помощью метода математической индукции. Рассмотрим сначала случай, когда рыцари находятся в разных половинах турнирной лестницы. Как известно из задачи о теннисных турнирах, эта вероятность равна $ \frac {2^{n - 1}}{2^n - 1}$. Если $A$ и $B$ находятся в разных половинах турнирной лестницы, то они могут встретиться лишь в финальном поединке. Вероятность выйти в финал для каждого рыцаря есть $ \frac {1}{2^{n - 1}}$, так как для осуществления этого события необходимо выиграть во всех предыдущих турах. Вероятность того, что $A$ и $B$ достигнут финала, равна $( \frac {1}{2^{n - 1}})^2 = \frac {1}{2^{2n - 2}}$. Итак, вероятность встречи рыцарей из разных половин таблицы равна
$ \frac {2^{n - 1}}{2^n - 1} \cdot \frac {1}{2^{2n - 2}}$.
К этой вероятности следует прибавить вероятность поединка близнецов, которые оказались записанными в одну и ту же половину таблицы. Вероятность последнего события равна $ \frac {2^{n - 1} - 1}{2^n - 1}$, и, согласно индукционному предположению, вероятность схватки между близнецами в турнире из $n-1$ тура равна $\frac {1}{2^{2n - 2}}$. Итак, вероятность встречи равна
$ \frac {2^{n - 1}}{2^n - 1} \cdot \frac {1}{2^{2n - 2}} + \frac {2^{n - 1} - 1}{2^n - 1} \cdot \frac {1}{2^{n - 2}} = \frac {1}{(2^n - 1) 2^{n - 2}} \left ( \frac{1}{2} + 2^{n - 1} - 1 \right ) = \frac {1}{2^{n - 1}}$,
что и доказывает наше утверждение.
