Привет! Меня зовут Азат, я создаю курсы по подготовке к экзамену в ШАД. Недавно мы запустили курс по дискретной математике, поэтому наша команда активно прорешивает задачки по соответствующей теме. После разбора экзамена в ШАД 2019 года мы увидели большой интерес пользователей Хабра к занимательным задачкам из экзамена. Поэтому выкладываем здесь 4 избранных по дискретной математике. Наслаждайтесь!

Задача 1 (26 мая 2018, №5)

Случайная величина $inline$ равна длине цикла, содержащего одновременно элементы 1 и 2, при случайной перестановке множества $\{1, 2, \ldots, n\}$ . Если такого цикла нет, то $inline$ . Найдите распределение случайной величины $inline$ и ее математическое ожидание.

Решение

По сути, задача больше на комбинаторику, чем на теорвер. По определению, распределение $inline$ — это значения $inline$ для всех возможных $inline$ . Каждое из таких значений — это отношение количества перестановок, в которых есть требуемый цикл длины $inline$ , к количеству всех перестановок, что равно $inline$

Займемся подсчетом перестановок. Сначала нужно выбрать элементы для цикла. Два из них мы уже знаем (1 и 2), осталось выбрать $inline$ из оставшихся $inline$ , можно сделать $C_{n - 2}^{k - 2}$ способами. Элементы, не вошедшие в цикл, можно расставить как угодно, это можно сделать $inline$ способами. Наконец, нужно расставить выбранные элементы в цикл. Единицу можно сопоставить любому числу, кроме её самой же, иначе цикл тут же оборвется. Пусть $inline$ — наш цикл и $inline$ , тогда на позицию $inline$ можно поставить любой элемент, кроме 1 и $inline$ (по аналогичным причинам). Продолжая расставлять элементы, получаем, что всего существует $inline$ способов сделать цикл. Итог:

$P(X = k) = \frac{C_{n - 2}^{k - 2} \cdot (n - k)! \cdot (k - 1)!}{n!} = \frac{k - 1}{n(n - 1)}$

Заметим, что наши рассуждения не работали при $inline$ и $inline$ . При $inline$ , однако, мы все равно получили верный ответ ( $inline$ , т.к. если цикл и существует, его длина не меньше двух). Также очевидно, что если $inline$ , то $inline$ (цикл не может быть длиннее самой перестановки). Значит, $inline$ можно посчитать как дополнение к полученным результатам:

$P(X = 0) = 1 - \sum_{k = 1}^n \frac{k - 1}{n(n - 1)} = 1 - \frac{1}{n(n - 1)} \cdot \frac{n(n - 1)}{2} = 1 - \frac{1}{2} = \frac{1}{2}$

Как только мы нашли распределение $inline$ , мы можем посчитать ее матожидание:

$E(X) = \sum_{k = 1}^n k \cdot \frac{k - 1}{n(n - 1)} = \frac{1}{n(n - 1)} \left( \sum_{k = 1}^n k^2 - \sum_{k = 1}^n k \right) =$

$= \frac{1}{n(n - 1)} \cdot \left( \frac{1}{6}n(n + 1)(2n + 1) - \frac{1}{2}n(n + 1) \right) = \frac{n + 1}{3}$

Задача 2 (4 июня 2016, №3)

Случайные величины $inline$ и $inline$ принимают по два значения и $inline$ . Доказать, что они независимы.

Решение

Эта задача, в противовес предыдущей, уже действительно на теорвер, хоть и дискретный.

Сначала рассмотрим частный случай: пусть обе величины принимают значения 0 и 1, при этом $inline$ , $inline$ , а $inline$ . Покажем, что $inline$ . Действительно, $E(X) = P(X = 0) \cdot 0 + P(X = 1) \cdot 1 = P(X = 1) = p$ , $E(Y) = P(Y = 0) \cdot 0 + P(Y = 1) \cdot 1 = P(Y = 1) = q$ , $inline$ . Но по условию $inline$ , откуда $inline$ и $inline$ .

