Примеры решений

Примеры решений

Тема: множества. Задача. Докажите, что множество $A$ тогда и только тогда является подмножеством множества $B$, когда каждый элемент, не принадлежащий $B$, не принадлежит $A$. Решение. Оборот "тогда и только тогда" означает два утверждения: 1) $(A \subset B) \Rightarrow {}$(для любого $x$, не принадлежащего $B$, $x$ не принадлежит $A$), 2) (для любого $x$, не принадлежащего $B$, $x$ не принадлежит $A$)${} \Rightarrow (A \subset B)$. Продемонстрируем на примере этой задачи, как применяется метод доказательства "от противного". Чтобы доказать некоторое утверждение, мы предполагаем, что оно не выполняется и приходим к противоречию Докажем здесь только утверждение 1). Предположим противное, то есть что $A \subset B$, но существует некоторый элемент $x$, не принадлежащий $B$, но принадлежащий $A$. По определению того, что $A \subset B$ мы знаем, что каждый элемент, принадлежащий $A$, должен принадлежать $B$. В частности, $x \in B$. Возникает противоречие. Значит, наше предположение было неверно, и нет элементов принадлежащих $A$, но не принадлежащих $B$. Комментарий. Заметим, что эта внешне несложная задача является одновременно очень важной и достаточно сложной. Как и в некоторых других задачах листка "Множества", зачастую не совсем понятно, что, собственно, надо доказывать. Мы одновременно демонстрируем метод от противного, учимся писать отрицание к следствию и разбираемся, что значит "тогда и только тогда".


Тема: множества. Задача. Может ли у множества быть ровно: 1) 0; 2) 7; 3) 16 подмножеств? Решение. Во-первых, заметим, что число подмножеств пустого множества равно 1, число подмножеств множества, состоящего из одного элемента, равно 2, из двух – 4, из трех – 8, из четырех – 16. Второе важное наблюдение – монотонность: если у одного множества больше элементов, чем у другого, то и подмножеств у него больше. Теперь легко решить нашу задачу: 1) Нет. У любого множества больше чем 0 подмножеств, потому что пустое множество $\varnothing$ является подмножеством любого множества. 2) Нет. У множеств из 0, 1 и 2 элементов подмножеств меньше чем 7. У множества из 3 элементов подмножеств уже 8. У всех остальных множеств больше чем 3 элемента, а значит подмножеств у них тоже больше чем 8. Таким образом ни у какого множества не может быть 7 подмножеств. 3) Да. У любого множества из 4 элементов ровно 16 подмножеств.


Тема: отображения. Задача. Пусть задано отображение $f\colon X\rightarrow Y$, и подмножества $A_1, A_2\subset X$, $B_1, B_2\subset Y$. Всегда ли верно, что 1) $f[X]=Y$ 2) $f^{-1}[B_1\cup B_2] = f^{-1}[B_1]\cup f^{-1}[B_2]$. Решение. 1) Нет. Например, если $X=Y=\{1,2\}$, f(1)=1, f(2)=1, то $f[X]=\{1\}$, что не равно $Y$. 2) Верно. Докажем сначала, что $f^{-1}[B_1\cup B_2]\subset f^{-1}(B_1)\cup f^{-1}(B_2)$. Действительно, для любого $x\in f^{-1}[B_1\cup B_2]$ верно, что $f(x)\in B_1$ или $f(x)\in B_2$, то есть $x\in f^{-1}[B_1]$ или $x\in f^{-1}[B_2]$. Теперь докажем, что $f^{-1}(B_1)\cup f^{-1}(B_2)\subset f^{-1}[B_1\cup B_2]$. Действительно, для любого $x\in f^{-1}(B_1)\cup f^{-1}(B_2)$ верно, что $f(x)\in B_1$ или $f(x)\in B_2$, то есть $f(x)\in B_1\cup B_2$, что и означает, что $x\in f^{-1}[B_1\cup B_2]$.


