Комбинаторика олимпиаднику
 Скачать 0.51 Mb.
|
|
а) Через всевозможные пары точек провели прямые. Сколько различных прямых получилось? б) Сколько существует различных треугольников с вершинами в этих точках? а)20; б)76 23. (Высшая проба, 2014, 9–10 ) В выражении + x)(1 + x 2 )(1 + x 3 ) . . . (1 + раскрыли все скобки и привели подобные слагаемые. Сколько слагаемых получилось 24. (Высшая проба, 2014, 11 ) В выражении + x)(1 + x 2 )(1 + x 3 ) . . . (1 + x 13 )(1 + x 14 )(1 + раскрыли все скобки и привели подобные слагаемые. Сколько слагаемых получилось 25. (Высшая проба, 2014, 9 ) Сколько слагаемых получится после раскрытия скобок и приведения подобных слагаемых в выражении (1 + x 2 ) 100 (1 + x 3 ) 100 ? 499 26. (Высшая проба, 2014, 11 ) Сколько слагаемых получится после раскрытия скобок и приведения подобных слагаемых в выражении (1 + x 3 ) 100 (1 + x 4 ) 100 ? 695 27. (Физтех, 2014, 9–10 ) Дан выпуклый угольник, никакие три диагонали которого не имеют общих точек, отличных от вершин. Найдите число точек пересечения диагоналей (не считая вершин 28. (Физтех, 2014, 9, 11 ) Отметили все вершины правильного угольника. Сколько существует незамкнутых несамопересекающихся семизвенных ломаных с вершинами в отмеченных точках 35 29. В треугольнике Паскаля заменим числа точками и соединим точки отрезками следующим образом: Путём назовём ломаную с началом в вершине треугольника, звенья которой идут по линиям получившейся сетки только вниз. Докажите, что количество путей, ведущих в ю точку й строки, равно C k строки нумеруются сверху с нуля точки в строке нумеруются слева с нуля. (Высшая проба, 2014, 9, 11 ) Приведённая ниже диаграмма состоит из 24 единичных квадратов. Лягушка из каждой клетки может прыгнуть либо на одну клетку вниз, либо на одну клетку влево-вниз по диагонали (не выходя при этом заграницы диаграммы. Сколько существует путей лягушки, ведущих из верхнего ряда квадратов в нижний (На рисунке показан один из путей лягушки. Верхний и нижний ряды квадратов выделены серым фоном 31. (Высшая проба, 2013, 9 ) Сколькими способами можно заполнить цифрами 0, 1, . . . , можно с повторениями) таблицу 3 × 3 так, чтобы сумма цифр в каждой строке и каждом столбце равнялась 4? 120 32. (Высшая проба, 2013, 10 ) Сколькими способами можно заполнить цифрами 0, 1, . . . , можно с повторениями) таблицу 3 × 3 так, чтобы сумма цифр в каждой строке и каждом столбце равнялась 5? 231 33. (Высшая проба, 2013, 11 ) Сколькими способами можно заполнить цифрами 0, 1, . . . , можно с повторениями) таблицу 3 × 3 так, чтобы сумма цифр в каждой строке и каждом столбце равнялась 6? 406 36 34. (Физтех, 2013, 10–11 ) Тест по английскому языку сдавали 10 школьников. Известно, что любые пять школьников ответили вместе на все вопросы, а любые четыре школьника ответили вместе не на все вопросы. При каком наименьшем количестве вопросов теста такое могло случиться 35. (Физтех, 2013 ) Число 84605 написали семь раз подряд, при этом получилось 35-значное число 84605846058460584605846058460584605. Из этого 35-значного числа требуется вычеркнуть две цифры так, чтобы полученное после вычёркивания 33-значное число делилось на 15. Сколькими способами это можно сделать 36. (Ломоносов, 2014, 8–9 ) Дан правильный угольник A 1 A 2 . . . A 27 . Найдите количество неравнобедренных треугольников с вершинами в точках A 1 , A 2 , . . . , A 27 . Треугольники, отличающиеся порядком вершин (например, и A 2 A 4 A 1 ), считаются за один треугольник 37. (Ломоносов, 2016, 7–8 ) Круг разбили на 4 равных сектора по 90 ◦ . Сколькими способами можно его раскрасить, если есть 7 цветов и каждый сектор можно красить в любой цвет? Раскраски, которые совпадают при повороте круга, считать одинаковыми 38. (Высшая проба, 2011, 11 ) Сколькими способами можно раскрасить грани куба в чёрный и белый цвета (каждую грань в один цвет, и оба цвета должны быть использованы Раскраски считаются одинаковыми, если одну можно получить из другой, повертев куб в руках 39. (Физтех, 2015, 10 ) Дан правильный угольник. Найдите количество четвёрок вершин этого угольника, являющихся вершинами выпуклых четырёхугольников, у которых есть хотя бы одна пара параллельных сторон 40. (Физтех, 2015, 10 ) Дан правильный угольник. Найдите количество четвёрок вершин этого угольника, являющихся вершинами трапеций 41. (Физтех, 2013 ) Дан правильный угольник. Найдите количество троек его вершин, являющихся вершинами треугольника, в котором хотя бы один угол равен 45 ◦ . (Две тройки вершин, отличающиеся порядком вершин, считаются одинаковыми 42. (Физтех, 2013 ) Дан правильный угольник. Найдите количество четвёрок его вершин, являющихся вершинами выпуклого четырёхугольника, в котором хотя бы один угол равен Две четвёрки вершин, отличающиеся порядком вершин, считаются одинаковыми 37 43. (Физтех, 2014 ) Есть семь карточек с цифрами 0, 1, 2, 2, 3, 4, 5. Сколько существует различных шестизначных чисел, делящихся на 15, которые можно сложить из этих карточек 44. (Всеросс., 2014, II этап, 11 ) На окружности отмечено 20 точек. Сколько существует таких троек хорд с концами в этих точках, что каждая хорда пересекает каждую (возможно, в концах 45. (Физтех, 2014, 11 ) В выпуклом угольнике проводят все его диагонали. На какое наибольшее число частей они могут его разбить 46. (Физтех, 2011, 10 ) 26 солдат выстроены в одну шеренгу. Сколько существует различных способов выбрать 11 из них так, что никакие двое из них не стоят рядом 47. (Физтех, 2011, 11 ) В Городском Собрании 24 депутата. Любые двое из них либо дружат, либо враждуют, причём известно, что каждый дружит ровно с 7 другими. Каждые три депутата образуют комиссию. Найдите общее число комиссий, в которых все три члена попарно дружат или все трое попарно враждуют 48. (Высшая проба, 2011, 9 ) В классе 20 учеников, каждый из которых дружит ровно с шестью одноклассниками. Найдите число таких различных компаний из трёх учеников, что в них либо все школьники дружат друг с другом, либо каждый не дружит ни с одним из двух оставшихся 49. (Высшая проба, 2011, 9 ) Класс из 20 учеников разделён на две половины так, что каждый школьник из первой половины дружит ровно с шестью одноклассниками, а каждый школьник из второй половины дружит ровно с четырьмя одноклассниками. Найдите число таких различных компаний из трёх учеников, что в них либо все школьники дружат друг с другом, либо каждый не дружит ни с одним из двух оставшихся 50. (Физтех, 2012, 9–11 ) Прямоугольник, составленный из одинаковых квадратных клеток, назовём чётным, если он содержит чётное число клеток. Из одинаковых квадратных клеток составлен прямоугольник длиной 9 клеток и шириной 4 клетки. Сколько в нём содержится чётных прямоугольников 51. (Физтех, 2012, 9–11 ) Сколькими способами можно выложить вряд три красных, четыре синих и пять зелёных шаров так, чтобы никакие два синих шара не лежали рядом 38 52. (Физтех, 2012, 10 ) Сколько существует способов раскрасить вершины правильного пятиугольника в восемь цветов, если раскраски, которые можно совместить поворотом, считаются одинаковыми 53. (Высшая проба, 2012, 9 ) На плоскости отмечены восемь точек, никакие три из которых не лежат на одной прямой. Может ли быть так, что более одной пятой всех выпуклых четырёхугольников с вершинами в этих точках — параллелограммы? Да 54. (Высшая проба, 2014, 10 ) На плосокости даны восемь различных точек. Нумерацию этих точек числами от 1 до 8 назовём хорошей, если выполнено следующее условие: существует такая прямая, что все точки лежат по одну сторону и на разных расстояниях от не, и при этом расстояния от точек до этой прямой возрастают с возрастанием номера (т. е. ближайшая точка — номер 1, следующая по удалённости — номер 2 и т. д.). Какое максимальное количество различных хороших нумераций может быть у заданной восьмёрки точек 55. (Высшая проба, 2012, 11 ) Водной из вершин правильного угольника (n > 2) поставлено число 1. Для данной расстановки чисел 2, 3, . . . , 2n в остальные вершины угольника поставим на каждой его стороне знак +, если число на конце стороны (при движении почасовой стрелке) больше числа на её начале, и знак −, если оно меньше. Докажите, что модуль разности между числом расстановок чисел 2, 3, . . . , 2n сч тным количеством плюсов на сторонах и числом расстановок с нечётным количеством плюсов равен числу расстановок, в которых плюсы и минусы чередуются, при (а) n = 3; (б) n = 4; (в) произвольном n. 39 Формула включений и исключений Не всякая задача комбинаторики решается непосредственным применением основных комбинаторных принципов — правила суммы или произведения, подсчётом числа размещений или сочетаний. В некоторых случаях приходится идти окольным путем и действовать своеобразным «методом решета, который состоит в следующем для нахождения числа элементов интересующего нас множества мы сначала находим число элементов некоторого большего множества, а потом просеиваем нужные элементы, постепенно отбрасывая лишние. 5.1 Переход к дополнению Простейшим примером метода решета является переход к дополнению число «хороших» элементов равно общему числу элементов минус число плохих элементов. Задача. Сколько существует четырёхзначных чисел, в записи которых есть хотя бы одна цифра Решение. Найдём сначала, сколько всего имеется четырёхзначных чисел. Первую цифру мы можем выбрать девятью способами, каждую из остальных цифр — десятью. Стало быть, количество четырёхзначных чисел равно 9 · 10 · 10 · 10 = Теперь найдём, сколько четырёхзначных чисел не содержат ни одной семёрки. Для выбора первой цифры имеется 8 способов, для выбора каждой из остальных цифр — 9 способов. Следовательно, всего будет 8 · 9 · 9 · 9 = 5832 четырёхзначных чисел, в записи которых нет ни одной цифры Ну а чисел, в которых хотя бы одна семёрка имеется, будет 9000 − 5832 = Здесь мы действовали по схеме, которую, выражаясь неформально, можно описать так хотя бы один равно общему числу минус ни одного. В других ситуациях можно действовать наоборот ни одного равно общему числу минус хотя бы один». Задача. Дан выпуклый угольник (n > 5). Сколькими способами можно выбрать в нём две непересекающиеся диагонали Порядок выбора не важен. Решение. Идея подсчёта такова искомое число пар непересекающихся диагоналей равно общему числу пар диагоналей минус число пар пересекающихся (внутри угольника) диагоналей минус число пар смежных (выходящих из одной вершины) диагоналей. Из каждой вершины угольника исходят n − 3 диагоналей, поэтому всего диагоналей имеется. Значит, число неупорядоченных пар диагоналей равно C 2 n(n−3)/2 = 1 2 · n(n − 3) 2 n(n − 3) 2 − 1 = n(n − 3)(n 2 − 3n − Теперь найдём число пар пересекающихся диагоналей. Каждой такой паре отвечает чет- вёрка вершин угольника — концов этих диагоналей. Наоборот, каждым четырём вершинам угольника соответствует единственная пара пересекающихся диагоналей. Поэтому число пар пересекающихся диагоналей есть число неупорядоченных четвёрок вершин угольника C 4 n = n(n − 1)(n − 2)(n − Осталось найти число пар смежных диагоналей. Из каждой вершины выходят пар диагоналей, поэтому nC 2 n−3 = n(n − 3)(n − 4) 2 40 Искомое число пар непересекающихся диагоналей N = N 0 − N 1 − N 2 , и после несложных преобразований получим = n(n − 3)(n − 4)(n − Бывает так, что в условии задачи ничто не намекает на хотя бы один или ни одного, и тем не менее задача проще всего решается переходом к дополнению. Задача. (Высшая проба, 2013, 10 ) В стране пять городов А, Б, В, Г и Д. Их хотят связать четырьмя авиалиниями так, чтобы из каждого города можно было (возможно, с пересадками) долететь до любого другого. Сколькими различными способами это можно сделать? Решение. Найдём сначала общее количество соединений пяти городов четырьмя авиалиниями. Всего пар городов имеется C 2 5 = 10. Из них нужно выбрать четыре пары для соединения. Это можно сделать C 4 10 = 210 способами. Теперь ищем количество плохих соединений (когда найдутся два города таких, что из одного никак нельзя долететь до другого. Плохие соединения могут быть двух видов 1) есть изолированный город (из которого не выходит ни одна авиалиния 2) нет изолированного города (то есть из каждого города выходит авиалиния). Пусть изолированный город есть (его можно выбрать 5 способами. Тогда четыре авиалинии проложены (как угодно) между четырьмя остальными городами. Из C 2 4 = 6 пар городов мы выбираем 4 пары для соединения это можно сделать C 4 6 = 15 способами. Следовательно, плохих соединений с изолированным городом получается 5 · 15 = Теперь предположим, что в плохом соединении изолированного города нет. Выясним, как устроено такое соединение. Допустим, что из города А нельзя попасть в город Д. Пусть А соединён линией с Б, а Д соединён линией с Г. Имеются лишь две возможности провести оставшиеся линии достроить треугольник АБВ (он не будет связан с отрезком ГД) или достроить треугольник ВГД (он не будет связан с отрезком АБ). Итак, плохое соединение без изолированного города — это треугольник плюс несвязанный с ним отрезок, и таких соединений столько же, сколько существует способов соединить два города отрезком (тогда оставшиеся три города автоматически замкнутся треугольником. Таким образом, нужно просто выбрать два города из пяти для этого имеется C 2 5 = 10 способов. Всего плохих соединений получается 75+10 = 85. Следовательно, искомое число соединений равно 210 − 85 = Формула включений и исключений Действуя по схеме ни одного равно общему числу минус хотя бы один, мы должны уметь вычислять хотя бы один, то есть находить число объектов, обладающих хотя бы одним из указанных свойств. С теоретико-множественной точки зрения речь идёт о нахождении числа элементов в объединении нескольких множеств. В такой ситуации часто приходит на помощь формула включений и исключений. В качестве элементарного примера рассмотрим следующую задачу. Задача. Каждый ученик класса побывал в театре или в кино. В театр сходили 22 человека. В кино были 15 человек. Ив театре, ив кино были 7 человек. Сколько учеников в классе? Решение. Если мы найдём сумму 22 + 15, то окажется, что каждого, кто побывали в театре, и в кино, мы посчитали дважды (например, если Вася сходили в театр, ив кино, то один раз он вошёл в эту сумму в числе 22 театралов, а второй разв числе 15 «киношников»). Поэтому найденная сумма на 7 больше количества учеников в классе. Следовательно, в классе + 15 − 7 = 30 человек Число элементов конечного множества A называется мощностью этого множества и обозначается. Формула включений и исключений даёт возможность находить мощность объединения любого конечного набора множеств. Формула включений и исключений для двух множеств. Для любых конечных множеств и B справедливо равенство ∪ B| = |A| + |B| − |A ∩ Доказательство формулы ( 7 ) почти дословно повторяет решение последней задачи суммируя мощности множеств A и B, мы дважды учитываем каждый элемент в их пересечении (один раз — со стороны множества A, второй раз — со стороны множества B). Поэтому мощность пересечения надо вычесть. Можно также доказать формулу ( 7 ) с помощью следующего наглядного рисунка Пусть x — число элементов множества A, не входящих в B; y — число элементов B, не входящих в A; z — число элементов в пересечении A и B. Тогда x + z = |A|, y + z = |B|, и мы имеем ∪ B| = x + y + z = (x + z) + (y + z) − z = |A| + |B| − |A ∩ Формула включений и исключений для трёх множеств. Для любых конечных множеств, B и C справедливо равенство ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |A ∩ C| + |A ∩ B ∩ Почему так получается Назовём двукратными элементы, входящие в пересечение ровно двух множеств, и трёхкратными — элементы, входящие в пересечение трёх множеств. Сложив мощности A, B и C, мы дважды учли каждый двукратный элемент и трижды — каждый трёх- кратный. Вычтя три попарных пересечения, мы восстановили справедливость в отношении двукратных элементов, но теперь оказались полностью неучтёнными трёхкратные элементы. Поэтому надо добавить мощность тройного пересечения. Приведём также доказательство формулы ( 8 ) с помощью следующего рисунка y z p q r s 42 Здесь x, y, z количества однократных элементов (входящих лишь водно изданных множеств количества двукратных элементов s — число трёхкратных элементов. Имеем ∪ B ∪ C| = x + y + z + p + q + r + s = = (x + p + q + s) + (y + p + r + s) + (z + q + r + s) − (p + s) − (q + s) − (r + s) + s = = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |A ∩ C| + |A ∩ B ∩ Задача. В группе 40 туристов. Из них 20 человек говорят по-английски, 15 — по-французски, 11 — по-испански. Английский и французский знают семь человек, английский и испанский пятеро, французский и испанский — трое. Два туриста говорят на всех трёх языках. Сколько человек группы не знают ни одного из этих языков? Решение. Пусть A множество туристов группы, знающих английский, F — французский — испанский. Тогда |A| = 20, |F | = 15, |I| = 11, |A ∩ F | = 7, |A ∩ I| = 5, |F ∩ I| = 3, |A ∩ F ∩ I| = 2. Сколько человек говорят хотя бы на одном из этих языков По формуле включений и исключений для трёх множеств имеем ∪ F ∪ I| = |A| + |F | + |I| − |A ∩ F | − |A ∩ I| − |F ∩ I| + |A ∩ F ∩ I| = = 20 + 15 + 11 − 7 − 5 − 3 + 2 = Значит, ни одного изданных языков не знают 40 − 33 = 7 человек. Теперь мы готовы привести формулу включений и исключений для любого конечного числа множеств, которая обобщает формулы ( 7 ) и (Формула включений и исключений. Для любых конечных множеств A 1 , A 2 , . . . , A n справедливо равенство A 2 ∪ . . . ∪ A n | = X i |A i | − X i i ∩ A j | + X i i ∩ A j ∩ A k |− − X i i ∩ A j ∩ A k ∩ A l | + . . . + (−1) n+1 |A 1 ∩ A 2 ∩ . . . ∩ A n |. (Выглядит формула ( 9 ) громоздко, но суть её проста сначала суммируем мощности всех множеств (n слагаемых, затем вычитаем мощности всех попарных пересечений (C 2 n слагаемых), затем прибавляем мощности всех тройных пересечений (C 3 n слагаемых) итак далее, чередуя знаки, до последнего слагаемого — мощности пересечения всех n множеств. Для доказательства формулы ( 9 ) нам понадобится вспомогательное тождество. Лемма. Для любого натурального m справедливо равенство C 2 m + C 3 m − . . . + (−1) m+1 C m m = Доказательство леммы. Воспользуемся биномом Ньютона = (1 − 1) m = m X k=0 C k m · 1 m−k · (−1) k = 1 + m X k=1 (−1) k C k m = 1 − m X k=1 (−1) k+1 C k откуда = m X k=1 (−1) k+1 C k m = C 1 m − C 2 m + C 3 m − . . . + (−1) m+1 C m Лемма доказана Доказательство формулы включений и исключений. Возьмём произвольный элемент x ∈ A 1 ∪ A 2 ∪ . . . ∪ A n . Покажем, что x учитывается правой частью формулы ( 9 ) в точности один раз. Предположим, что x принадлежит пересечению ровно m наших множеств не ограничивая общности, можно считать, что x принадлежит множествами не принадлежит множествам A m+1 , . . . , A n . Тогда впервой сумме элемент x посчитан m = C 1 m разв слагаемых |A 1 |, . . . , |A m |); • во второй сумме A j | элемент x посчитан C 2 m раз (ведь количество попарных пересечений A i ∩ A j , для которых i, j ∈ {1, 2, . . . , m}, равно C 2 m ); • в третьей сумме A j ∩ A k | элемент x посчитан C 3 m раз (ведь количество пересечений, для которых i, j, k ∈ {1, 2, . . . , m}, равно C 3 m ); • в й сумме m |A i 1 ∩ A i 2 ∩ . . . ∩ A i m | элемент x посчитан 1 = C m раз (он войдёт только в слагаемое |A 1 ∩ A 2 ∩ . . . ∩ A m |); • суммы, содержащие m + 1 и более пересечений, не учитывают элемент x, поскольку x не входит в пересечение более чем m множеств. Таким образом, элемент x оказывается посчитанным C 1 m − C 2 m + C 3 m − . . . + (−1) m+1 C m m раз. Согласно лемме это выражение равно единице, что и требовалось. Формула ( 9 ) тем самым доказана. Перейдём к рассмотрению задач, которые можно решить с помощью формулы включений и исключений. 5.3 Задача о беспорядках Ранее мы привели частный случай задачи о шляпах (для четырёх гостей) и решили её непосредственным перебором. Теперь рассмотрим данную задачу в общем виде. Задача. (Леонард Эйлер) Войдя в ресторан, n гостей оставили швейцару свои шляпы, а на выходе получили их обратно. Швейцар раздал шляпы случайным образом. Сколько существует вариантов, при которых каждый гость получит чужую шляпу? Решение. Занумеруем гостей числами 1, 2, . . . , n итак же занумеруем шляпы (при этом я шляпа принадлежит i-му гостю. Тогда любая перестановка k 1 k 2 . . . k чисел 1, 2, . . . , n обозначает вариант разбора шляп, при котором й гость получил k ю шляпу. Например, в случае четырёх человек перестановка 4132 означает, что первый получил четвёртую шляпу 4), второй — первую (k 2 = 1), третий — третью (свою, k 3 = 3) и четвёртый — вторую 2). Наоборот, каждый вариант разбора шляп обозначается единственной перестановкой чисел 1, 2, . . . , Будем говорить, что в перестановке k 1 k 2 . . . k чисел 1, 2, . . . , n число i стоит на своём месте, если k i = i (например, в перестановке 4132 тройка стоит на своём месте. Нас интересует количество беспорядков, то есть таких перестановок, в которых ни одно из чисел не стоит на своём месте. Число беспорядков можно найти, вычитая из общего количества перестановок, равного n!, количество тех перестановок, в которых хотя бы одно из чисел стоит на своём месте Пусть A i — множество перестановок, в которых число i стоит на своём месте (i = 1, 2, . . . , Искомое число N беспорядков, таким образом, равно = n! − |A 1 ∪ A 2 ∪ . . . ∪ A n | = = n! − X i |A i | + X i i ∩ A j | − X i i ∩ A j ∩ A k | + . . . + (−1) n |A 1 ∩ A 2 ∩ . . . ∩ Ясно, что |A i | = (n − 1)!, поэтому = n · (n − 1)! = Точно также и A j | = C 2 n · (n − 2)! = n(n − 1) 2! · (n − 2)! Аналогично |A i ∩ A j ∩ A k | = (n − 3)! и A j ∩ A k | = C 3 n · (n − 3)! = n(n − 1)(n − 2) 3! · (n − 3)! Теперь мы приходим к нужной формуле = n! − n! + n! 2! − n! 3! + . . . + (−1) n = n! · n X k=0 (−1) k При n = 4 найденная формула дат = 4! 2! − 4! 3! + 4! 4! = 12 − 4 + 1 = Этот результат мы получили ранее прямым перебором. Заметим, что если шляпы разбираются случайным образом, то вероятность беспорядка оказывается равной Приданная сумма стремится к пределу, равному 1/e, где e = 2,718 . . . — одна из самых распространённых математических констант (наряду с числом π), получившая обозначение также в честь Эйлера. Таким образом, если гостей много, то вероятность, что каждый уйдёт в чужой шляпе, приблизительно равна 1/e ≈ Функция Эйлера Напомним, что два натуральных числа называются взаимно простыми, если у них нет общих делителей (кроме Функция Эйлера — это функция ϕ(n) натурального аргумента n, равная количеству натуральных чисел, меньших n и взаимно простых с n (при этом ϕ(1) = 1 по определению). Например, ϕ(15) = 8, поскольку имеется 8 натуральных чисел, меньших 15 и взаимно простых с ним 1, 2, 4, 7, 8, 11, 13, 14. Функция Эйлера играет важную роль в теории чисел и криптографии Пусть n > 2. Значение функции Эйлера числа n можно найти из разложения этого числа на простые множители = p a 1 1 p a 2 2 . . . p a r r (p 1 , p 2 , . . . , p r — все различные простые делители числа n). Покажем, что) = n 1 − 1 p 1 1 − 1 p 2 1 − 1 p Если число k взаимно просто стоне делится ни на одно из чисел p 1 , p 2 , . . . , p r . Мы найдём величину ϕ(n), вычитая из n количество чисел, меньших n и делящихся хотя бы на одно из чисел p 1 , p 2 , . . . , p Пусть A i — множество чисел, меньших n и делящихся на p i (i = 1, 2, . . . , r). Имеем = n − |A 1 ∪ A 2 ∪ . . . ∪ A r | = = n − X i |A i | + X i i ∩ A j | − X i i ∩ A j ∩ A k | + . . . + (−1) r |A 1 ∩ A 2 ∩ . . . ∩ Ясно, что = n p i , |A i ∩ A j | = n p i p j , |A i ∩ A j ∩ A k | = n p i p j итак далее. Получаем) = n − X i n p i + X i p j − X i p j p k + . . . + (−1) r n p 1 p 2 . . . p r = = n 1 − 1 p 1 1 − 1 p 2 1 − 1 p что и требовалось. 5.5 Числа Стирлинга второго рода В качестве ещё одного примера применения формулы включений и исключений рассмотрим следующую комбинаторную задачу (далее предполагается, что k > Задача. Сколькими способами можно разложить m различных шаров по n различным ящикам так, чтобы ни один из ящиков не оказался пустым? Решение. Если ящики могут быть пустыми, то число способов разложить m различных шаров по n различным ящикам равно n m — это просто число размещений с повторениями Пусть A i — множество разложений шаров, при которых й ящик пуст (i = 1, 2, . . . , n). Тогда искомое число D(m, n) разложений шаров, при которых все ящики непусты, равно, n) = n m − |A 1 ∪ A 2 ∪ . . . ∪ A n | = = n m − X i |A i | + X i i ∩ A j | − X i i ∩ A j ∩ A k | + . . . + (−1) n |A 1 ∩ A 2 ∩ . . . ∩ Ясно, что = (n − 1) m , |A i ∩ A j | = (n − 2) m , |A i ∩ A j ∩ A k | = (n − 3) m итак далее. Получаем, n) = n m − C 1 n (n − 1) m + C 2 n (n − 2) m − C 3 n (n − 3) m + . . . + (−1) n · 0 = n X k=0 (−1) k C k n (n − k) m 46 Задача решена. Данная задача известна также ив другой формулировке. Прежде всего, дадим определение функция f : A → B называется сюръекцией, если каждый элемент множества B имеет прообраз (то есть для любого y ∈ B найдётся такой элемент x ∈ A, что f (x) = y). Например, функция f : R → [−1; 1], задаваемая формулой f (x) = sin x, является сюръекцией, а функция f : R → R, задаваемая той же формулой f (x) = sin x, сюръекцией уже не будет, так как число не имеет прообраза. Задача. Найти число сюръекций из элементного множества в n-элементное. Решение. Рассмотрим функцию f : A → B, где |A| = m и |B| = n. Представим себе, что элементы множества A — это шары, а элементы множества B — это ящики. Тогда функция f есть некоторый способ разложить m различных шаров в n различных ящиков при этом f будет сюръекцией в томи только в том случае, если при соответствующем разложении ни один ящик не окажется пустым. Следовательно, число сюръекций изв равно D(m, Интересна также ситуация, когда ящики неразличимы. Она приводит к отдельной комбинаторной задаче о числе разбиений множества. Задача. Сколькими способами можно разложить m различных шаров по n неразличимым ящикам так, чтобы ни один из ящиков не оказался пустым Иными словами, сколькими способами можно представить элементное множество в виде объединения n непустых непересе- кающихся подмножеств? Решение. Если ящики неразличимы, то любая перестановка n ящиков ничего не меняет, и поэтому число D(m, n) разложений m различных шаров по n различным ящикам нужно разделить на n!: S(m, n) = D(m, n) n! = 1 n! n X k=0 (−1) k C k n (n − Получилось число способов разложить m шаров по n неразличимым ящикам, или число способов представления элементного множества в виде объединения n непересекающихся непустых подмножеств. Числа S(m, n) называются числами Стирлинга второго рода. Теперь допустим, что ящики могут быть пустыми. Задача. Сколькими способами можно разложить m различных шаров по n неразличимым ящикам На число шаров в ящике ограничений нет. Решение. При произвольной раскладке наши m шаров окажутся лежащими в каких-то k ящиках (1 6 k 6 n), а остальные n − k ящиков будут пустовать. Такое разложение можно осуществить S(m, k) способами. Суммируя по k, получим искомое число способов, Задачи. Сколько существует четырёхзначных чисел, в записи которых есть хотя бы одна чётная цифра 2. Сколько существует шестизначных чисел, в записи которых есть хотя бы две одинаковых цифры 47 3. Сколько существует пятизначных чисел, в записи которых есть хотя бы две единицы 4. (ММО, 2006, 6, окружной этап) В саду у Ани и Вити росло 2006 розовых кустов. Витя полил половину всех кустов, и Аня полила половину всех кустов. При этом оказалось, что ровно три куста, самые красивые, были политы и Аней, и Витей. Сколько розовых кустов остались не политыми 5. (ММО, 2008, 7, окружной этап) Поданным опроса, проведённого в 7 Е классе, выяснилось, что 20% учеников, интересующихся математикой, интересуются ещё и физикой, а учеников, интересующихся физикой, интересуются также и математикой. И только Пете с Васей неинтересен ни один из этих предметов. Сколько человек в 7 Е, если известно, что их больше 20, но меньше 30? 26 6. Пусть A — множество букв слова абракадабра, B — множество букв слова бригантина множество букв слова каракатица. Выпишите множества A, B и C, найдите их всевозможные пересечения и проверьте формулу включений и исключений для трёх множеств. (ММО, 1938 ) Сколько существует натуральных чисел, меньших тысячи, которые не делятся ни на 5, ни на 7? |