bulgakov

21. «Правильные» очереди: от очереди к пути

Задачу про очередь в кассу можно перевести на язык путей по решётке: каждый человек — шаг вправо (платит 500 драмов) или вверх (платит 1000 драмов), а «очередь правильная» означает, что путь ни разу не поднимается выше диагонали. Остаётся посчитать такие пути; это сделаем в следующей главе.

Что пригодится из прошлого: пути по решётке — запись пути нулями и единицами; перестановки — расстановка разных людей по местам; число путей (m+nm)\dbinom{m+n}{m} из той же главы. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Условие задачи

У кассы кинотеатра стоят в очереди 2n2n человек (n∈Nn\in\mathbb N): у nn человек по 500 драмов, у остальных nn человек по 1000 драмов. Билет стоит 500 драмов. Каждый покупает один билет, расплачиваясь одной купюрой; в начале в кассе нет денег. Сдачу кассир даёт только купюрой в 500 драмов, полученной от прежних покупателей (купюра в 1000 драмов сдачей служить не может). Очередь называется «правильной», если каждый раз, когда человек с 1000 драмов покупает билет, в кассе уже есть купюра в 500 драмов, чтобы дать ему сдачу. Сколько существует правильных очередей?

Люди различны (это конкретные люди), поэтому очереди, которые отличаются порядком людей, считаются разными.

Начнём с малого: два человека

Пусть двое: AA с 500 драмами и BB с 1000.

  • Очередь A,BA,B. AA платит 500 — в кассе 500. BB платит 1000 и получает сдачу 500 — сдача есть. Правильная.
  • Очередь B,AB,A. BB платит 1000, а в кассе ничего нет — сдать нечего. Неправильная.

Правильная очередь одна.

Запишем очередь словом из нулей и единиц

Каждому человеку сопоставим символ αi\alpha_i (1≤i≤2n1\le i\le 2n): αi=0\alpha_i=0, если у ii-го человека 500 драмов, и αi=1\alpha_i=1, если у него 1000 драмов. Очередь превращается в слово α1α2…α2n\alpha_1\alpha_2\ldots\alpha_{2n}. Обозначим:

  • xnx_n — число правильных очередей (с различными людьми);
  • yny_n — число слов, отвечающих правильным очередям.

Не путайте: xn,yn,znx_n,y_n,z_n — это числа (количества), а запись (x,y)(x,y) в этой и следующей главах означает координаты точки решётки.

Касса как счётчик. Пока человек с 500 драмами платит, в кассе становится на одну «купюру для сдачи» больше. Когда платит человек с 1000, одна купюра в 500 уходит ему в сдачу (его собственная купюра в 1000 в кассе остаётся, но сдавать ею нельзя: сдача — 500). Значит, после первых kk человек в кассе лежит столько купюр, сколько нулей минус единиц в слове α1…αk\alpha_1\ldots\alpha_k. Сдача есть, если это число никогда не отрицательно.

В таблице: код очереди, число купюр в кассе после каждого человека и вердикт (в скобках — шаг, на котором сдачи не хватило):

Код Касса Верно?
0011 1, 2, 1, 0 да
0101 1, 0, 1, 0 да
0110 1, 0, -1, 0 нет (шаг 3)
1001 -1, 0, 1, 0 нет (шаг 1)
1010 -1, 0, -1, 0 нет (шаг 1)
1100 -1, -2, -1, 0 нет (шаг 1)

Для n=2n=2 правильных слов два: 00110011 и 01010101. Значит, y2=2y_2=2.

Условия правильного слова

Слово α1α2…α2n\alpha_1\alpha_2\ldots\alpha_{2n} соответствует правильной очереди тогда и только тогда, когда выполнены два условия:

  • а) в нём nn нулей и nn единиц;
  • б) для каждого kk (1≤k≤2n1\le k\le 2n) в начале слова α1α2…αk\alpha_1\alpha_2\ldots\alpha_k нулей не меньше, чем единиц.

Условие (б) говорит ровно то, что после каждого человека число купюр в 500 драмов в кассе не отрицательно, то есть сдача всегда нашлась.

От слова к очереди людей: множитель n!⋅n!n!\cdot n!

Слово хранит только «у кого сколько»; конкретные люди в нём не указаны. Возьмём любое правильное слово. Людей с 500 драмами nn человек, их нужно расставить по nn нулевым местам: n!n! способов. Людей с 1000 драмами тоже nn, их расставляем по nn местам единиц: n!n! способов. Расстановки независимы, поэтому каждому слову отвечает n!⋅n!n!\cdot n! очередей:

xn=n!⋅n!⋅yn.\boxed{x_n=n!\cdot n!\cdot y_n}.

Например, слову 01010101 для людей a,ba,b (500) и c,dc,d (1000) отвечают четыре очереди: a c b d; a d b c; b c a d; b d a c. Для n=2n=2: x2=2!⋅2!⋅2=8x_2=2!\cdot2!\cdot2=8.

От слова к пути

Вспомним код пути из главы про решётку: «00» — шаг вправо, «11» — шаг вверх. Слово с nn нулями и nn единицами — путь из O(0,0)O(0,0) в A(n,n)A(n,n). Условие (б) «нулей не меньше, чем единиц» означает, что после каждого шага число шагов вправо не меньше числа шагов вверх, то есть точка (x,y)(x,y) лежит на диагонали OAOA или ниже неё: y≤xy\le x.

