С.Н. Селезнева - Основы дискретной математики (1060725), страница 3
Текст из файла (страница 3)
. . , ck . Введем множествоA = {0, 1, 2} и рассмотрим его k-ю декартову степень Ak . Сопоставимкаждому элементу (a1 , . . . , ak ) ∈ Ak взаимно-однозначно решение (X, Y )исходного уравнения по следующему правилу:если ai = 0, то ci ∈/ X, ci ∈ Y ;если ai = 1, то ci ∈ X, ci ∈/ Y;если ai = 2, то ci ∈ X, ci ∈ Y , i = 1, . . . , k.По изложенным выше рассуждениям каждому элементу множества Akсоответствует решение исходного уравнения (X, Y ), и, наоборот, для каждого решения (X, Y ) найдется соответствующий ему элемент множества Ak .Найдено взаимно-однозначное соответствие между множеством Ak имножеством решений исходного уравнения.
Следовательно, эти множества равномощны (по теореме 1.1). Откуда число решений исходногоуравнения равно 3k .Ответ: 3k решений.1.4УпражненияЗадача 1.12. Каким числом можно ограничить количество двухбуквенных существительных русского языка? (Омонимы не рассматриваются).14Задача 1.13. Номер проездного билета состоит из 4-х цифр. Сколькосчастливых“ билетов среди них? (Билет счастливый“, если сумма двух””первых цифр номера равна сумме двух последних его цифр).Задача 1.14. В азбуке Морзе каждая буква или управляющий знакзадается некоторой последовательностью символов из множества A ={·, −}. Последовательности какой длины должны присутствовать в азбуке Морзе, чтобы иметь возможность по меньшей мере закодироватьвсе буквы русского алфавита?Задача 1.15.
Пусть A = {0, 1}. Словом длины n в алфавите A назовемпроизвольный элемент множества An , n ≥ 1. Подсчитать количествослов длины n,1)2)3)4)5)у которых нет никаких особенностей (то есть общего вида);не начинающихся с 1;оканчивающихся на 00;начинающихся на 0 и оканчивающихся на 1;являющихся палиндромами (то есть с начала и с конца читающихся одинаково);6) у которых четное число нулей;7) у которых нечетное число единиц;8) в которых встречаются и нули, и единицы.Задача 1.16.
Пусть X, Y – неизвестные множества, X, Y ⊆ C, где C –заданное множество, |C| = k. Найти число решений следующих уравнений:1) X ∩ Y = ∅;3) X ∪ Y = X ∩ Y ;2) X \ Y = ∅;4) X ∩ Y = X \ Y .Задача 1.17. Пусть X, Y, Z – неизвестные множества, X, Y, Z ⊆ C, гдеC – заданное множество, |C| = k. Найти число решений следующихуравнений:1)2)3)4)X ∪ Y = C \ (X ∩ Y );X ∪ Y = C \ (X \ Y );(X ∩ Y ) ∪ Z = X ∪ Z;(X ∩ Y ) \ Z = X \ Z;5)6)7)8)15(X(X(X(X∪Y)\Z =X ∪Y;∩ Y ) \ Z = Y ∩ Z;∪ Y ) ∩ Z = X ∪ (Y ∩ Z);∪ Y ) \ Z = (X ∩ Y ) \ Z.Задача 1.18. Пусть X, Y – неизвестные множества, а C, D – заданныемножества, C ⊆ D, |C| = k, |D| = m, k ≤ m.
Найти число решенийследующих систем:X ∩Y =CX \Y =C1);2).X, Y ⊆ DX, Y ⊆ DЗадача 1.19. 1. Существуют ли конечные множества A и B, для которых верны следующие свойства? Если существуют, привести примертаких множеств A и B, если не существуют, объяснить почему:1) |(A × B) ∪ (B × A)| = k, k = 0, 1, 2, 3;2) |(A × B) ∩ (B × A)| = k, k = 0, 1, 2, 3;3) |(A × B) \ (B × A)| = k, k = 0, 1, 2, 3;4) |((A × B) \ (B × A)) ∪ ((B × A) \ (A × B))| = k, k = 0, 1, 2, 3.2. Выяснить для случаев 1)-4) п. 1, какие значения может приниматьчисло k, если A и B – некоторые конечные множества. Для каждогоиз возможных его значений привести пример множеств A и B, когда онодостигается.Задача 1.20.
1. Доказать, что для произвольных конечных множеств Aи B верно равенство|(A × B) \ (B × A)| = |(B × A) \ (A × B)|.2. Доказать, что число |((A × B) \ (B × A)) ∪ ((B × A) \ (A × B))| –четно для произвольных конечных множеств A и B.Задача 1.21. Натуральные числа k и m называются взаимно простыми, если их наибольший общий делитель равен 1.
Для каждого натурального числа n обозначим как ϕ(n) количество натуральных чисел,не превосходящих n и взаимно простых с ним. Функция ϕ(n) называется функцией Эйлера4 .mk1Пусть n = pm1 · . . . · pk , где p1 , . . . , pk – попарно различные простыечисла (см. задачу 1.26, п. 6), m1 , . . . , mk ≥ 1, – каноническое разложениечисла n на простые сомножители.В предположении, что известно каноническое разложение числа nна простые сомножители, найти формулу для значений функции ϕ(n).4Леонард Эйлер (Euler) – математик, механик, физик и астроном XVIII века, по происхождениюшвейцарец.161.5Формула включений-исключенийТеорема 1.3. Пусть A1 , .
. . , An – конечные множества, n ≥ 2. Тогда|A1 ∪ . . . ∪ An | =nXX(−1)k−1 |Ai1 ∩ . . . ∩ Aik |.k=1 1≤i1 <...<ik ≤nФормула в теореме 1.3 называется формулой включений-исключений.Пример 1.5. Подсчитать количество трехзначных чисел, в записи которых есть хотя бы одна цифра 7.Решение.
Пусть множество A1 содержит все числа вида 7bc, множество A2 содержит все числа вида a7c и множество A3 содержит все числавида ab7, где a ∈ {1, 2, . . . , 9}, b, c ∈ {0, 1, . . . , 9}.Если в записи трехзначного числа есть хотя бы одна цифра 7, то эточисло принадлежит объединению множеств A1 , A2 и A3 . По формулевключений-исключений|A1 ∪A2 ∪A3 | = |A1 |+|A2 |+|A3 |−|A1 ∩A2 |−|A1 ∩A3 |−|A2 ∩A3 |+|A1 ∩A2 ∩A3 |.Находим|A1 | = 100, |A2 | = |A3 | = 90,|A1 ∩ A2 | = |A1 ∩ A3 | = 10, |A2 ∩ A3 | = 9,|A1 ∩ A2 ∩ A3 | = 1.Откуда |A1 ∪ A2 ∪ A3 | = 100 + 90 + 90 − 10 − 10 − 9 + 1 = 252.Ответ: 252 числа.1.6УпражненияЗадача 1.22. 1. Доказать, что для любых конечных множеств A и Bверно:1) |A ∪ B| = |A| + |B| − |A ∩ B|;2) |A \ B| = |A| − |A ∩ B|.2.
Применив один шаг индукции, опираясь на п. 1, доказать, что длялюбых конечных множеств A, B и C верно:1) |A∪B ∪C| = |A|+|B|+|C|−|A∩B|−|A∩C|−|B ∩C|+|A∩B ∩C|;2) |A \ (B ∪ C)| = |A| − |A ∩ B| − |A ∩ C| + |A ∩ B ∩ C|.17Задача 1.23. В июле было 20 солнечных и 15 дождливых дней. Доказать, что по меньшей мере 4 дня июля были и солнечными, и дождливыми.Задача 1.24. Номерной знак автомобиля состоит из трех цифр. Сколькономеров автомобилей, в которых две одинаковые цифры стоят подряд?(Например, 773, 122).Задача 1.25. Пусть A = {0, 1}.
Словом длины n в алфавите A назовемпроизвольный элемент множества An , n ≥ 1. Определим подмножествамножества An : B – множество слов с нечетным количеством единиц, C –множество слов, начинающихся с 0, и D – множество слов, оканчивающихся на 11. Найти мощности следующих множеств:1)2)3)4)B ∪ C;B \ D;B ∪ C ∪ D;B ∪ (C ∩ D);5)6)7)8)B ∩ (C ∪ D);B \ (C ∪ D);C \ (B ∩ D);D \ (B \ C).Задача 1.26. 1. Доказать, что количество натуральных чисел, делящихся на число p и не превосходящих числа n, равно b np c.52.
Найти количество натуральных чисел, меньших 100, которые делятся или на 3, или на 5.3. Найти количество натуральных чисел, не больших 1000, которыеделятся или на 10, или на 15, или на 24.4. Найти количество натуральных чисел, меньших 100, которые не делятся ни на 7, ни на 11.5. Найти количество натуральных чисел, не больших 1000, которыене делятся ни на 15, ни на 20, ни на 36.6. Натуральное число называется простым, если оно имеет толькодва делителя: 1 и самого себя.
Натуральное число, не являющееся простым, называется составным. По определению число 1 не является нипростым, ни составным. Найти количество простых чисел, меньших 100.7. По формуле включений-исключений, опираясь на п. 1, вывести формулу для подсчета количества натуральных чисел, делящихся хотя бына одно из простых чисел p1 , . . . , pk и не превосходящих числа n.5выражение bxc обозначает максимальное целое число, не превосходящее число x18√8. Пусть p1 , . .
. , pk – все простые числа, не большие числа n. По формуле включений-исключений, опираясь на п. 1, вывести формулу дляподсчета количества простых чисел, не превосходящих числа n.Задача 1.27. Каждый из студентов группы изучает хотя бы один иностранный язык. Известно, что английский изучают 15 человек, французский – 10 человек, немецкий – 3 человека, английский и французский – 5 человек, английский и немецкий – 2 человека, французский инемецкий – 1 человек. При этом никто не изучает все три языка. Найтичисленность группы.Задача 1.28.
При исследовании читательских интересов студентов оказалось, что 60 % студентов читают журнал А, 50 % – журнал В, 50 % –журнал С, 30 % – журналы А и В, 50 % – журналы А и С, 20 % – журналы В и С, 20 % – журналы А, В и С. Сколько процентов студентов1) не читают ни одного из журналов;2) читают хотя бы один журнал;3) читают не менее двух журналов;4) читают ровно два журнала.Задача 1.29. Симметрической разностью множеств A и B называетсямножествоA4B = {x | x ∈ A, x ∈/ B или x ∈/ A, x ∈ B}.1.
Обосновать следующие свойства операции 4:1) коммутативность: A4B = B4A;2) ассоциативность: (A4B)4C = A4(B4C).2. Доказать, что множество A1 4 . . . 4An не зависит от расстановкискобок, и произвольный элемент x принадлежит этому множеству, еслии только если он содержится в нечетном числе множеств A1 , . .
. , An .3. Доказать, что для любых конечных множеств A и B верно:|A4B| = |A| + |B| − 2 · |A ∩ B|.4. Доказать по индукции, опираясь на п. 3, что если множества A1 ,. . . , An – конечны, то|A1 4 . . . 4An | =nXX(−1)k−1 · 2k−1 · |Ai1 ∩ . . . ∩ Aik |.k=1 1≤i1 <...<ik ≤n191.7Принцип ДирихлеПринцип Дирихле6 состоит в следующем: если есть n мест, то, как бымы не размещали (n + 1) объект по этим n местам, всегда найдется хотябы одно место, где будет не менее двух объектов.Как правило, принцип Дирихле формулируется так:Принцип Дирихле: Если есть n клеток и (n+1) кролик, то, как бы мы”не размещали кроликов по клеткам, всегда найдется клетка, в которойбудет не менее двух кроликов“.Пример 1.6.
В сентябре 21 день был солнечным. Доказать, что1) в сентябре два дня подряд была солнечная погода;2) хотя бы однажды три подряд идущих дня сентября были солнечными.Решение. 1. Выпишем в линейку числа с единицы до тридцати, означающие дни сентября. Пасмурные дни, которых было 30 − 21 = 9, заштрихуем. Они разбивают все дни сентября на промежутки из солнечных дней.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
