ГДЗ: Параграф § 17 / Информатика 10 класс

Множество – это совокупность объектов произвольной природы, которые рассматриваются как единое целое. Объекты, входящие в него, называются элементами.

Множество можно задать двумя способами:

• Перечислением всех его элементов, например, \( \{ a, b, c \} \).
• Характеристическим свойством, которое однозначно описывает элементы множества.

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

• Пересечение: Множество общих элементов. Обозначается \( \cap \), например \( X \cap Y \).
• Объединение: Множество всех элементов, принадлежащих хотя бы одному из множеств. Обозначается \( \cup \), например \( X \cup Y \).
• Дополнение: Множество элементов универсального множества, не входящих в данное подмножество. Обозначается чертой над буквой, например \( \bar{P} \).

Мощность множества (\( |X| \)) – это число элементов, содержащихся в конечном множестве \( X \).

Принцип включений-исключений – это формула, используемая для вычисления мощности объединения (или пересечения) множеств. Он позволяет найти число элементов в объединении двух или более множеств, гарантируя, что элементы, принадлежащие пересечениям, не будут посчитаны несколько раз. Для двух множеств формула имеет вид: \( |X \cup Y| = |X| + |Y| - |X \cap Y| \).

Наименьший элемент пересечения \( X \cap Y \):

• Наименьший элемент, входящий в \( X \cap Y \), должен делиться без остатка как на 18, так и на 14. Это наименьшее общее кратное (НОК) чисел 18 и 14.
• Разложим числа на простые множители: \( 18 = 2 \cdot 3^2 \), \( 14 = 2 \cdot 7 \).
• НОК(18, 14) \( = 2 \cdot 3^2 \cdot 7 = 2 \cdot 9 \cdot 7 = 126 \).
• Ответ: Наименьшее число в пересечении – 126.

Наименьший элемент объединения \( X \cup Y \):

• Наименьший элемент, входящий в \( X \cup Y \), должен принадлежать либо \( X \), либо \( Y \).
• Наименьший элемент множества \( X \) – 18.
• Наименьший элемент множества \( Y \) – 14.
• Наименьшее число, входящее в объединение, – это наименьшее из наименьших элементов: \( \min(18, 14) = 14 \).
• Ответ: Наименьшее число в объединении – 14.

• 1) \( \{ 1, 2, 3, 4, 5, 6 \} \): Это все элементы, принадлежащие хотя бы одному из множеств \( A \), \( B \), \( C \). Выражение: \( A \cup B \cup C \).
• 2) \( \{ 2, 5 \} \): Это элементы, принадлежащие пересечению \( A \cap B \), но не принадлежащие \( C \). Выражение: \( (A \cap B) \cap \bar{C} \).
• 3) \( \{ 5 \} \): Это элементы, принадлежащие только пересечению \( A \cap C \), но не \( B \). Выражение: \( (A \cap C) \cap \bar{B} \).
• 4) \( \{ 2, 4, 5, 6 \} \): Это элементы, которые принадлежат \( A \) или \( B \), но не \( C \). Выражение: \( (A \cup B) \cap \bar{C} \).
• 5) \( \{ 1, 2, 3 \} \): Это элементы, принадлежащие только \( A \), но не \( B \) и не \( C \). Выражение: \( A \cap \bar{B} \cap \bar{C} \). (Примечание: на диаграмме это \( A \cap \bar{(B \cup C)} \), т.е. область 1). Выражение: \( A \cap \bar{(B \cup C)} \).
• 6) \( \{ 8 \} \): Это элементы, не принадлежащие ни \( A \), ни \( B \), ни \( C \). Выражение: \( \bar{(A \cup B \cup C)} \).

Обозначим множества:

• \( О \) — отличники: \( |О| = 30 \)
• \( П \) — победители олимпиад: \( |П| = 28 \)
• \( С \) — спортсмены: \( |С| = 42 \)

Данные о пересечениях:

• Отличники и спортсмены (\( О \cap С \)): \( |О \cap С| = 10 \)
• Отличники и победители олимпиад (\( О \cap П \)): \( |О \cap П| = 5 \)
• Спортсмены и победители олимпиад (\( С \cap П \)): \( |С \cap П| = 8 \)
• Отличники, спортсмены и победители олимпиад (\( О \cap С \cap П \)): \( |О \cap С \cap П| = 3 \)

