21. «Правильные» очереди: от очереди к пути
Задачу про очередь в кассу можно перевести на язык путей по решётке: каждый человек — шаг вправо (платит 500 драмов) или вверх (платит 1000 драмов), а «очередь правильная» означает, что путь ни разу не поднимается выше диагонали. Остаётся посчитать такие пути; это сделаем в следующей главе.
Что пригодится из прошлого: пути по решётке — запись пути нулями и единицами; перестановки — расстановка разных людей по местам; число путей из той же главы. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Условие задачи
У кассы кинотеатра стоят в очереди человек (): у человек по 500 драмов, у остальных человек по 1000 драмов. Билет стоит 500 драмов. Каждый покупает один билет, расплачиваясь одной купюрой; в начале в кассе нет денег. Сдачу кассир даёт только купюрой в 500 драмов, полученной от прежних покупателей (купюра в 1000 драмов сдачей служить не может). Очередь называется «правильной», если каждый раз, когда человек с 1000 драмов покупает билет, в кассе уже есть купюра в 500 драмов, чтобы дать ему сдачу. Сколько существует правильных очередей?
Люди различны (это конкретные люди), поэтому очереди, которые отличаются порядком людей, считаются разными.
Начнём с малого: два человека
Пусть двое: с 500 драмами и с 1000.
- Очередь . платит 500 — в кассе 500. платит 1000 и получает сдачу 500 — сдача есть. Правильная.
- Очередь . платит 1000, а в кассе ничего нет — сдать нечего. Неправильная.
Правильная очередь одна.
Запишем очередь словом из нулей и единиц
Каждому человеку сопоставим символ (): , если у -го человека 500 драмов, и , если у него 1000 драмов. Очередь превращается в слово . Обозначим:
- — число правильных очередей (с различными людьми);
- — число слов, отвечающих правильным очередям.
Не путайте: — это числа (количества), а запись в этой и следующей главах означает координаты точки решётки.
Касса как счётчик. Пока человек с 500 драмами платит, в кассе становится на одну «купюру для сдачи» больше. Когда платит человек с 1000, одна купюра в 500 уходит ему в сдачу (его собственная купюра в 1000 в кассе остаётся, но сдавать ею нельзя: сдача — 500). Значит, после первых человек в кассе лежит столько купюр, сколько нулей минус единиц в слове . Сдача есть, если это число никогда не отрицательно.
В таблице: код очереди, число купюр в кассе после каждого человека и вердикт (в скобках — шаг, на котором сдачи не хватило):
| Код | Касса | Верно? |
|---|---|---|
| 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) |
Для правильных слов два: и . Значит, .
Условия правильного слова
Слово соответствует правильной очереди тогда и только тогда, когда выполнены два условия:
- а) в нём нулей и единиц;
- б) для каждого () в начале слова нулей не меньше, чем единиц.
Условие (б) говорит ровно то, что после каждого человека число купюр в 500 драмов в кассе не отрицательно, то есть сдача всегда нашлась.
От слова к очереди людей: множитель
Слово хранит только «у кого сколько»; конкретные люди в нём не указаны. Возьмём любое правильное слово. Людей с 500 драмами человек, их нужно расставить по нулевым местам: способов. Людей с 1000 драмами тоже , их расставляем по местам единиц: способов. Расстановки независимы, поэтому каждому слову отвечает очередей:
Например, слову для людей (500) и (1000) отвечают четыре очереди: a c b d; a d b c; b c a d; b d a c. Для : .
От слова к пути
Вспомним код пути из главы про решётку: «» — шаг вправо, «» — шаг вверх. Слово с нулями и единицами — путь из в . Условие (б) «нулей не меньше, чем единиц» означает, что после каждого шага число шагов вправо не меньше числа шагов вверх, то есть точка лежит на диагонали или ниже неё: .
Итог перевода: слова, отвечающие правильным очередям, — это пути из в , которые ни разу не поднимаются выше диагонали (касаться диагонали можно).
Вот все пять правильных путей для (знаками ◇ отмечены точки диагонали, которых путь не касается; точки самого пути — ●) и один неправильный, у которого первая точка выше диагонали помечена знаком ✗:
·─·─·─● ·─·─·─● ·─·─·─●
│ │ │ ┃ │ │ │ ┃ │ │ │ ┃
·─·─◇─● ·─·─◇─● ·─·─●━●
│ │ │ ┃ │ │ │ ┃ │ │ ┃ │
·─◇─·─● ·─◇─●━● ·─◇─●─·
│ │ │ ┃ │ │ ┃ │ │ │ ┃ │
●━●━●━● ●━●━●─· ●━●━●─·
000111 001011 001101
·─·─·─● ·─·─·─● ·─·─·─●
│ │ │ ┃ │ │ │ ┃ │ │ │ ┃
·─·─◇─● ·─·─●━● ·─✗━●━●
│ │ │ ┃ │ │ ┃ │ │ ┃ │ │
·─●━●━● ·─●━●─· ·─●─·─·
│ ┃ │ │ │ ┃ │ │ │ ┃ │ │
●━●─·─· ●━●─·─· ●━●─·─·
010011 010101 011001
Видно: правильные пути «прижимаются» к нижней части квадрата, а неправильный после первого шага вправо делает два шага вверх, и его точка оказывается выше диагонали — в кассе не хватило сдачи.
Сколько путей всего и сколько «хороших»
Обозначим число путей из в , которые поднимаются выше диагонали (их называют «пересекающими диагональ»). Любой путь либо не поднимается выше диагонали, либо поднимается, и общее число путей мы знаем:
Осталось найти , число «плохих» путей. Посмотрим на малые случаи: в столбце «Всего» стоит , далее — число хороших и плохих путей:
| Всего | |||
|---|---|---|---|
| 1 | 2 | 1 | 1 |
| 2 | 6 | 2 | 4 |
| 3 | 20 | 5 | 15 |
| 4 | 70 | 14 | 56 |
В последнем столбце — числа . Это , то есть . Это не случайно; в следующей главе мы докажем формулу для красивым приёмом — отражением пути.
Частые ошибки
- Считать только слова и забыть про людей. Слово — это распределение «у кого сколько»; чтобы получить очереди, нужно умножить на .
- Думать, что касание диагонали запрещено. Условие допускает точки на диагонали: в кассе в этот момент ровно ноль купюр для сдачи, и очередь ещё правильная (пример ).
- Применять условие только в конце. «Нулей столько же, сколько единиц» верно для всего слова, а условие (б) нужно проверять для каждого начала слова.
- Перепутать, что кодируют нули и единицы. Здесь — человек с 500 драмами (вправо), — с 1000 драмами (вверх).
Проверь себя
1. Выпишите все слова, отвечающие правильным очередям при .
Решение
000111, 001011, 001101, 010011, 010101 — всего . Остальные слов из двадцати неправильные.
2. Правильно ли слово ()? Где в нём нарушается условие?
Решение
Считаем «нули минус единицы» после каждого символа: . После пятого символа получилось : в начале слова три единицы и только два нуля — в кассе нет сдачи. Слово неправильное.
3. Сколько существует правильных очередей из четырёх различных людей (двое с 500 и двое с 1000 драмов)?
Решение
.
4. Известно (см. таблицу выше и следующую главу), что при существует правильных слов. Сколько существует правильных очередей из восьми различных людей (четверо с 500 драмами и четверо с 1000)?
Решение
.
Итог
- Очередь превращается в слово: — человек с 500 драмами, — с 1000 драмами.
- Слово правильное: нулей и единиц по , и в каждом начале слова нулей не меньше, чем единиц.
- Правильные слова — это пути из в , не поднимающиеся выше диагонали.
- и , где — число «плохих» путей.
