В стране 100 городов некоторые из которых соединены авиалиниями

В стране 100 городов некоторые из которых соединены авиалиниями

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более а) 198 перёлетов; б) 196 перелётов.

Решение

б) Рассмотрим соответствующий граф и выделим из него максимальное дерево (см. задачу 30789 а).
Докажем по индукции, что в дереве с n вершинами (n > 2) существует обходящий все вершины маршрут длины не более 2n – 4. База (n = 3) очевидна.
Шаг индукции. Рассмотрим висячую вершину А (см. задачу 30786) и удалим её и выходящее из неё ребро АВ. По предположению индукции в оставшемся дереве есть обходящий его маршрут длины 2n – 6. Вставив в него кусок ВАВ получим маршрут длины 2n – 4, обходящий исходное дерево.

графы — Задача про города и авиалинии

В стране 100 городов разделенных на 3 республики. Некоторые из городов соединены авиалиниями. Министр связи нашел не менее 70 городов, из каждого из которых выходит не менее 70 авиалиний. Докажтите, что какая-то авиалиния соединяет 2 города одной республики.

задан 6 Янв ’17 0:34

Найдётся республика, в которой как минимум 34 города. Тогда хотя бы один из 70 найденных министром городов в неё попадает. Из него в другие республики уходит не большее 66 авиарейсов. Значит, не менее 4 рейсов будут внутри этой республики.

А как доказать, что найдется республика с 34 городамт?

@maaaaths: если рассуждать строго формально, то это доказывается «от противного». Предположим, что в каждой из республик строго меньше 34 городов. Тогда их в каждой республике не больше 33 ввиду того, что количество городов — целое число. Республик у нас три, и в сумме получается не более 33+33=33=99 городов. А на самом деле их 100. Противоречие.

Если рассуждать проще, то в среднем на республику приходится 100/3 > 33 города. Значит, где-то есть 34 города или больше.

Здравствуйте

Математика — это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

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

Привет! Меня зовут Азат, я создаю курсы по подготовке к экзамену в ШАД. Недавно мы запустили курс по дискретной математике, поэтому наша команда активно прорешивает задачки по соответствующей теме. После разбора экзамена в ШАД 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. Всегда рад ответить!