Общее количество отдохнувших равно мощности объединения \( |О \cup П \cup С| \). Используем формулу включений-исключений для трех множеств:

\( |О \cup П \cup С| = |О| + |П| + |С| - |О \cap С| - |О \cap П| - |С \cap П| + |О \cap С \cap П| \)

Подставим значения:

\( |О \cup П \cup С| = 30 + 28 + 42 - 10 - 5 - 8 + 3 \)

\( |О \cup П \cup С| = 100 - 23 + 3 = 80 \)

Ответ: В лагере отдохнуло 80 ребят.

Обозначим множества:

• Общее число учеников в классе: 38
• Число учеников, записавшихся на экзамены: 35. Следовательно, 38 - 35 = 3 ученика не выбрали ни одного предмета.
• \( И \) — информатика: \( |И| = 21 \)
• \( Ф \) — физика: \( |Ф| = 19 \)
• \( О \) — обществознание: \( |О| = 26 \)

Данные о пересечениях:

• \( |И \cap О| = 3 \) (трое избравших информатику выбрали еще и обществознание)
• \( |Ф \cap О| = 6 \) (шестеро выбрали физику и обществознание)
• \( |И \cap Ф \cap О| = 1 \) (один выбрал все три предмета)
• Объединение всех трех множеств должно равняться числу записавшихся: \( |И \cup Ф \cup О| = 35 \)

Используем формулу включений-исключений для трех множеств, чтобы найти недостающее пересечение \( |И \cap Ф| \):

\( |И \cup Ф \cup О| = |И| + |Ф| + |О| - |И \cap О| - |Ф \cap О| - |И \cap Ф| + |И \cap Ф \cap О| \)

Подставим известные значения:

\( 35 = 21 + 19 + 26 - 3 - 6 - |И \cap Ф| + 1 \)

\( 35 = 67 - 9 - |И \cap Ф| + 1 \)

\( 35 = 59 - |И \cap Ф| \)

Отсюда находим \( |И \cap Ф| \):

\( |И \cap Ф| = 59 - 35 = 24 \)

Проверим последнюю фразу условия: 'Пятнадцать учеников из выбравших по два предмета указали в анкете два предмета.'
Общее число выбравших ровно два предмета: \( (|И \cap О| - |И \cap Ф \cap О|) + (|Ф \cap О| - |И \cap Ф \cap О|) + (|И \cap Ф| - |И \cap Ф \cap О|) \).
\( (3 - 1) + (6 - 1) + (24 - 1) = 2 + 5 + 23 = 30 \).
Общее число учеников, выбравших ровно два предмета, равно 30. Условие, что 15 учеников указали в анкете два предмета, может быть интерпретировано как дополнительная или избыточная информация, которая не влияет на основной расчет по формуле включений-исключений.

Внимание! В условии задачи допущена ошибка. Если \( |И \cap Ф| = 24 \), то \( |И \cup Ф \cup О| = 35 \) выполняется. Однако, это число больше, чем \( |И|=21 \) и \( |Ф|=19 \), что невозможно для пересечения \( |И \cap Ф| \).
Вернемся к тексту: 'Информатику выбрал 21 ученик, причем трое из них выбрали еще и обществознание, а шестеро — еще и физику. Один ученик выбрал все три предмета.' – Это означает, что:

• \( |И| = 21 \)
• \( |И \cap О| = 3 \).
• \( |И \cap Ф| = 6 \).
• \( |И \cap Ф \cap О| = 1 \).

В этом случае пересчитаем, используя \( |И \cap Ф| = 6 \):

\( 35 = 21 + 19 + 26 - 3 - 6 - |Ф \cap О| - 6 + 1 \)

\( 35 = 67 - 9 - 6 - |Ф \cap О| + 1 \)

\( 35 = 53 - |Ф \cap О| \).

\( |Ф \cap О| = 53 - 35 = 18 \).

Это противоречит условию 'шестеро выбрали физику и обществознание' (\( |Ф \cap О| = 6 \)).
В тексте сказано: 'а шестеро – еще и физику' — это может означать, что \( 6 \) учеников выбрали только информатику и физику, но не обществознание, или что \( |И \cap Ф| = 6 \).

Примем интерпретацию, что: \( |И \cap О| = 3 \), \( |Ф \cap О| = 6 \), \( |И \cap Ф \cap О| = 1 \). Нам нужно найти сколько учеников выбрали физику – это уже дано в условии: \( |Ф| = 19 \).

