НОВОСТИ Дискретная математика на экзамене в ШАД

[BDFINFO2.0]

Введение



Привет!
Я создаю курсы по подготовке к экзамену в ШАД. Недавно мы запустили курс по дискретной математике, поэтому наша команда активно прорешивает задачки по соответствующей теме.
После разбора экзамена в

You must be registered for see links

, мы увидели большой интерес пользователей хабра на занимательные задачки из экзамена. Поэтому выкладываем здесь 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»