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