В. Дольников

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

Задача №2. Дан связный граф. Докажите, что можно раскрасить все его вершины в синий и зелёный цвета и отметить в нём некоторые рёбра так, чтобы каждые две вершины были соединены путём из отмеченных рёбер, каждое отмеченное ребро соединяло вершины разных цветов и никакие две зелёные вершины не были соединены ребром исходного графа. ( В. Дольников )
комментарий/решение олимпиада

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

Задача №4. Вершины связного графа нельзя покрасить меньше чем в $n+1$ цвет так, чтобы соседние вершины были разного цвета. Докажите, что можно удалить из графа $n(n-1)/2$ ребер без потери связности. ( В. Дольников )
комментарий/решение олимпиада

Задача №5. В стране несколько городов, между некоторыми городами курсируют прямые односторонние авиарейсы. Докажите, что можно выделить из всех городов такую группу $A$, что:
1) между городами группы $A$ нет ни одного рейса;
2) из любого города, не лежащего в группе $A$, можно попасть в какой-нибудь город группы $A$ либо прямым рейсом, либо с одной пересадкой в промежуточном городе. ( В. Дольников )
комментарий/решение олимпиада

Задача №6. На плоскости расположено $n$ чёрных и $n$ белых квадратов, каждый из которых может быть переведен в любой другой параллельным переносом. Каждые два квадрата разного цвета имеют общую точку. Докажите, что существует точка, принадлежащая хотя бы $n$ квадратам. ( В. Дольников )
комментарий/решение олимпиада

Задача №7. Вершины связного графа нельзя покрасить меньше чем в $n+1$ цвет так, чтобы соседние вершины были разного цвета. Докажите, что можно удалить из графа $n(n-1)/2$ ребер без потери связности. ( В. Дольников )
комментарий/решение олимпиада

Задача №8. В школе $30$ кружков, в каждом занимаются $40$ детей. Для каждого $i = 1, 2, \ldots, 30$ обозначим через $n_i$ количество детей, занимающихся ровно в $i$ кружках. Докажите, что в этой же школе можно организовать $40$ кружков с $30$ детьми в каждом так, чтобы числа $n_i$ для этих новых кружков были бы теми же самыми. ( В. Дольников )
комментарий/решение(1) олимпиада