МАЛЫЙ МЕХМАТ МГУ

В стране 2003 города. Из столицы выходит 203 дороги, из города Тьмутараканьска 3 дороги, а из всех остальных городов — по 20 дорог. Докажите, что из столицы можно попасть в Тьмутараканьск.
 

В некоторой стране столица соединена дорогами со 100 городами, а каждый город, кроме столицы, соединен дорогами ровно с 10 городами. Известно, что из любого города можно попасть в любой другой. Докажите, что можно закрыть половину дорог, ведущих из столицы, так, что возможность попасть из любого города в любой сохранится.
 

Между 40 городами существует 742 двусторонние авиалинии (любая авиалиния соединяет два города, никакие два города не соединены более, чем одной авиалинией). Докажите, что из любого города можно долететь до любого другого.
 

а) В областной думе 100 депутатов. За год работы каждый из них подрался не менее, чем с 51 коллегой. Докажите, что можно выбрать трех депутатов, из которых любые два уже подрались.
б) Ещё через год оказалось, что кадый депутат подрался не менее, чем с 67 коллегами. Докажите, что можно выбрать четырёх депутатов, из которых любые два уже подрались.
в) А ещё через год каждый депутат подрался не менее, чем с 76 коллегами. Докажите, что можно выбрать пять депутатов, из которых любые два уже подрались.
 

Пусть в думе всего N депутатов, причём каждый подрался более, чем с (k – 2)N/(k – 1) коллегами (k > 1). Докажите, что тогда найдутся k депутатов, любые два из которых уже подрались.
 

а) Докажите, что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых.
б) Среди 17 человек любые два либо дружат, либо враждуют, либо незнакомы. Докажите, что среди них найдутся либо трое друзей, либо трое врагов, либо трое незнакомых.
в) Пусть a₁ = 2, a_n = a_{n – 1} + 1 для n > 2. Рёбра полного графа из a_n + 1 вершин раскрашены в n цветов. Докажите, что в этом графе есть одноцветный треугольник.
 

Докажите, что среди любых 10 человек есть либо трое попарно знакомых, либо четверо попарно незнакомых.
 

Докажите, что среди любых 9 человек есть либо трое попарно знакомых, либо четверо попарно незнакомых.