Привет! Меня зовут Азат, я создаю курсы по подготовке к экзамену в ШАД. Недавно мы запустили курс по дискретной математике, поэтому наша команда активно прорешивает задачки по соответствующей теме. После разбора экзамена в ШАД 2019 года мы увидели большой интерес пользователей Хабра к занимательным задачкам из экзамена. Поэтому выкладываем здесь 4 избранных по дискретной математике. Наслаждайтесь!
Задача 1 (26 мая 2018, №5)
Случайная величина 
равна длине цикла, содержащего одновременно элементы 1 и 2, при случайной перестановке множества 
. Если такого цикла нет, то 
. Найдите распределение случайной величины и ее математическое ожидание.
По сути, задача больше на комбинаторику, чем на теорвер. По определению, распределение — это значения 
для всех возможных 
. Каждое из таких значений — это отношение количества перестановок, в которых есть требуемый цикл длины , к количеству всех перестановок, что равно 
Займемся подсчетом перестановок. Сначала нужно выбрать элементы для цикла. Два из них мы уже знаем (1 и 2), осталось выбрать 
из оставшихся 
, можно сделать 
способами. Элементы, не вошедшие в цикл, можно расставить как угодно, это можно сделать 
способами. Наконец, нужно расставить выбранные элементы в цикл. Единицу можно сопоставить любому числу, кроме её самой же, иначе цикл тут же оборвется. Пусть 
— наш цикл и 
, тогда на позицию 
можно поставить любой элемент, кроме 1 и 
(по аналогичным причинам). Продолжая расставлять элементы, получаем, что всего существует 
способов сделать цикл. Итог:
Заметим, что наши рассуждения не работали при 
и 
. При , однако, мы все равно получили верный ответ (
, т.к. если цикл и существует, его длина не меньше двух). Также очевидно, что если 
, то 
(цикл не может быть длиннее самой перестановки). Значит, 
можно посчитать как дополнение к полученным результатам:
Как только мы нашли распределение , мы можем посчитать ее матожидание:
Задача 2 (4 июня 2016, №3)
Случайные величины и 
принимают по два значения и 
. Доказать, что они независимы.
Эта задача, в противовес предыдущей, уже действительно на теорвер, хоть и дискретный.
Сначала рассмотрим частный случай: пусть обе величины принимают значения 0 и 1, при этом 
, 
, а 
. Покажем, что 
. Действительно, 
, 
, 
. Но по условию 
, откуда 
и .
Заметим, что этого достаточно для независимости и : действительно, все остальные вероятности можно выразить через введенные (для самих величин это очевидно, для их комбинации: 
, 
, 
). Можно проверить, что условие независимости верно для любой из четырех комбинаций, соответственно частный случай можно считать доказанным.
Пусть в общем случае 
, где 
и 
. Введем новые случайные величины 
и 
. Заметим, что принимает значения и тогда и только тогда, когда 
равна 0 и 1 соответственно, аналогично для . Если мы докажем, что 
, то по вышедоказанному исходные величины также будут независимы.
Но по условию , откуда и требуемые величины независимы, ч.т.д.
Задача 3 (26 мая 2018, №8)
В волшебной стране Ляляндии 100 городов, некоторые из которых соединены авиалиниями. Известно, что из каждого города выходит более 90 авиалиний. Докажите, что найдется 11 городов, попарно соединенных авиалиниями друг с другом.
Построим граф, где вершины — это города, а ребра — авиалинии. Рассмотрим произвольную вершину, она соединена с хотя бы 91 вершиной, и потому из нее может отсутствовать не более 8 ребер. Уберем из графа все вершины, не соединенные с выбранной, и ее саму, после чего выберем другую вершину в оставшемся графе и повторим процесс.
Выбранные вершины образуют полный граф (то есть граф, в которым каждая пара вершин соединена ребром). Действительно, на первом шаге мы оставили только те вершины, которые связаны с первой выбранной, на втором удалили все, что не связаны со второй и т.д., в итоге на каждом шаге новая выбранная вершина будет связана со всеми предыдущими. Оценим размер этого подграфа. Каждая итерация процесса увеличивает его на 1 и выкидывает не более 9 вершин, следовательно, полученный подграф будет иметь размер хотя бы 
городов, что и требовалось.
Задача 4 (3 июня 2017, №4)
В компании «Тындекс» у каждого сотрудника не менее 50 знакомых. Оказалось, что есть два сотрудника, знакомые друг с другом лишь через 9 рукопожатий (то есть кратчайшая соединяющая их цепочка из попарно знакомых людей содержит 8 промежуточных людей). Докажите, что в этой компании хотя бы 200 сотрудников.
Выпишем описанную цепочку, в ней будет 10 человек. Обозначим за 
множество знакомых для 
-го сотрудника из цепочки, тогда 
.
Заметим, что множества 
не могут пересекаться. Действительно, в противном случае мы можем взять элемент из пересечения и через него сократить число рукопожатий между первым и последним сотрудником. Но тогда общее количество сотрудников не меньше, чем 
, ч.т.д.
Если у вас есть другие идеи решения задач или какие-то замечания, смело пишите мне в телеграм @Azatik1000. Всегда рад ответить!
Азат Калмыков, куратор в «ШАД Helper»