Цепочки и множества. Упорядоченные наборы Неупорядоченные наборы Операции надмножествами 4
 Скачать 222.91 Kb.
|
|
ИВ. Яковлев | Материалы по математике | MathUs.ru Цепочки и множества Содержание 1 Упорядоченные наборы Неупорядоченные наборы Операции надмножествами 4 Задачи 3 Исчерпывающий перебор конечного числа вариантов является совершенно законным способом решения задач. Однако в задачах с большим числом вариантов следует искать другие подходы. Ниже мы подробно рассмотрим наиболее распространённые комбинаторные схемы размещения и сочетания. Однако прежде нам нужно обсудить понятия цепочки и множества (то есть упорядоченных и неупорядоченных наборов, которые лежат в основе этих схем. 1 Упорядоченные наборы В некоторых ситуациях порядок следования объектов важен для нас, а в некоторых — не важен. Пусть, например, нужно решить систему уравнений + y = 3, x − y = Легко находим решение x = 2, y = 1 и пишем ответ в виде пары (2, 1). По общепринятому соглашению, первым числом нашей пары является значение x, а вторым числом — значение Такую пару называют упорядоченной, поскольку порядок следования чисел важен записывая ответ, мы не можем поменять числа местами Запись (1, 2) означала бы, что x = 1 и y = 2; эта пара, заметим, не является решением данной системы. Пары (2, 1) и (1, 2) — это две разные упорядоченные пары. Упорядоченный набор объектов мы называем цепочкой, асами объекты — элементами цепочки. Цепочка, составленная по порядку из элементов a 1 , a 2 , . . ., a k , записывается a 1 a 2 . . . a или (a 1 , a 2 , . . . , a k ); число k называется длиной цепочки. При изменении порядка следования элементов мы, вообще говоря, получим другую цепочку (той же длины. Рассмотрим некоторые примеры цепочек Пусть точка на координатной плоскости имеет абсциссу x = 0 и ординату y = 1. В таком случае мы записываем координаты точки в виде упорядоченной пары (0, 1). Это — цепочка длины 2, составленная из чисел 0 ив указанном порядке. Порядок следования чисел важен ведь (1, 0) — это уже другая точка плоскости (то есть другая упорядоченная пара или другая цепочка Аналогично, пусть точка координатного пространства имеет координаты x = 0, y = 1 и z = 2. Мы записываем её координаты в виде (0, 1, 2). Это — цепочка длины 3, составленная из чисел 0, 1 иона называется также упорядоченной тройкой чисел 0, 1 и 2. Порядок следования чисел важен при изменении порядка мы получим другую точку координатного пространства (другую упорядоченную тройку, другую цепочку). 1 Другое название упорядоченного набора — кортеж • Слово автор является цепочкой длины 5, составленной из буква, в, тор. Порядок следования букв важен например, слово отвар, составленное из тех же букв, — это уже другое слово (другая цепочка). 2 Неупорядоченные наборы Допустим теперь, что требуется решить квадратное уравнение x 2 − 3x + 2 = Его корнями служат числа 1 и 2. Мы записываем пару этих корней в виде {1, 2}. Такую пару называют неупорядоченной, поскольку порядок следования чисел в данной записи не играет роли в самом деле, мы можем записать ответив виде {2, 1}, перечислив те же корни в другом порядке. Пары {1, 2} и {2, 1} — это одна и та же неупорядоченная пара. Всякий неупорядоченный набор объектов есть нечто иное, как множество сами объекты являются элементами множества. Множество, состоящее из элементов a 1 , a 2 , . . ., a k , записывается. Порядок следования элементов неважен при изменении порядка мы получим тоже множество. Например, как мы видели выше, {1, 2} = {2, 1}. Рассмотрим некоторые примеры множеств Множество корней уравнения x(x−1)(x−2) = 0 есть A = {0, 1, 2}. Это — неупорядоченная тройка чисел 0, 1 и 2, которые являются элементами множества A. Множество A можно записать ив любом другом порядке, например A = {2, 0, 1}. • Множество букв русского алфавита состоит из 33 элементов а, б, в, . . . , ю, я Множество букв слова математика есть M = мате, и, к. Множество букв слова «физика» есть F = физ, ка Запись a ∈ A означает, что объект a является элементом множества A, и читается «a принадлежит множеству A». Если a не является элементом множества A (a не принадлежит то это записывается так a / ∈ Множество A называется подмножеством множества B (обозначается A ⊂ B), если любой элемент множества A является элементом множества B. Например, {1, 2, 3} ⊂ {1, 2, 3, 4, Ясно, что для любого множества A выполнено A ⊂ Два множества называются равными, если они состоят из одних и тех же элементов. Иными словами, множество A равно множеству B в томи только в том случае, если A ⊂ B и B ⊂ Например, {1, 2, 3} = {3, 2, Имеется множество, которое не содержит элементов это пустое множество, которое обозначается. Например, множество действительных корней уравнения x 2 + 1 = 0 пусто. Любопытно, что пустое множество является подмножеством любого множества. Докажем данное утверждение от противного. Предположим, что это не так, то есть пустое множество не является подмножеством некоторого множества A. Тогда найдётся элемент пустого множества, который не принадлежит множеству A. Но пустое множество не содержит элементов. Противоречие. 3 Операции надмножествами Наиболее важные для нас операции надмножествами объединение, пересечение и разность множеств Объединение множеств A и B есть множество A ∪ B, которое состоит из всех элементов, принадлежащих хотя бы одному из множеств A или B. Так, для множеств M и F из рассмотренного выше примера имеем M ∪ F = мате, и, к, ф, з. Аналогично определяется объединение трёх и большего числа множеств. Пересечение множеств A и B есть множество A ∩ B, которое состоит из всех элементов, принадлежащих как множеству A, таки множеству B. Например, для тех же множеств M и имеем M ∩ F = аи, к. Множества, у которых нет общих элементов (то есть пересечение которых пусто, называются непересекающимися. Разность множеств A и B есть множество A \ B, которое состоит из всех элементов множества, не принадлежащих множеству B. Например, M \ F = м, те Задача. (Высшая проба, 2014, 9 ) В детский сад завезли карточки для обучения чтению: на некоторых написано МА, на остальных — «НЯ». Каждый ребёнок взял три карточки и стал составлять из них слова. Оказалось, что слово МАМА могут сложить из своих карточек детей, слово НЯНЯ — 30 детей, а слово МАНЯ — 36 детей. У скольких ребят все три карточки одинаковы? Решение. Возможны четыре вида наборов из трёх карточек МАМА, МА пусть a детей имеют такой набор МАМАНЯ пусть b детей имеют такой набор МАНЯ, НЯ; пусть c детей имеют такой набор НЯНЯ, НЯ; пусть d детей имеют такой набор. Очевидно, что a + b = 25, c + d = 30, b + c = 36. Нас интересует величина a + d. Имеем + d = (a + b) + (c + d) − (b + c) = 25 + 30 − 36 = Итак, три карточки одинаковы у 19 детей. 4 Задачи 1. Докажите, что для любых трёх множеств A, B и C выполнены равенства: а) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ б) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ в) (A ∪ B) \ C = (A \ C) ∪ (B \ г) A \ (B ∪ C) = (A \ B) ∩ (A \ C). 2. (Математический праздник, 1990, 6–7 ) Среди математиков каждый седьмой — философа среди философов каждый девятый — математик. Кого больше — философов или математиков? Философов(в предположении ихсуществования) 3. (Физтех, 2013, 8 ) На маленьком острове 2/3 всех мужчин женаты и 3/5 всех женщин замужем. Сколько жителей острова состоят в браке, если всего там проживает 1900 человек 4. (Физтех, 2014, 7–8 ) На данный момент в классе 20 учеников, получивших сначала учебного года хотя бы одну двойку, 17 учеников, получивших не менее двух двоек, 8 учеников, получивших не менее трёх двоек, три ученика, получивших не менее четырёх двоек, один ученик, получивший пять двоек. Больше пяти двоек нет ни у кого. Сколько всего двоек в журнале 3 5. (Физтех, 2014, 9–10 ) Сколько одинаковых членов находится среди первых 2000 членов арифметических прогрессий 9, 11, 13, . . . и 3, 8, 13, . . . ? 400 6. (Высшая проба, 2014, 9 ) В детский сад завезли карточки трёх видов для обучения чтению: на некоторых написано пана некоторых «сть», и на некоторых ко. Каждый из 40 детей взял три карточки (необязательно разные) и стал составлять из них слова. Оказалось, что слово папа могут сложить из своих карточек 23 ребёнка, слово пасть — 19 детей, слово «кость» — 11 детей, слово пакость — 4 ребёнка. При этом каждый ребёнок может сложить хотя бы одно слово из перечисленных. Сколько детей взяли себе три карточки со слогами папа, «сть»? 9 7. (Турнир городов, 1985, 7–10 ) В классе 32 ученика. Было организовано 33 кружка, причём каждый кружок состоит из трёх человек и никакие два кружка не совпадают по составу. Доказать, что найдутся такие два кружка, которые пересекаются ровно по одному ученику. (ММО, 1985, 10 ) Даны 1985 множеств, каждое из которых состоит из 45 элементов, причём объединение любых двух множеств содержит ровно 89 элементов. Сколько элементов содержит объединение всех этих 1985 множеств 9. (Всеросс., 1997, ОЭ, 11 ) Члены Государственной Думы образовали фракции так, что для любых двух фракций A и B (необязательно различных) A ∪ B — тоже фракция (через обозначается множество всех членов Думы, не входящих в C). Докажите, что для любых двух фракций A и B множество A ∪ B — также фракция. (Всеросс., 2016, РЭ, 9.6 ) Назовём непустое (конечное или бесконечное) множество A, состоящее из натуральных чисел, полным, если для любых натуральных a и b (необязательно различных и необязательно лежащих в A), при которых a + b лежит в A, число ab также лежит в A. Найдите все полные множества натуральных чисел. (Всеросс., 2016, РЭ, 10–11.5 ) Назовём непустое (конечное или бесконечное) множество состоящее из действительных чисел, полным, если для любых действительных a и b (необязательно различных и необязательно лежащих в A), при которых a + b лежит в A, число ab также лежит в A. Найдите все полные множества действительных чисел. (Всеросс., 2018, РЭ, 9.4 ) Кондитерская фабрика выпускает N сортов конфет. На Новый год фабрика подарила каждому из 1000 учеников школы подарок, содержащий по конфете нескольких сортов (составы подарков могли быть разными. Каждый ученик заметил, что для любых 11 сортов конфет он получил конфету хотя бы одного из этих сортов. Однако оказалось, что для любых двух сортов найдётся ученик, получивший конфету ровно одного из этих двух сортов. Найдите наибольшее возможное значение N . 4 13. (Всеросс., 2019, РЭ, 11.9 ) В классе m учеников. В течение сентября каждый из них несколько раз ходил в бассейн никто не ходил дважды в один день. Первого октября выяснилось, что все количества посещений бассейна у учеников различны. Более того, для любых двух из них обязательно был день, когда первый из них был в бассейне, а второй — нет, и день, когда, наоборот, второй из них был в бассейне, а первый — нет. Найдите наибольшее возможное значение В сентябре 30 дней |