Д. Карпов


Задача №1.  В стране Графинии $n$ $( n \geq 2)$ городов. Некоторые города соединены беспосадочными авиалиниями (по каждой авиалинии выполняются рейсы в обоих направлениях) таким образом, что из любого города можно самолётами (возможно, с пересадками) добраться до любого другого, но закрытие любой авиалинии нарушает это свойство. При этом из любого города выходит не больше $d$ авиалиний. Докажите, что все города Графинии можно разбить не более чем на $\frac{n}{2} + d$ групп таким образом, чтобы каждая авиалиния соединяла города из разных групп и для любых двух групп существовало не более одной авиалинии, соединяющей города из этих групп. ( Д. Карпов )
комментарий/решение(1) олимпиада
Задача №2.  В стране Эйлерии 101 город. Каждые два города соединены двусторонним беспосадочным рейсом одной из 99 авиакомпаний. Известно, что из каждого города выходят рейсы всех 99 компаний. Назовём $\textit{треугольником}$ три города, попарно соединённых рейсами одной и той же компании. Докажите, что в Эйлерии не больше одного треугольника. ( И. Богданов, Д. Карпов )
комментарий/решение(1) олимпиада
Задача №3.  В городе N. существует множество оппозиционных обществ, каждое из которых состоит из 10 членов. Известно, что для любых 2004 обществ найдется человек, состоящий хотя бы в 11 из них. Докажите, что правительство может арестовать 2003 человека так, чтобы в каждом обществе хотя бы один член был арестован. ( Д. Карпов, В. Дольников )
комментарий/решение олимпиада