Открыть список
Как стать автором
Обновить

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

Занимательные задачкиМатематика

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



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


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


Решение

По сути, задача больше на комбинаторику, чем на теорвер. По определению, распределение $X$ — это значения $P(X = k)$ для всех возможных $k$. Каждое из таких значений — это отношение количества перестановок, в которых есть требуемый цикл длины $k$, к количеству всех перестановок, что равно $n!$


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


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


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


$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}$


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


$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)


Случайные величины $X$ и $Y$ принимают по два значения и $cov(X, Y) = 0$. Доказать, что они независимы.


Решение

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


Сначала рассмотрим частный случай: пусть обе величины принимают значения 0 и 1, при этом $P(X = 1) = p$, $P(Y = 1) = q$, а $P(X = 1, Y = 1) = r$. Покажем, что $r = pq$. Действительно, $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$, $E(XY) = P(X = 1, Y = 1) = r$. Но по условию $cov(X, Y) = E(XY) - E(X)E(Y) = 0$, откуда $E(XY) = E(X)E(Y)$ и $r = pq$.


Заметим, что этого достаточно для независимости $X$ и $Y$: действительно, все остальные вероятности можно выразить через введенные (для самих величин это очевидно, для их комбинации: $P(X = 1, Y = 0) = P(X = 1) - P(X = 1, Y = 1) = p - r$, $P(X = 0, Y = 1) = P(Y = 1) - P(X = 1, Y = 1) = q - r$, $P(X = 0, Y = 0) = 1 - P(X = 1, Y = 1) - P(X = 0, Y = 1) - P(X = 1, Y = 0)$). Можно проверить, что условие независимости верно для любой из четырех комбинаций, соответственно частный случай можно считать доказанным.


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


$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)}$


Но по условию $cov(X, Y) = 0$, откуда $cov(X', Y') = 0$ и требуемые величины независимы, ч.т.д.


Задача 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 человек. Обозначим за $A_i$ множество знакомых для $i$-го сотрудника из цепочки, тогда $\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»

Теги:математикадискретная математикашкола анализа данных
Хабы: Занимательные задачки Математика
Всего голосов 11: ↑10 и ↓1 +9
Просмотры4.3K

Комментарии 0

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Похожие публикации

Математик-программист, Склад
от 180 000 до 270 000 ₽OZONМосква
Разработчик Ruby on Rails
до 300 000 ₽ВГТМожно удаленно
Аналитик по математическому моделированию
от 80 000 ₽ООО "2050-Интегратор"Санкт-ПетербургМожно удаленно
Ведущий Python-разработчик
от 150 000 до 200 000 ₽Российский квантовый центрМожно удаленно
PHP разработчик / Backend
от 75 000 ₽UBS TechnologiesНижний Новгород

Лучшие публикации за сутки