Тема: Комбинаторика. Задача. Сколько существует "cлов" из двух букв английского языка? Комментарий. Во-первых, в этой задаче, конечно, имеются в виду не те слова, которые можно встретить в словаре, а произвольные сочетания букв английского языка. Теперь перейдем к главным идеям решений подобных комбинаторных задач. Когда требуется посчитать кол-во каких-то специальных объектов, часто работает следующая схема: 1. перечисление всех вариантов в разумном порядке; 2. понимание того, какие "записи" соответствуют одному и тому же объекту. В этой задаче нам понадобится только 1. Второй пункт будет проиллюстрирован в следующем примере. Другая полезная (отнюдь не только в комбинаторике) идея состоит в том, что, прежде чем решать задачу для произвольного (или очень большого) $n$, полезно сначала разобраться со случаем небольших $n$. Замеченные при этом закономерности (даже если они не доказаны) часто существенно упрощают решение задачи. Решение. Попробуем для начала решить ту же задачу, но с алфавитом, состоящим всего из трех букв – а, b, c. Здесь мы можем явно выписать все слова, состоящие из двух букв: аа, аb, аc, bа, bb, bc, cа, cb, cc. Получили $9=3\cdot3$. В общем случае подсчет числа таких слов будем вести следующим образом: сначала посчитаем число слов, которые начинаются с буквы "а", затем – число слов, начинающихся с буквы "b" и так далее. Совершенно очевидно, что таким образом мы посчитаем каждое "слово" по разу. Заметим, что двухбуквенных слов, начинающихся на букву "а", будет ровно столько же, сколько есть букв в алфавите. Слов, начинающихся на букву "б", будет столько же. И так со всеми буквами. В нашей задаче слов, начинающихся с буквы "а", будет 26. Столько же будет слов, начинающихся с буквы "b", и так далее. Значит, всего слов, состоящих из двух букв, будет $26\cdot 26=676$. Комментарий. На самом деле тут речь идет о прямом (или декартовом) произведении множеств. Произведением множеств называют множество из упорядоченных пар. Число элементов в произведении множеств равно произведению числа элементов исходных множеств (правило умножения). В нашем случае множество всех слов из 2 букв на английском языке – это как раз множество неупорядоченных пар английских букв, а значит равно произведению множества букв английского алфавита (их 26 штук) с самим собой, а значит в нем 26*26=676 элементов.


Тема: комбинатрика. Задача. Сколькими способами можно выбрать из десяти человек двух дежурных и одного старшего дежурного? Решение. Полезным упражнением является честное выписывание троек дежурных, выбираемых из, скажем, четырех человек (Вася, Коля, Леша, Петя). При этом первым будем писать старшего дежурного, а остальных дежурных записывать в алфавитном порядке. Удобно при этом сначала выбирать старшим дежурным первого по алфавиту, потом второго по алфавиту и т.д. Так как порядок "обычных" дежурных не важен, выписывая их по алфавиту, мы никакой случай не забудем и не повторим дважды. (Вася, Коля, Леша), (Вася, Коля, Петя),& (Вася, Леша, Петя), (Коля, Вася, Леша), (Коля, Вася, Петя),& (Коля, Леша, Петя), (Леша, Вася, Коля), (Леша, Вася, Петя),& (Леша, Коля, Петя), (Петя, Вася, Коля), (Петя, Вася, Леша),& (Петя, Коля, Леша). Итого $12$ вариантов. Теперь перейдем к решению исходной задачи. Старшего дежурного можно выбрать десятью способами. Когда мы уже выбрали старшего, мы можем выбрать первого дежурного девятью (потому что одного человека мы уже назначили старшим дежурным) способами. После того, как мы выбрали старшего дежурного и еще одного дежурного, второго дежурного мы можем выбрать восемью способами. Итого, вроде бы, по "правилу умножения" должно получаться $10\cdot9\cdot8=720$. Однако если мы внимательно посмотрим на наше решение, то увидим, что каждую тройку дежурных мы посчитали по два раза. Например, тройку дежурных (Вася – старший дежурный, Леша, Петя) мы посчитали два раза: как тройку (Вася, Петя, Леша) и как тройку (Вася, Леша, Петя). Поэтому правильный ответ в два раза меньше – 360.