Д. Карпов

Задача №1. В стране Графинии

$n$

$( n \geq 2)$ городов. Некоторые города соединены беспосадочными авиалиниями (по каждой авиалинии выполняются рейсы в обоих направлениях) таким образом, что из любого города можно самолётами (возможно, с пересадками) добраться до любого другого, но закрытие любой авиалинии нарушает это свойство. При этом из любого города выходит не больше

$d$ авиалиний. Докажите, что все города Графинии можно разбить не более чем на

$\frac{n}{2} + d$ групп таким образом, чтобы каждая авиалиния соединяла города из разных групп и для любых двух групп существовало не более одной авиалинии, соединяющей города из этих групп. ( Д. Карпов )
комментарий/решение(1) олимпиада

Задача №2. В стране Эйлерии 101 город. Каждые два города соединены двусторонним беспосадочным рейсом одной из 99 авиакомпаний. Известно, что из каждого города выходят рейсы всех 99 компаний. Назовём

$\textit{треугольником}$ три города, попарно соединённых рейсами одной и той же компании. Докажите, что в Эйлерии не больше одного треугольника. ( И. Богданов, Д. Карпов )
комментарий/решение(1) олимпиада

Задача №3. В городе N. существует множество оппозиционных обществ, каждое из которых состоит из 10 членов. Известно, что для любых 2004 обществ найдется человек, состоящий хотя бы в 11 из них. Докажите, что правительство может арестовать 2003 человека так, чтобы в каждом обществе хотя бы один член был арестован. ( Д. Карпов, В. Дольников )
комментарий/решение олимпиада

Задача №4. Существуют ли 10000 последовательных семизначных чисел, которые можно разбить на 99 групп так, чтобы сумма всех чисел в каждой из групп была одной и той же? ( Д. Карпов )
комментарий/решение(1) олимпиада