Привет! Меня зовут Азат, я создаю курсы по подготовке к экзамену SAD. Недавно мы запустили курс по дискретной математике, поэтому наша команда активно решает задачи по актуальной теме.
После анализ ЕГ? в ШАД 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)
В Tyndex у каждого сотрудника не менее 50 знакомых.Оказалось, что есть два сотрудника, которые знают друг друга только через 9 рукопожатий (то есть кратчайшая цепочка парных знакомств, соединяющая их, содержит 8 промежуточных людей).
Докажите, что в этой компании работает не менее 200 сотрудников.
Решение Распишем описанную цепочку, в ней будет 10 человек.
Обозначим через 
много знакомых для 
-ый сотрудник из сети, то 
.
Обратите внимание, что множества 
не могут пересекаться.
Ведь иначе мы можем взять элемент из пересечения и через него уменьшить количество рукопожатий между первым и последним сотрудником.
Но тогда общая численность работающих будет не менее 
, и т. д. Если у вас есть другие идеи решения задач или какие-либо комментарии, смело пишите мне в телеграмм @Azatik1000. Всегда рад ответить! Азат Калмыков, куратор SHAD Helper
Теги: #математика #школа анализа данных #Занимательные задачи #дискретная математика
-
Что Такое Защита Паролем Usb?
19 Oct, 24 -
Как Появился Android-Планшет
19 Oct, 24 -
Теплый Ламповый Звук
19 Oct, 24 -
Получите Максимум От Sil
19 Oct, 24 -
Какие Типы Дисплеев Есть В Ноутбуках? Анализ
19 Oct, 24 -
Анонс Новых Инженерных Тренингов
19 Oct, 24 -
Хабрафильтр
19 Oct, 24