Итог перевода: слова, отвечающие правильным очередям, — это пути из O(0,0)O(0,0) в A(n,n)A(n,n), которые ни разу не поднимаются выше диагонали OAOA (касаться диагонали можно).

Вот все пять правильных путей для n=3n=3 (знаками ◇ отмечены точки диагонали, которых путь не касается; точки самого пути — ●) и один неправильный, у которого первая точка выше диагонали помечена знаком ✗:

·─·─·─●    ·─·─·─●    ·─·─·─●
│ │ │ ┃    │ │ │ ┃    │ │ │ ┃
·─·─◇─●    ·─·─◇─●    ·─·─●━●
│ │ │ ┃    │ │ │ ┃    │ │ ┃ │
·─◇─·─●    ·─◇─●━●    ·─◇─●─·
│ │ │ ┃    │ │ ┃ │    │ │ ┃ │
●━●━●━●    ●━●━●─·    ●━●━●─·
 000111     001011     001101

·─·─·─●    ·─·─·─●    ·─·─·─●
│ │ │ ┃    │ │ │ ┃    │ │ │ ┃
·─·─◇─●    ·─·─●━●    ·─✗━●━●
│ │ │ ┃    │ │ ┃ │    │ ┃ │ │
·─●━●━●    ·─●━●─·    ·─●─·─·
│ ┃ │ │    │ ┃ │ │    │ ┃ │ │
●━●─·─·    ●━●─·─·    ●━●─·─·
 010011     010101     011001

Видно: правильные пути «прижимаются» к нижней части квадрата, а неправильный после первого шага вправо делает два шага вверх, и его точка (1,2)(1,2) оказывается выше диагонали — в кассе не хватило сдачи.

Сколько путей всего и сколько «хороших»

Обозначим znz_n число путей из OO в A(n,n)A(n,n), которые поднимаются выше диагонали (их называют «пересекающими диагональ»). Любой путь либо не поднимается выше диагонали, либо поднимается, и общее число путей мы знаем:

yn+zn=(2nn),yn=(2nn)−zn.\boxed{y_n+z_n=\binom{2n}{n},\qquad y_n=\binom{2n}{n}-z_n}.

Осталось найти znz_n, число «плохих» путей. Посмотрим на малые случаи: в столбце «Всего» стоит (2nn)\dbinom{2n}{n}, далее — число хороших yny_n и плохих znz_n путей:

nn Всего yny_n znz_n
1 2 1 1
2 6 2 4
3 20 5 15
4 70 14 56

В последнем столбце — числа 1,4,15,561,4,15,56. Это (20),(41),(62),(83)\dbinom{2}{0},\dbinom41,\dbinom62,\dbinom83, то есть (2nn−1)\dbinom{2n}{n-1}. Это не случайно; в следующей главе мы докажем формулу для znz_n красивым приёмом — отражением пути.

Частые ошибки

  • Считать только слова и забыть про людей. Слово — это распределение «у кого сколько»; чтобы получить очереди, нужно умножить на n!⋅n!n!\cdot n!.
  • Думать, что касание диагонали запрещено. Условие y≤xy\le x допускает точки на диагонали: в кассе в этот момент ровно ноль купюр для сдачи, и очередь ещё правильная (пример 01010101).
  • Применять условие только в конце. «Нулей столько же, сколько единиц» верно для всего слова, а условие (б) нужно проверять для каждого начала слова.
  • Перепутать, что кодируют нули и единицы. Здесь 00 — человек с 500 драмами (вправо), 11 — с 1000 драмами (вверх).

Проверь себя

1. Выпишите все слова, отвечающие правильным очередям при n=3n=3.

Решение

000111, 001011, 001101, 010011, 010101 — всего 55. Остальные 1515 слов из двадцати неправильные.

2. Правильно ли слово 010110010110 (n=3n=3)? Где в нём нарушается условие?

Решение

Считаем «нули минус единицы» после каждого символа: 1,0,1,0,−1,01,0,1,0,-1,0. После пятого символа получилось −1-1: в начале слова 0101101011 три единицы и только два нуля — в кассе нет сдачи. Слово неправильное.

3. Сколько существует правильных очередей из четырёх различных людей (двое с 500 и двое с 1000 драмов)?

Решение

x2=2!⋅2!⋅y2=4⋅2=8x_2=2!\cdot2!\cdot y_2=4\cdot2=8.

4. Известно (см. таблицу выше и следующую главу), что при n=4n=4 существует 1414 правильных слов. Сколько существует правильных очередей из восьми различных людей (четверо с 500 драмами и четверо с 1000)?

Решение

x4=4!⋅4!⋅14=8064x_4=4!\cdot4!\cdot14=8064.

Итог

  • Очередь превращается в слово: 00 — человек с 500 драмами, 11 — с 1000 драмами.
  • Слово правильное: нулей и единиц по nn, и в каждом начале слова нулей не меньше, чем единиц.
  • Правильные слова — это пути из O(0,0)O(0,0) в A(n,n)A(n,n), не поднимающиеся выше диагонали.
  • xn=n!⋅n!⋅ynx_n=n!\cdot n!\cdot y_n и yn=(2nn)−zny_n=\dbinom{2n}{n}-z_n, где znz_n — число «плохих» путей.
ПрактикаЗагружаем тест…