Заметим, что этого достаточно для независимости $inline$ и $inline$ : действительно, все остальные вероятности можно выразить через введенные (для самих величин это очевидно, для их комбинации: $inline$ , $inline$ , $inline$ ). Можно проверить, что условие независимости верно для любой из четырех комбинаций, соответственно частный случай можно считать доказанным.

Пусть в общем случае $P(X = a) = p, \ P(X = b) = 1 - p, \ P(Y = c) = q, \ P(Y = d) = 1 - q$ , где $inline$ и $inline$ . Введем новые случайные величины $X' = \dfrac{X - a}{b - a}$ и $Y' = \dfrac{Y - c}{d - c}$ . Заметим, что $inline$ принимает значения $inline$ и $inline$ тогда и только тогда, когда $inline$ равна 0 и 1 соответственно, аналогично для $inline$ . Если мы докажем, что $inline$ , то по вышедоказанному исходные величины также будут независимы.

$E(X') = \frac{E(X) - a}{b - a} \ \ \ E(Y') = \frac{E(Y) - c}{d - c}$

$E(X'Y') = E\left( \frac{X - a}{b - a} \cdot \frac{Y - c}{d - c} \right) = \frac{E(XY) - cE(X) - aE(Y) + ac}{(b - a)(d - c)}$

$cov(X', Y') = E(X'Y') - E(X')E(Y') = \frac{E(XY) - E(X)E(Y)}{(b - a)(d - c)} = \frac{cov(X, Y)}{(b - a)(d - c)}$

Но по условию $inline$ , откуда $inline$ и требуемые величины независимы, ч.т.д.

Задача 3 (26 мая 2018, №8)

В волшебной стране Ляляндии 100 городов, некоторые из которых соединены авиалиниями. Известно, что из каждого города выходит более 90 авиалиний. Докажите, что найдется 11 городов, попарно соединенных авиалиниями друг с другом.

Решение

Построим граф, где вершины — это города, а ребра — авиалинии. Рассмотрим произвольную вершину, она соединена с хотя бы 91 вершиной, и потому из нее может отсутствовать не более 8 ребер. Уберем из графа все вершины, не соединенные с выбранной, и ее саму, после чего выберем другую вершину в оставшемся графе и повторим процесс.

Выбранные вершины образуют полный граф (то есть граф, в которым каждая пара вершин соединена ребром). Действительно, на первом шаге мы оставили только те вершины, которые связаны с первой выбранной, на втором удалили все, что не связаны со второй и т.д., в итоге на каждом шаге новая выбранная вершина будет связана со всеми предыдущими. Оценим размер этого подграфа. Каждая итерация процесса увеличивает его на 1 и выкидывает не более 9 вершин, следовательно, полученный подграф будет иметь размер хотя бы $\lfloor \frac{100}{9} \rfloor = 11$ городов, что и требовалось.

Задача 4 (3 июня 2017, №4)

В компании «Тындекс» у каждого сотрудника не менее 50 знакомых. Оказалось, что есть два сотрудника, знакомые друг с другом лишь через 9 рукопожатий (то есть кратчайшая соединяющая их цепочка из попарно знакомых людей содержит 8 промежуточных людей). Докажите, что в этой компании хотя бы 200 сотрудников.

Решение

Выпишем описанную цепочку, в ней будет 10 человек. Обозначим за $inline$ множество знакомых для $inline$ -го сотрудника из цепочки, тогда $\forall i \ |A_i| \geq 50$ .

Заметим, что множества $A_1, \ A_4, \ A_7, \ A_{10}$ не могут пересекаться. Действительно, в противном случае мы можем взять элемент из пересечения и через него сократить число рукопожатий между первым и последним сотрудником. Но тогда общее количество сотрудников не меньше, чем $|A_1 \cup A_4 \cup A_7 \cup A_{10}| = |A_1| + |A_4| + |A_7| + |A_{10}| \geq 200$ , ч.т.д.

Если у вас есть другие идеи решения задач или какие-то замечания, смело пишите мне в телеграм @Azatik1000. Всегда рад ответить!

Азат Калмыков, куратор в «ШАД Helper»

Дискретная математика на экзамене в ШАД