Условие
Билет стоит 100 рублей. В очереди к кассе 10 человек: у пятерых есть только купюра в 100 рублей, у пятерых — только купюра в 200 рублей. В начале работы в кассе нет денег.
а) Сколько существует последовательностей «у первого покупателя такая-то купюра, у второго такая-то, …», при которых кассир каждый раз сможет дать сдачу?
б) Какова вероятность этого, если все порядки людей в очереди равновероятны?
в) Обобщите ответы на 2n покупателей: n со сторублёвками и n с двухсотрублёвками.
Решение
Запишем сторублёвку как +1, двухсотрублёвку как −1. После k покупателей у кассира лежит столько сторублёвок, какова сумма первых k членов последовательности. Сдачу можно дать всегда тогда и только тогда, когда все частичные суммы неотрицательны. Всего последовательностей из n плюсов и n минусов C(2n, n); при n = 5 их 252.
Посчитаем плохие последовательности, у которых частичная сумма где-то становится равной −1. Возьмём первый такой момент и поменяем знаки всех членов до него включительно. Сумма этого начального куска была −1, а станет +1, поэтому сумма всей последовательности станет 2: в ней n + 1 плюсов и n − 1 минусов. Обратно, в любой последовательности из n + 1 плюсов и n − 1 минусов частичная сумма впервые достигает +1 в какой-то момент; меняя знаки до этого момента, получаем плохую последовательность. Это взаимно однозначное соответствие (принцип отражения), поэтому плохих последовательностей C(2n, n + 1).
Хороших: C(2n, n) − C(2n, n + 1) = C(2n, n)/(n + 1) — число Каталана. При n = 5: 252 − 210 = 42.
Если люди различимы, каждой последовательности купюр соответствует одно и то же число порядков людей: n!·n!. Поэтому все последовательности купюр равновероятны, и искомая вероятность равна 42/252 = 1/6, а в общем случае 1/(n + 1). Для 10 различных людей подходящих порядков 42·5!·5! = 604 800 из 10! = 3 628 800.
Ответ
а) 42; б) 1/6; в) C(2n, n)/(n + 1) последовательностей, вероятность 1/(n + 1).
Проверка
Программа перебрала все 252 расположения пяти двухсотрублёвок среди десяти мест и нашла 42 подходящих. Для n от 1 до 8 перебор дал 1, 2, 5, 14, 42, 132, 429, 1430 и вероятности ровно 1/(n + 1). Отдельно проверено обобщение: если у кассира заранее есть k сторублёвок, подходящих последовательностей C(2n, n) − C(2n, n + k + 1).
Типичные ошибки
- Отражать не начальный кусок до первого «провала», а всю последовательность или кусок после него — соответствие ломается.
- Считать, что вероятность для различимых людей другая, чем для последовательностей купюр. Множитель n!·n! одинаков у всех последовательностей и сокращается.
- Забывать, что касса пуста: даже первый покупатель с двухсотрублёвкой делает порядок плохим.
Задача по мотивам problems.ru, № 60450. Формулировка и решение — редакция damirock.com.