Вероятность/Задачи/coin-game-n-k/Решение Бескровного А. — различия между версиями
Aimly (обсуждение | вклад) (Новая страница: «Похоже, в задаче полагается, что есть человек-бросатель, который бросает, т.к., судя по усл…») |
Aimly (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
Похоже, в задаче полагается, что есть человек-бросатель, который бросает, т.к., судя по условию задачи, в раунде побеждает один человек. | Похоже, в задаче полагается, что есть человек-бросатель, который бросает, т.к., судя по условию задачи, в раунде побеждает один человек. | ||
| − | В таком случае нам просто нужно найти вероятность того, что у игрока после n+k ходов будет k побед, причем k-й раунд для него был проигрышным (т.к. это был последний раунд и в нем узналось, что он проиграл). | + | В таком случае нам просто нужно найти вероятность того, что у игрока после n + k ходов будет k побед, причем k-й раунд для него был проигрышным (т.к. это был последний раунд и в нем узналось, что он проиграл). |
| − | Итак, у нас есть цепь из n+k чисел, 0 - если игрок в этом раунде проиграл, 1 - если выиграл. | + | Итак, у нас есть цепь из n + k чисел, 0 - если игрок в этом раунде проиграл, 1 - если выиграл. |
| − | Нужно найти вероятность того, что после игры в такой цепи (длиной n+k) для игрока будет k единиц, n нулей и последний элемент - нуль. | + | Нужно найти вероятность того, что после игры в такой цепи (длиной n + k) для игрока будет k единиц, n нулей и последний элемент - нуль. |
| − | Посчитаем общее число цепей. Понятно, что в цепи должно быть n нулей, т.к. игрок проигравший. Последняя цифра - нуль. Всего игрок мог выиграть s раундов, где s = 0, 1, ... , n - 1. В каждой такой ситуации в игре будет n+s шагов. Значит для каждого s всего возможных цепей - число разбиений n+s-1 по s-1 (т.е. мы выбираем, куда поставить s-1 нулей в цепи без последнего члена, который заведомо нуль, всего в такой цепи как раз s нулей и ее длина n+s). А все возможные варианты - это сумма таких разбиений при s = 0, 1, ... , n-1. | + | Посчитаем общее число цепей. Понятно, что в цепи должно быть n нулей, т.к. игрок проигравший. Последняя цифра - нуль. Всего игрок мог выиграть s раундов, где s = 0, 1, ... , n - 1. В каждой такой ситуации в игре будет n + s шагов. Значит для каждого s всего возможных цепей - число разбиений n + s - 1 по s - 1 (т.е. мы выбираем, куда поставить s - 1 нулей в цепи без последнего члена, который заведомо нуль, всего в такой цепи как раз s нулей и ее длина n + s). А все возможные варианты - это сумма таких разбиений при s = 0, 1, ... , n - 1. |
Теперь посчитаем успешные исходы. | Теперь посчитаем успешные исходы. | ||
| − | Это все цепи длины n+k с k нулями и последним нулем. Их число - число сочетаний из n+k-1 по k-1, аналогично предыдущим рассуждениям. | + | Это все цепи длины n + k с k нулями и последним нулем. Их число - число сочетаний из n + k - 1 по k - 1, аналогично предыдущим рассуждениям. |
Итак, мы получаем ответ: | Итак, мы получаем ответ: | ||
Версия 20:36, 30 июня 2013
Похоже, в задаче полагается, что есть человек-бросатель, который бросает, т.к., судя по условию задачи, в раунде побеждает один человек.
В таком случае нам просто нужно найти вероятность того, что у игрока после n + k ходов будет k побед, причем k-й раунд для него был проигрышным (т.к. это был последний раунд и в нем узналось, что он проиграл).
Итак, у нас есть цепь из n + k чисел, 0 - если игрок в этом раунде проиграл, 1 - если выиграл. Нужно найти вероятность того, что после игры в такой цепи (длиной n + k) для игрока будет k единиц, n нулей и последний элемент - нуль.
Посчитаем общее число цепей. Понятно, что в цепи должно быть n нулей, т.к. игрок проигравший. Последняя цифра - нуль. Всего игрок мог выиграть s раундов, где s = 0, 1, ... , n - 1. В каждой такой ситуации в игре будет n + s шагов. Значит для каждого s всего возможных цепей - число разбиений n + s - 1 по s - 1 (т.е. мы выбираем, куда поставить s - 1 нулей в цепи без последнего члена, который заведомо нуль, всего в такой цепи как раз s нулей и ее длина n + s). А все возможные варианты - это сумма таких разбиений при s = 0, 1, ... , n - 1.
Теперь посчитаем успешные исходы. Это все цепи длины n + k с k нулями и последним нулем. Их число - число сочетаний из n + k - 1 по k - 1, аналогично предыдущим рассуждениям.
Итак, мы получаем ответ: