С.Н. Селезнева - Основы дискретной математики (1060725), страница 4
Текст из файла (страница 4)
Всего пасмурных дней 9, они могут разбить все дни не более,чем на 10, промежутков. Даже при 11 солнечных днях по принципу Дирихле хотя бы один промежуток состоял бы хотя бы из двух дней.2. Продолжим рассуждения. Пусть каждый из промежутков состоитне более, чем из двух дней. Тогда заметим, что промежутков не более10, в каждом - не более двух дней, значит всего - не более 20 солнечныхдней. А по условию в сентябре был 21 солнечный день. Полученное противоречие убеждает нас, что хотя бы в одном промежутке должно бытьне менее трех дней.1.8УпражненияЗадача 1.30. 1.
В коробке лежат 2 пары одинаковых ботинок. Какоенаименьшее число ботинок нужно вынуть не глядя, чтобы среди нихобязательно оказалась одна пара?2. В корзине лежат 2 пары одинаковых носков. Какое наименьшеечисло носков нужно вынуть не глядя, чтобы среди них обязательно оказалась одна пара?6Петер Густав Лежëн Дирихле (Dirichlet) – немецкий математик XIX века.203. В коробке лежат 3 пары разных ботинок. Какое наименьшее числоботинок нужно вынуть не глядя, чтобы среди них обязательно оказаласьодна пара?4. В корзине лежат 4 пары разных носков.
Какое наименьшее числоносков нужно вынуть не глядя, чтобы среди них обязательно оказаласьодна пара?Задача 1.31. В коробке лежат 10 конфет в красных обертках, 10 в синихи 10 в желтых обертках. Какое наименьшее число конфет нужно вынутьне глядя, чтобы среди них обязательно оказались две конфеты в обертках1) одного цвета;2) разных цветов;3) красного цвета;4) не синего цвета?Задача 1.32. 1. В шахматной партии одним конем ходили 9 раз. Доказать, что конь побывал хотя бы дважды и на какой-то горизонтали, ина какой-то вертикали шахматной доски.2.
В шахматной партии одним конем ходили 8 раз. Мог ли конь побывать хотя бы раз на каждой горизонтали и на каждой вертикали шахматной доски?Задача 1.33. В трех группах учатся 60 студентов. Доказать, что хотябы два из них празднуют свой день рождения в одну и ту же неделю.Задача 1.34. В университетской сборной по футболу 60 студентов, являющихся полевыми игроками. За год сборная сыграла 40 матчей, причем в каждом матче участвовало ровно 10 игроков. Доказать, что какието два студента играли вместе по меньшей мере дважды.Задача 1.35.
Доказать, что в любой группе из n человек, где n ≥ 2, всегда найдутся хотя бы два человека, знакомые с одинаковым количествомприсутствующих.Задача 1.36. 1. Пусть даны два числа, сумма которых равна 100. Доказать, что одно из этих чисел не меньше 50 и другое из этих чисел небольше 50.2. Пусть даны числа a1 , . . . , an , сумма которых равна M . Доказать,что хотя бы одно из этих чисел не меньше n1 · M и хотя бы одно из этихчисел не больше n1 · M .21Задача 1.37.
Моток ниток проткнули 200 спицами в форме прямогоцилиндра с диаметром основания 1 мм. После этого он приобрел формушара. Может ли диаметр этого шара быть равным 1 см?Задача 1.38. Цветочный город имеет форму квадрата, который разбитна 25 одинаковых квадратных участков параллельными линиями, делящими каждую его сторону на 5 частей. Известно, что каждый жительЦветочного города враждует не более, чем с тремя другими. Можно литак расселить 25 жителей Цветочного города по этим участкам, чтобыникакие два врага не были соседями? Два квадратных участка считаются соседними, если у них общая сторона.222Элементы комбинаторики2.1Комбинаторные объектыПусть A = {a1 , .
. . , an } – множество из n элементов.Из этого множества можно выбирать элементы, которые будут образовывать подмножества с определенными свойствами. В зависимостиот свойств подмножеств получатся различные комбинаторные объекты.С каждым комбинаторным объектом связано комбинаторное число – количество комбинаторных объектов этого вида, которые можно выбратьиз исходного множества.Рассмотрим некоторые комбинаторные объекты и связанные с нимикомбинаторные числа.Определение 2.1. Размещением из n элементов по k называется упорядоченный набор k элементов из этих n элементов.Число размещений из n по k обозначается как Akn .Теорема 2.1. Число размещений из n из k равно Akn = (n)k = n(n − 1) ·. . .
· (n − k + 1).Число (n)k называется убывающим факториалом для чисел n и k.Для числа размещений верны следующие свойства:Akn = n(n − 1) . . . (n − k + 1) при n ≥ k ≥ 1;A0n = 1;Akn = 0 при n < k;Akn = n · Ak−1n−1 .Определение 2.2. Перестановкой n элементов называется упорядоченный набор всех этих элементов.Перестановка является частным случаем размещения при k = n.Число перестановок n элементов обозначается как Pn .Теорема 2.2. Число перестановок n элементов равно Pn = Ann = n! =n(n − 1) · .
. . · 1.Число n! называется факториалом числа n.Факториал является частным случаем убывающего факториала приk = n: n! = (n)n .23Для числа перестановок верны следующие свойства:Pn = n(n − 1) . . . 1 при n ≥ 1;P0 = 1;Pn = n · Pn−1 .Определение 2.3. Размещением с повторениями из n элементов по kназывается упорядоченный набор k элементов с возможными повторениями из этих n элементов.Число размещений с повторениями из n по k обозначается как Ākn .Теорема 2.3.
Число размещений с повторениями из n по k равно Ākn =nk .Определение 2.4. Сочетанием из n элементов по k называется неупорядоченный набор k элементов из этих n элементов.Число сочетаний из n по k обозначается как Cnk .Теорема 2.4. Число сочетаний из n по k равно Cnk =nk=(n)kk! .Для числа сочетаний верны следующие свойства:n!kCnk = (n)k! = k!(n−k)! при n ≥ k ≥ 1;Cn0 = 1;Cnk = 0 при n < k;k−1kCnk = Cn−1+ Cn−1.Теорема 2.5. (x + y)n =nPCnk xn−k y k .k=0Следствие 2.5.1.nPCnk = 2n .k=0Следствие 2.5.2.nP(−1)k Cnk = 0.k=0Формула в теореме2.5 называется формулой бинома Ньютона7 .
Поэтому числа nk называются биномиальными коэффициентами.Определение 2.5. Сочетанием с повторениями из n элементов по kназывается неупорядоченный набор k элементов с возможными повторениями из этих n элементов.7Исаак Ньютон (Newton) – английский математик, механик, астроном и физик XVII-XVIII веков.24Число сочетаний с повторениями из n по k обозначается как C̄nk .Теорема 2.6. Число сочетаний с повторениями из n из k равно C̄nk =k.Cn+k−1Пример 2.1. В шахматном турнире играют 10 человек. Сколько различных вариантов распределения трех призовых мест между участниками?Решение. Есть три призовых места, которые не равнозначны. На нихпретендуют 10 участников. Поэтому число различных распределенийпризовых мест равно числу размещений из 10 по 3: A310 = (10)3 =10 · 9 · 8 = 720 вариантов.Ответ: 720 вариантов.Пример 2.2.
В городском первенстве по хоккею участвуют 10 команд.Команды, занявшие три первых места, получают путевки на чемпионат страны. Сколько различных вариантов команд города на чемпионатестраны?Решение. Есть три призовых места, которые равнозначны. На них претендуют 10 команд. Поэтому число различных троек победителей равно3числу сочетаний из 10 по 3: C10= 10·9·83! = 120 вариантов.Ответ: 120 вариантов.2.2УпражненияЗадача 2.1.
Найти все возможные1) размещения по 2 из 4-х элементов множества A = {1, 2, 3, 4};2) перестановки 3-х элементов множества A = {1, 2, 3};3) сочетания по 3 из 5-ти элементов множества A = {a, b, c, d, e};4) сочетания с повторениями по 2 из 4-х элементов множестваA = {a, b, c, d}.Задача 2.2. На плоскости расположены 35 точек, никакие три из которых не лежат на одной прямой. Сколько треугольников с вершинами вэтих точках можно построить?Задача 2.3. Города A, B, C, D и E попарно соединены дорогами. Сколько разных маршрутов путешествия из города A в город E с посещением еще каких-то двух городов можно составить? Предполагается, что вмаршруте каждый город присутствует не более одного раза, и маршруты, отличающиеся порядком следования городов, различны.25Задача 2.4.
Сколькими способами можно распределить среди 20 студентов группы четыре билета в театр, если1) билеты на один спектакль, и каждый студент может получитьне более одного билета;2) билеты на один спектакль, и каждый студент может получитьсколько угодно билетов;3) все билеты на разные спектакли, и каждый студент может получить не более одного билета;4) все билеты на разные спектакли, и каждый студент может получить сколько угодно билетов?Билеты на одно мероприятие считаются равнозначными.Задача 2.5. Есть 4 билета на концерт, 5 билетов в театр и 7 билетовв цирк. Сколькими способами их можно распределить среди 25 студентов группы, если каждый студент может получить не более одного билета на каждое мероприятие? Билеты на одно мероприятие считаютсяравнозначными.Задача 2.6.
1. Девочка нанизала n разных бусин на английскую булавку. Сколько различных украшений может получиться таким образом?Два украшения различны, если они отличаются порядком следованиябусин на булавке.2. Девочка собрала n бусин разного цвета и составила из них ожерелье.Сколько различных ожерелий может получиться таким образом? Дваожерелья различны, если они отличаются порядком следования бусин.Задача 2.7. У англичан принято давать детям несколько имен. Сколькими способами можно можно назвать ребенка, если ему дадут не болеетрех имен из 300 возможных, и при этом1) имена могут повторяться;2) все имена различны?Задача 2.8. Гости рассаживаются за круглым столом.
Два рассаживания считаются одинаковыми, если при них у каждого гостя одни и те жесоседи.1) Сколькими разными способами можно так рассадить за столом n(n ≥ 2) человек?2) Сколькими разными способами можно так рассадить n мужчин иn женщин (n ≥ 1), чтобы еще любые два соседа оказались разного пола?26Задача 2.9. Пусть A1 , .
. . , An – конечные множества. Обозначим количество элементов, принадлежащих в точности m множествам из множеств A1 , . . . , An , как N (n, m), m ≥ 1.1. Доказать, что1) N (2, 1) = |A1 | + |A2 | − 2 · |A1 ∩ A2 |;2) N (2, 2) = |A1 ∩ A2 |.2. Доказать индукцией по n, опираясь на п. 1, что если 1 ≤ m ≤ n, тоN (n, m) =n−mXXm(−1)k · Cm+k· |Ai1 ∩ . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
