День 215. Об одной задаче (I)

Еще в школьном возрасте нашел одну интересную задачку (у Гарднера, кажется). Задачка очень простая, но недавно пришла в голову мысль ее обобщить и попытаться получить какие-то содержательные выводы.

О решении, удивительных открытиях и одном хитром математическом приеме и будет данный пост.

Исходная задача

Мальчик играет в шахматы против родителей поочередно. Известно, что отец играет лучше матери. Цель мальчика — выиграть две партии подряд из трех. С кем ему лучше начать, чтобы увеличить свои шансы?

Решение: пусть вероятность победы мальчика в партии против матери — p, против отца — q. Известно, что p>q. Необходимо сравнить вероятности двух побед подряд в серии «отец, мать, отец» и «мать, отец, мать».

Обозначая проигрыш в партии нулем, а выигрыш — единицей, имеем:

Для первой серии подходят варианты 11, вероятность которого равна qp, и 011, вероятность которого (1-q)pq. Итоговая вероятность — pq + (1-q)pq = pq(2-q)

Для второй серии аналогично имеем вероятность pq + (1-p)qp = pq(2-p)

Учитывая p>q, получаем, что первый вариант выгоднее, то есть мальчик должен начать играть ПРОТИВ БОЛЕЕ СИЛЬНОГО ИГРОКА (в серии, где с ним, возможно, придется играть дважды), ЧТОБЫ УВЕЛИЧИТЬ ШАНСЫ.

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

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

Обобщение

Пусть серия состоит не из 3 игр, а из N. И выиграть нужно не 2 игры подряд, а m. Отмечу, что победы подряд — необходимое условие для сохранения содержательности игры (в противном случае, приходим к формуле Бернулли)

Вероятность победы в такой игре, в зависимости от того, с какого игрока мы начинаем, будем обозначать 

Fq_m(N).

Наша задача, таким образом, сравнить Fq_m(N) и Fp_m(N) для заданных пар m, N.

Для исходной игры мы получили Fq_2(3) > Fp_2(3)

1. Сначала проведем обобщение для N, зафиксировав m=2.

Посчитаем несколько начальных значений функции:

Fq_2(3) = pq(2-q)

Для Fq_2(4) подойдут следующие исходы игр:

11 — выигрыш, выигрыш

1011 — выигрыш, проигрыш, выигрыш, выигрыш

и аналогично: 011, 0011

Fq_2(4) = qp + q(1-p)qp + (1-q)pq + (1-q)(1-p)qp = qp(1 + q — qp + 1 — q + 1 — p — q + pq) = qp(3-p-q)

Fp_2(4) = pq(3-p-q)

эти значения совпадают.

Для Fq_2(5) подойдут следующие исходы игр (в принятой нами нотации): 11, 1011, 10011, 011, 01011, 0011, 00011

Fq_2(5) = qp + q(1-p)qp + q(1-p)(1-q)pq + (1-q)pq + (1-q)p(1-q)pq + (1-q)(1-p)qp + (1-q)(1-p)(1-q)pq.

Для Fq_2(6) следующие: 11, 1011, 101011, 10011, 100011, 011, 01011, 010011, 0011, 001011, 00011, 000011

Fq_2(6) = qp + q(1-p)qp + q(1-p)q(1-p)qp + q(1-p)(1-q)pq + q(1-p)(1-q)(1-p)qp + (1-q)pq + (1-q)p(1-q)pq + (1-q)(1-p)qp + (1-q)(1-p)q(1-p)qp + (1-q)(1-p)(1-q)pq + (1-q)(1-p)(1-q)(1-p)qp.

Упрощать эти выражения не будем — просто обратим внимание, что решение задачи «в лоб» приводит к большому количеству выкладок и длинным выражениям, в которых не прослеживается никакой закономерности.

Есть ли способ решить проще?

Для подсчета Fq_2(N) необходимо суммировать вероятности ДВУХ ПОБЕД ПОДРЯД. Они могут произойти либо в 1,2 играх (11), либо во 2,3 при условии, что 1 была проиграна (011), либо в 3,4 при условии, что 2 была проиграна (*011) и т.д.

В общем случае — в m-1,m, где m <= N, m-2 = 0 и в партиях 1,...,m-3 не было двух побед подряд.

Уже прослеживается рекуррентное выражение, из которого мы и выразим функцию Fq_2(N), аккуратно проделав выкладки:

      1 партия  2 партия  3 партия  4 партия  5 партия  6 партия                     вероятность

1.        1             1                                                                                              pq

2.        0             1             1                                                                          (1-q)pq

3.        *             0             1                1                                                        (1-p)pq

4.        *             *             0                1             1                                     (1-q)pq(1-pq)

первые две звездочки — не пара (1,1)     

5.        *             *             *                0             1             1

в первых трех звездочках — нет двух единиц подряд, то есть подойдут варианты

000 — (1-q)(1-p)(1-q), 001 — (1-q)(1-p)q, 010 — (1-q)p(1-q), 100 — q(1-p)(1-q), 101 — q(1-p)q

Но эта вероятность есть не что иное, как 1-Fq_2(3)

Обозначив, fi(N) — вероятность того, что в серии игр первые две победы подряд случатся в паре (i,i-1),

получим

fi(2k)     = (1-p)pq(1-Fq_2(2k-3)) 

fi(2k+1) = (1-q)pq(1-Fq_2(2k-2))

Обсудить у себя 0
Комментарии (0)
Чтобы комментировать надо зарегистрироваться или если вы уже регистрировались войти в свой аккаунт.

Войти через социальные сети:

Сахаров Денис
Сахаров Денис
Был на сайте сегодня в 15:47
Читателей: 21 Опыт: 920.487 Карма: 10.1215
все 22 Мои друзья