Изменения
Нет описания правки
# Подсчет помеченных двудольных графов. Граф называется двудольным, если его вершины можно разбить на два множества, таких что ребра соединяют только вершины различных множеств. Сколько существует помеченных двудольных графов?
# Подсчет помеченных связных двудольных графов. Сколько существует помеченных связных двудольных графов?
# Докажите, что в любой перестановке $n$ элементов найдется возрастающая последовательность из $\sqrt{n}$ элементов или убывающая последовательнтсть из $\sqrt{n}$ элементов.
# Докажите, что среди любых 5 точек общего положения на плоскости (никакие три не лежат на одной прямой) можно выбрать 4, которые являются вершинами выпуклого многоугольника.
# Какое число точек необходимо для того, чтобы среди них можно было выбрать 5, являющихся вершинами выпуклого пятиугольник?
# Докажите, что для любого $r$ существует $K(r)$, такое что среди любых $K(r)$ точек общего положения на плоскости (никакие три не лежат на одной прямой) можно выбрать $r$, которые являются вершинами выпуклого многоугольника.
# 🔎 Теорема Ван дер Вардена. Докажите, что для любых $n$ и $k$ найдется такое $W(n, k)$, что если числа от $1$ до $W(n, k)$ покрасить в $k$ цветов, то найдется арифметическая прогрессия длины $n$, покрашенная в один цвет.
# Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что найдутся четыре вершины прямоугольника со сторонами, параллельными осям координат, которые покрашены в один цвет.
# Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что для любых $k$ и $l$ найдутся $k$ строк и $l$ столбцов, что все $kl$ их клеток пересечения покрашены в один и тот же цвет.
