ах вже перший глядач не зможе отримати здачі, а в останньому випадку у каси затримається третій глядач. p> При невеликих значеннях m і k завдання можна вирішити прямим перебором. Але якщо m і k порівняно великі, то прямий перебір не допоможе. Адже число різних перестановок з m рублів і k полтиника одно P (m, k) = Вже при m = k = 20 число перестановок з 20 рублів і 20 полтиника одно, а це число більше ста мільярдів. p> Отже, нам треба вирішити наступну комбінаторну задачу.
Знайти число перестановок з повтореннями з m рублів і k полтиника, таких, що для будь-якого r, 1? r? m + k , число полтиника серед перших r елементів перестановки не менш числа рублів.
Ясно, що шукане число відмінно від нуля лише за умови, що т? до - інакше полтиника завідомо не вистачить, щоб дати здачу всім власникам рублів.
Як і в багатьох комбінаторних задачах, тут корисно використовувати геометричну ілюстрацію. Візьмемо координатну сітку і будемо зображати кожну перестановку рублів і полтиника ламаної, що з'єднує вузли сітки за такими правилами: ламана починається на початку координат О (0, 0); кожному полтинику відповідає ланка ламаної, що йде вгору направо, а кожному рублю - ланка, що йде вгору наліво (ланка з'єднує протилежні точки одного з квадратів координатної сітки). Наприклад, послідовності відповідає ламана, зображена на рис. 1. br/>В
Ясно, що якщо в послідовності мається m рублів і до полтиника. то кінцем ламаної виявиться точка А (к - т; до + т). Число ламаних, що ведуть з точки Про в точку А , дорівнює числу перестановок з повтореннями з т рублів і k полтиника, тобто Р (т, к). З'ясуємо тепер, ніж характеризуються ламані, що задовольняють умові завдання. Якщо чергу в якийсь момент часу застопорилася, то це означає, що число рублів до цього моменту виявилося на 1 більше числа полтиника. Але тоді точка, що рухається по ламаній, зробить вліво на один крок більше, ніж вправо, і опиниться на прямій x = -1 (для ламаної на рис. 1 на цій прямій лежить точка В (-1; 7); вона вказує, що чергу зупиниться на 7-му кроці). Отже, всім перестановок, при яких чергу зупиняється і якийсь момент, відповідають ламані, що мають точки на прямій х = -1 . Зворотно, якщо у ламаної є точка на цій прямій, то черга зупиниться.
Ми прийшли, таким чином, до наступної геометричній задачі: знайти число ламаних зазначеного виду, що не перетинають пряму X = -1 .
<...