Вероятно, вопрос 'Надо определить, сколько учеников выбрали физику.' является ошибочным и должен быть 'Надо определить, сколько учеников выбрали только физику.'.
Число выбравших только физику (Ф):
\( \text{Только } |Ф| = |Ф| - (|И \cap Ф| - |И \cap Ф \cap О|) - (|Ф \cap О| - |И \cap Ф \cap О|) - |И \cap Ф \cap О| \)

Используем формулу, исходя из условия, что \( |Ф|=19 \), \( |И \cap Ф| \) найдено, \( |Ф \cap О| \) дано, \( |И \cap Ф \cap О| \) дано. Предположим, что \( |И \cap Ф| \) не дано, а нам нужно его найти. Тогда решение №1 верно, и \( |И \cap Ф| = 24 \). Но это противоречит \( |И|=21 \) и \( |Ф|=19 \).
Примем, что в задаче опечатка, и число выбравших физику дано: 19.

Ответ: Физику выбрали 19 учеников.

Обозначим множества:

• \( U \) — общее число человек: \( |U| = 100 \)
• \( А \) — английский: \( |А| = 85 \)
• \( И \) — испанский: \( |И| = 80 \)
• \( Н \) — немецкий: \( |Н| = 75 \)

Требуется найти минимальное возможное значение \( |А \cap И \cap Н| \). Минимальное пересечение достигается, когда объединение \( |А \cup И \cup Н| \) максимально. Но поскольку \( A, И, Н \subset U \), максимальное объединение не может превышать \( |U| = 100 \). Таким образом, мы примем \( |А \cup И \cup Н| = 100 \).

Формула включений-исключений:

\( |А \cup И \cup Н| = |А| + |И| + |Н| - (|А \cap И| + |А \cap Н| + |И \cap Н|) + |А \cap И \cap Н| \)

Перенесем слагаемые, чтобы выразить \( |А \cap И \cap Н| \):

\( |А \cap И \cap Н| = |А \cup И \cup Н| - (|А| + |И| + |Н|) + (|А \cap И| + |А \cap Н| + |И \cap Н|) \)

Для минимизации \( |А \cap И \cap Н| \) нужно минимизировать \( |А \cup И \cup Н| \) (что мы сделали, приняв \( 100 \)) и минимизировать \( (|А \cap И| + |А \cap Н| + |И \cap Н|) \).
Это некорректно. Для минимизации \( |А \cap И \cap Н| \) нужно максимизировать сумму попарных пересечений \( \sum |X \cap Y| \).

Альтернативный подход (принцип Дирихле):
Число людей, не знающих какой-либо язык, не может быть отрицательным. Если бы 1 человек не знал английский, 0 — испанский, 0 — немецкий, то 100 - (85+80+75) = -140. Это неверно.

Число людей, не знающих английский: \( |\bar{A}| = 100 - 85 = 15 \)

Число людей, не знающих испанский: \( |\bar{И}| = 100 - 80 = 20 \)

Число людей, не знающих немецкий: \( |\bar{Н}| = 100 - 75 = 25 \)

Число людей, которые не знают хотя бы один язык: \( |\bar{A} \cup \bar{И} \cup \bar{Н}| \). Максимальное число людей, которые не знают хотя бы один язык: \( |\bar{A}| + |\bar{И}| + |\bar{Н}| = 15 + 20 + 25 = 60 \).

Люди, знающие все три языка, составляют множество \( А \cap И \cap Н \). Это дополнение к множеству людей, которые не знают хотя бы один язык: \( |А \cap И \cap Н| = |U| - |\bar{A} \cup \bar{И} \cup \bar{Н}| \).

Минимальное число знающих все три языка будет, когда максимально число не знающих хотя бы один язык, то есть \( |\bar{A} \cup \bar{И} \cup \bar{Н}| \). Максимальное значение \( |\bar{A} \cup \bar{И} \cup \bar{Н}| \) не может превышать сумму мощностей: \( 15 + 20 + 25 = 60 \).

Минимально возможное число знающих все три языка:

\( |А \cap И \cap Н|_{\min} = |U| - |\bar{A} \cup \bar{И} \cup \bar{Н}|_{\max} \)

\( |А \cap И \cap Н|_{\min} = 100 - 60 = 40 \)

Ответ: Минимум 40 человек заведомо знают все три языка.