Тема 5.4. Метод траекторий

Метод траекторий состоит в том, что для комбинаторной задачи указывается геометрическая интерпретация, которая сводит задачу к подсчёту числа путей (траекторий), обладающих определённым свойством. Этим методом фактически была решена задача в примере 4.2. Проиллюстрируем метод траекторий ещё на одном примере.

Пример 5.3: Возле кассы собрались человек, причём из них имеют монеты стоимостью 50 копеек, а другие имеют лишь по рублю . Сначала в кассе нет денег, билет стоит 50 копеек. Сколько всего имеется способов размещения всех покупателей в очереди так, чтобы ни один из них не ждал сдачи?

Решение: Допустим, что покупатели расположены в очереди некоторым образом. Пусть

Рассмотрим сумму

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

Введём на плоскости декартову прямоугольную систему координат. Построим в ней точки с координатами и рассмотрим ломаную, соединяющую точку с точкой и проходящую через точки . Будем называть ломаную траекторией, соответствующей данному способу размещения покупателей в очереди. Каждая траектория состоит из отрезков, из которых направлены вверх, а направлены вниз. Если указать номера тех отрезков, которые направлены вверх, то тем самым траектория будет полностью определена. Следовательно, общее число траекторий, т.е. число возможных размещений покупателей в очереди, равно .

Траектории, соответствующие тем способам размещения покупателей, при которых ни один покупатель не ждет сдачи, не имеют общих точек с прямой . Действительно, если для некоторого то, в лучшем случае, это означает, что первые покупателей подали в кассу одинаковое количество полтинников и рублей , а следующий покупатель подал рубль и вынужден ожидать сдачу. Определим число траекторий, имеющих общую точку с прямой . Поставим в соответствие каждой траектории , имеющей с прямой хотя бы одну общую точку, ломаную по следующему правилу. До первой общей точки с прямой ломаная совпадает с , а далее является симметричным отображением T относительно прямой . Все ломаные заканчиваются в точке , являющейся симметричным отображением точки относительно прямой . Установленное соответствие является взаимно однозначным. Число ломаных типа , равно числу ломаных, соединяющих точки и . Это число легко подсчитать. Если ломаная состоит из отрезков, направленных вниз, и отрезков, направленных вверх, то

откуда получаем , . Таким образом, число траекторий, имеющих общую точку с прямой , равно . Следовательно, искомое число траекторий, соответствующих тем способам размещения покупателей, при которых ни один покупатель не ждет сдачи, равно

Дата добавления: 2015-10-28