Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 65
Текст из файла (страница 65)
ПРИМЕР 8.71. Сколько решений имеет уравнение п1+и2+пз+п4+из =25, где каждое и; — неотрицательное целое число? Это эквивалентно вопросу о том, сколько существует различных выборок вида П1И1 + П2И2 + Пзаз + П4И4 + П5И5, где имеется гн объектов типа а, и п1+П2+ из+ п4+ Из = 25, но количество таких выборок — это количество различных сочетаний из 5 эле- ментов по 25 с повторениями.
Итак, существуют (25 + 5 — 1)! 29! 25! (5 — 1) )! 25! 4! различных решений уравнения и, + из+ из + П4 + П5 = 25. 382 ГПЯВА 8. Комбинвторикв и вероятность Было показано, что число различных сочетаний из й объектов по и объектов с повторением равно С(п + )с — 1, и) = С(п + lс — 1, й — 1) = (п+ lс — 1)! п! (/с — 1)! Если необходимо выбрать хотя бы по одному объекту каждого типа, то имеются п — 'к выборов из !с различных объектов.
Следовательно, имеем С(п — й+й — 1, й — 1) или С(п — 1,!с — 1) способов выбора. ТЕОРЕМА 8.72. Количество различных сочетаний из )с объектов по и объектов с повторением, когда необходимо выбрать хотя бы по одному объекту каждого типа, равно (и — 1) ! С(п — 1,п — к) = С(п — 1, к — 1) = и! (/с — 1)! ПРИМЕР 8.73. Если в булочной продается 10 различных видов пончиков, то сколькими способами можно выбрать две дюжины пончиков, если необходимо выбрать хотя бы по одному пончику каждого вида? Если бы не было последнего ограничения, то для выбора двух дюжин пончиков нз 10 различных видов существовало бы С(24+ 10 — 1,24) = С(33,24) различных способов.
Однако, учитывая ограничение, можно выбрать только 24— 10 = 14 пончиков из 10 различных видов, что дает С(14 + 10 — 1, 14) = С(33, 14) различных вариантов выбора. ПРИМЕР 8.74. Найдем количество различных целочисленных решений уравнения п4 + пз + пз + п4 + пз — — 25, если п4 > 1, пз > 1, пз > 2, п4 > 2 и пз > 2. Представим эту задачу, как подсчет количества выборок вида п,аг + пзаз + пзаз + п4а4 + пзаз, где п4 + пз + пз + п4 + пз — — 25, причем следует выбрать, по крайней мере, одно аы одно аз, два аз, два а4 и два аз. Это оставляет для выбора только 25 — 8 = 17 элементов из пяти типов, что дает (17+ 5 — 1)! 21! 17! 17! решений для пг + па + пз+ п4+ пз — — 25. РЛЗДЕЛ 68.
Принцип клегпок 363 ° УПРАЖНЕНИЯ 1. Сколько существует решений уравнения из + из + из + п4 + пз — — 17 таких, что каждое п, — неотрицательное целое число? 2. Сколько существует решений уравнения пз + из + пз + п4 = 23 таких, что каждое и, — неотрицательное целое число? 3. Сколько существует решений уравнения иг + из + из+ ич = 23 таких, что п~ > 2, пз > 3, из > 4, п4 > 5? 4. Сколько существует решений уравнения пз + пз + пз + п4 = 21 таких, что пг > 2, пз > 3, пз > 4, п4 > 5? 5.
Сколько различных коллекций из десяти монет можно собрать из монет стоимостью 1 цент, 5 центов, 10 центов, 25 центов и 50 центов? 6. В киоске продаетея мороженое 21 вида. Фрэд хочет купить пять порций мороженого. Если мороженого одного вида может быть более одной порции, то сколько существует способов сделать покупку? 7. Если в урне имеются 20 красных, 20 зеленых и 20 синих шаров, то сколькими различными способами можно выбрать 10 шаров? 8.
Цветочник продает 10 видов цветов. Сколько различных букетов из 12 цветков он может сделать? 9. Сколько существует чисел, меньших 10000 и таких, что сумма цифр равна 12? 10. Сколько существует бриджевых раздач (из 13 карт), содержащих три трефовые, четыре червовые, пять пиковых карт и одну карту бубей? 11. Если не делать различий между картами одной масти, то сколько может быть типов бриджевых раздач? 12. Человек покупает 12 различных игрушек для своих четырех детей. Сколькими способами он может распределить игрушки? А сколькими способами, если игрушки делить поровну? 8.8.
ПРИНЦИП КЛЕТОК Принцип клеток, известный также как принцип Дирихле, — это очень простая, но тем не менее очень мощная идея. Она особенно полезна в теории чисел. Данный раздел состоит из двух довольно простых теорем и нескольких не совсем простых примеров. Начнем с наиболее известной формы принципа клеток.
ТЕОРЕМА 8.76. Если поместить п+ 1 голубей в и клеток, то, по крайней мере, в одной клетке будет находится более одного голубя. ДОКАЗАТЕЛЬСТВО. Если в каждой клетке не более одного голубя, то голубей не может быть больше, чем клеток. Тогда во всех клетках должно быть не более, чем и голубей, что противоречит условию. Из теоремы следует, что если т > п и требуется т голубей разместить в и клетках, то в одной клетке находится более одного голубя.
ПРИМЕР 8.76. В списке, содержащем т + 1 положительных целых чисел, по крайней мере, два числа имеют один и тот же остаток при делении на т. Пусть 384 ГЛАВА 8. Комбонвторикв и вероятность а1азаз ...,а,а 4.1 — перечень положительных целых чисел. Предположим, что для 1 < 1 < т+ 1 имеем а; = багги+ т1, где 0 < тг < т. Следовательно, т1 т2 тз ...,т,т ь1 — список, содержащий та+ 1 положительных целых чисел, меньших т. Но существует только ти различных неотрицательных чисел, меньших и1.
Поэтому два числа из т; должны быть равны. П ПРИМЕР 8.77. Если (А! ) )В(, то не может существовать инъективная функция 1': А — В. Пусть (В! = и. Существует и множеств Г" 1(6) = (х: Дх) = 6) для 6 е В и А = Оь В 2' '(6). Но А содержит больше и элементов. Поэтому не менее двух элементов, например, а и а', должны быть в одном множестве.
Но тогда Да) = Да') и 2 не является инъективной функцией. С) ПРИМЕР 8.78. Если в прямоугольнике со сторонами 6 и 8 дюймов помещены пять точек, то существуют две точки, расстояние между которыми не более 5 дюймов. Разделим исходный прямоугольник на четыре прямоугольника, размером 3 на 4 дюйма каждый. Поскольку пять точек должны находиться либо внутри, либо на границах четырех прямоугольников, то хотя бы две точки должны быть либо внутри, либо на границе одного и того же прямоугольника размера 3 х 4. Но любые такие точки находятся на расстоянии не более 5 дюймов.
ь) ПРИМЕР 8.79. В последовательности а1, аз, аз,..., 01о из десяти целых чисел существует последовательность идущих подряд элементов а„„ а 41, а Е2,,,., а сумма которых делится на 10. Рассмотрим числа в1 = 01, зз = а1 + аз, зз = а1 + 02 + аз з4 а1 + 02 + аз + 04 ° ° ° з10 01 + 02 + аз + 04 + ''' + 010 ° Если одна из этих сумм делится на 10, то процесс завершен, элементы суммы образуют искомую последовательность. Если нет, то каждое в, = 10д, + т„где 1 < т, < 9. Имеется десять т„и только девять значений, которые они могут принимать. Поэтому существуют два т с одинаковыми значениями, например, т, = ть для некоторого 1 < й. Тогда вь — а = 10дь + ть — (10д + ту) = = 10д, - 10д, = = 10(„-„)' кратно 10. Но это не что иное, как сумма а 41+ а „2+ 0 ез+ ..
+аь, элементы которой образуют искомую последовательность. П ПРИМЕР 8 80. (Эрдош и Шекерес) Пусть  — подмножество множества 11, 2,3, ..., 2и), содержащее и+1 элемент, где и — некоторое положительное целое число. Существуют два элемента, принадлежащие множеству Я такие, что один элемент делит другой элемент.
Любое положительное целое число можно представить в виде 2*у„где д; — положительное нечетное число. Запишем каждый элемент множества В в таком виде. Множество (д1,92,...,9„,9„е1,) содержит и+ 1 положительных нечетных целых чисел, при том что имеется только и нечетных чисел, которые меньше или равны 2и. Поэтому 9, = д при 1 ~ 11 Таким образом, множество В содержит два различных целых числа вида а = 2"д1 и 6 = 2'д1 соответственно. Если т < з, то а делит Ь, и если т > в, то Ь делит а. П РЯЭДЕЛ а.в. Принцип клеток 366 А теперь приведем более сильные формы принципа клеток. ТЕОРЕМА 8.81.
а) Пусть т > п голубей помещены в и клеток, тогда некоторая клетка содержит не менее ~ ™1 голубей. ~п~ б) Пусть т = т1 + тз + тз + .. + т„— и + 1 голубей помещены в п клеток, где т, — положительное целое число для каждого 1 < 1 < и. Тогда, для некоторого г, г-ая клетка содержит не менее т, голубей. ДОКАЗАТЕЛЬСТВО. а) Пусть каждая клетка содержит меньше ~ — „1 голубей. Тогда, поскольку нас интересуют целые голуби, каждая клетка содержит меньше — „голубей. Поэтому общее количество голубей меньше и х — „= т, что противоречит условию. б) Пусть 1-ая клетка содержит меньше, чем т, голубей. Тогда количество голубей в 1-ой клетке меньше или равно т, — 1.
Просуммировав по всем клеткам, получаем, что всего голубей не более, чем (т1 — 1)+(тз — 1)+(тз — 1)+ +(т„— 1) =т1+тз+тз+ ..+т„— п, что противоречит условию. ПРИМЕР 8.82. Пусть в урне находятся 10 красных, 10 синих и 10 зеленых шаров. Сколько шаров нужно взять из урны, чтобы с уверенностью иметь хотя бы 4 красных или 5 синих, или 6 зеленых шаров? Мы знаем, что 12 шаров недостаточно, поскольку можно выбрать 3 красных, 4 синих и 5 зеленых шаров. Если отождествить шары одного цвета с голубями, находяшимися в одной клетке, то, согласно части (б) сильной формы принципа клеток, имеем и = 3, т1 = 4, тз = 5 и тз = 5.
Поэтому искомое количество шаров равно т=т1+тз+тз+ . +т„— и+1= =4+5+6 †3+ = 13. ПРИМЕР 8.83. (Эрдош н Шекерес) Конечная последовательность целых чисел аы аз, аз, ..., аь возрастающая, если каждое число последовательности больше предыдущего. Иначе говоря, если г > з, то а; > а . Конечная последовательность целых чисел аы аз, аз, ..., аь убывающая, если каждое число последовательности меньше предыдушего. Иначе говоря, если г > з, то а, < а,.
Любая последовательность из из+ 1 различных целых чисел содержит либо убывающую подпоследовательность, включающую не менее и+ 1 членов, либо возрастающую подпоследовательность, включаюшую не менее и+1 членов, Для доказательства предположим, что з, — количество чисел в самой длинной возрастаюшей последовательности аы аз, аз, ..., а„~ы начинающейся с а;. Если з, > и+ 1 для некоторого г, то процесс завершен. Если нет, то для каждого г, 1 < е, < п. Поэтому для всех из+ 1 штук з,, где 1 < з' < из+ 1, имеется п значений. Согласно части (а) сильной формы принципа клеток получаем, что 366 ГЛАВА 8. Комбинвторикв и вероятность штук в, равны.
Поэтому, по крайней мере, и + 1 чисел из з; равны. Пусть все они равны в. Рассмотрим подпоследовательность длины п+ 1, состоящую из таких а,, что в, равны в. Эта последовательность — убывающая, потому что если а; > а, для г > 1, то, добавляя а, в начало последовательности длины в, начинающейся с а,, можно получить возрастающую последовательность длины в+ 1, начинающуюся с ао Но это противоречит тому факту, что самая длинная возрастающая последовательность, начинающаяся с а,, имеет длину в.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
