Цепочки и множества

Упорядоченные наборы

В некоторых ситуациях порядок следования объектов важен для нас, а в некоторых — не важен. Пусть, например, нужно решить систему уравнений

x + y = 3,

x − y = 1.

Легко находим решение: x = 2, y = 1 и пишем ответ в виде пары: (2, 1). По общепринятому соглашению, первым числом нашей пары является значение x, а вторым числом — значение y. Такую пару называют упорядоченной, поскольку порядок следования чисел важен; записывая ответ, мы не можем поменять числа местами! Запись (1, 2) означала бы, что x = 1 и y = 2; эта пара, заметим, не является решением данной системы. Пары (2, 1) и (1, 2) — это две разные упорядоченные пары.

Упорядоченный набор объектов мы называем цепочкой, а сами объекты — элементами цепочки. Цепочка, составленная по порядку из элементов a1, a2, . . ., ak, записывается a1a2 . . . ak или (a1, a2, . . . , ak); число k называется длиной цепочки. При изменении порядка следования элементов мы, вообще говоря, получим другую цепочку (той же длины). Рассмотрим некоторые примеры цепочек.

Пусть точка на координатной плоскости имеет абсциссу x = 0 и ординату y = 1. В таком случае мы записываем координаты точки в виде упорядоченной пары (0, 1). Это — цепочка длины 2, составленная из чисел 0 и 1 в указанном порядке. Порядок следования чисел важен: ведь (1, 0) — это уже другая точка плоскости (то есть другая упорядоченная пара или другая цепочка).

Аналогично, пусть точка координатного пространства имеет координаты x = 0, y = 1 и z = 2. Мы записываем её координаты в виде (0, 1, 2). Это — цепочка длины 3, составленная из чисел 0, 1 и 2; она называется также упорядоченной тройкой чисел 0, 1 и 2. Порядок следования чисел важен: при изменении порядка мы получим другую точку координатного пространства (другую упорядоченную тройку, другую цепочку).

Слово автор является цепочкой длины 5, составленной из букв а, в, т, о, р. Порядок следования букв важен: например, слово отвар, составленное из тех же букв, — это уже другое слово (другая цепочка).

Неупорядоченные наборы

Допустим теперь, что требуется решить квадратное уравнение

x − 3x + 2 = 0.

Его корнями служат числа 1 и 2. Мы записываем пару этих корней в виде {1, 2}. Такую пару называют неупорядоченной, поскольку порядок следования чисел в данной записи не играет роли; в самом деле, мы можем записать ответ и в виде {2, 1}, перечислив те же корни в другом порядке. Пары {1, 2} и {2, 1} — это одна и та же неупорядоченная пара.

Всякий неупорядоченный набор объектов есть не что иное, как множество; сами объекты являются элементами множества. Множество, состоящее из элементов a1, a2, . . ., ak, записывается {a1, a2, . . . , ak}. Порядок следования элементов не важен; при изменении порядка мы получим то же множество. Например, как мы видели выше, {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 ∈ A.

Множество A называется подмножеством множества B (обозначается A ⊂ B), если любой элемент множества A является элементом множества B. Например, {1, 2, 3} ⊂ {1, 2, 3, 4, 5}. Ясно, что для любого множества A выполнено A ⊂ A.

Два множества называются равными, если они состоят из одних и тех же элементов. Иными словами, множество A равно множеству B в том и только в том случае, если A ⊂ B и B ⊂ A. Например, {1, 2, 3} = {3, 2, 1}.

Имеется множество, которое не содержит элементов: это пустое множество, которое обозначается ∅. Например, множество действительных корней уравнения x + 1 = 0 пусто.

Операции над множествами

Наиболее важные операции над множествами — объединение, пересечение и разность множеств.

Объединение множеств A и B есть множество A ∪ B, которое состоит из всех элементов, принадлежащих хотя бы одному из множеств A или B. Так, для множеств M и F из рассмотренного выше примера имеем: M ∪ F = {м, а, т, е, и, к, ф, з}. Аналогично определяется объединение трёх и большего числа множеств.

Пересечение множеств A и B есть множество A ∩ B, которое состоит из всех элементов, принадлежащих как множеству A, так и множеству B. Например, для тех же множеств M и F имеем: M ∩ F = {а, и, к}. Множества, у которых нет общих элементов (то есть пересечение которых пусто), называются непересекающимися.

Разность множеств A и B есть множество A \ B, которое состоит из всех элементов множества A, не принадлежащих множеству B. Например, M \ F = {м, т, е}.

Задача. В детский сад завезли карточки для обучения чтению: на некоторых написано «МА», на остальных — «НЯ». Каждый ребёнок взял три карточки и стал составлять из них слова. Оказалось, что слово «МАМА» могут сложить из своих карточек 25 детей, слово «НЯНЯ» — 30 детей, а слово «МАНЯ» — 36 детей. У скольких ребят все три карточки одинаковы?

Решение. Возможны четыре вида наборов из трёх карточек:

МА, МА, МА; пусть a детей имеют такой набор;
МА, МА, НЯ; пусть b детей имеют такой набор;
МА, НЯ, НЯ; пусть c детей имеют такой набор;
НЯ, НЯ, НЯ; пусть d детей имеют такой набор.

Очевидно, что a + b = 25, c + d = 30, b + c = 36. Нас интересует величина a + d. Имеем: a + d = (a + b) + (c + d) − (b + c) = 25 + 30 − 36 = 19.

Итак, три карточки одинаковы у 19 детей.

ЗАДАЧИ

1. Докажите, что для любых трёх множеств A, B и C выполнены равенства:

а) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C); б) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C);

в) (A ∪ B) \ C = (A \ C) ∪ (B \ C); г) A \ (B ∪ C) = (A \ B) ∩ (A \ C).

2. Среди математиков каждый седьмой — философ, а среди философов каждый девятый — математик. Кого больше — философов или математиков?

Философов (в предположении их существования)

3. На маленьком острове 2/3 всех мужчин женаты и 3/5 всех женщин замужем. Сколько жителей острова состоят в браке, если всего там проживает 1900 человек?

1200

4. На данный момент в классе 20 учеников, получивших с начала учебного года хотя бы одну двойку, 17 учеников, получивших не менее двух двоек, 8 учеников, получивших не менее трёх двоек, три ученика, получивших не менее четырёх двоек, один ученик, получивший пять двоек. Больше пяти двоек нет ни у кого. Сколько всего двоек в журнале?

5. Сколько одинаковых членов находится среди первых 2000 членов арифметических прогрессий 9, 11, 13, . . . и 3, 8, 13, . . . ?

400

6. В детский сад завезли карточки трёх видов для обучения чтению: на некоторых написано «па», на некоторых «сть», и на некоторых «ко». Каждый из 40 детей взял три карточки (не обязательно разные) и стал составлять из них слова. Оказалось, что слово «папа» могут сложить из своих карточек 23 ребёнка, слово «пасть» — 19 детей, слово «кость» — 11 детей, слово «пакость» — 4 ребёнка. При этом каждый ребёнок может сложить хотя бы одно слово из перечисленных. Сколько детей взяли себе три карточки со слогами «па», «па», «сть»?

7. Даны 1985 множеств, каждое из которых состоит из 45 элементов, причём объединение любых двух множеств содержит ровно 89 элементов. Сколько элементов содержит объединение всех этих 1985 множеств?

87341

8. Члены Государственной Думы образовали фракции так, что для любых двух фракций A и B (не обязательно различных) A ∪ B — тоже фракция (через C обозначается множество всех членов Думы, не входящих в C). Докажите, что для любых двух фракций A и B A ∪ B — также фракция.