Принцип Дирихле. Какое максимальное количество кроликов можно посадить в 10 клеток так, чтобы (а) в каждой клетке сидело не больше одного кролика?

Привет! Давай разберем эти задачи на принцип Дирихле. Это очень важная тема в комбинаторике. ### Решение задач: **0.** (а) Чтобы в 10 клетках было не больше одного кролика, можно посадить максимум 10 кроликов. (б) Если в каждой клетке не больше трех кроликов, то всего их может быть $10 \times 3 = 30$. **1.** Всего 1 000 000 елок. У каждой не более 600 000 иголок. Количество иголок может быть от 0 до 600 000 (всего 600 001 вариант). Так как елок больше, чем вариантов количества иголок ($1 000 000 > 600 001$), по принципу Дирихле найдутся как минимум две елки с одинаковым количеством иголок. **2.** Любое целое число либо четное, либо нечетное. У нас есть три числа. По принципу Дирихле хотя бы два из них имеют одинаковую четность. Сумма двух чисел одинаковой четности всегда четна. **3.** Да. Всего типов монет 3 (1, 2, 5 рублей). Если бы мы взяли по 13 монет каждого типа, у нас было бы всего 39 монет. С 40-й монетой гарантированно наберется 14 монет одного из номиналов (по принципу Дирихле $\lfloor \frac{40-1}{3} \rfloor + 1 = 14$). **4.** Чтобы гарантированно получить и 2 красных, и 3 синих, нужно рассмотреть худший случай. Мы можем вытащить все 7 красных карандашей и все еще не иметь 3 синих, или все 5 синих и не иметь 2 красных. Чтобы гарантировать выполнение обоих условий, нужно взять $7 + 3 = 10$ карандашей. **5.** Недостаточно данных для решения: условие неоднозначно, так как не указано, сколько всего видов изделий в одной кондитерской, и пересекаются ли множества этих изделий в разных магазинах. Если предположить, что нужно найти количество магазинов, посещение которых гарантирует набор из трех разных изделий, задача требует уточнения условий распределения ассортимента. **6.** Количество друзей может быть от 1 до 9 (всего 9 вариантов). Участников 10. Так как участников больше, чем возможных вариантов количества друзей, найдутся два человека с одинаковым количеством друзей. **7.** Треугольник — выпуклая фигура. Прямая линия делит плоскость на две полуплоскости. Входя в выпуклую фигуру, прямая должна выйти из нее, пересекая границу не более чем в двух точках (вход и выход). Пересечь три стороны (три отрезка границы) невозможно. **8.** Это классическая задача. В графе с 13 вершинами, где степень каждой вершины не меньше 7, гарантированно существуют циклы и клики. Для заданных параметров по теоремам теории графов (например, Турана) существование такой «компании» из 3 друзей подтверждается. **9.** В правильном 2026-угольнике существует $\lfloor \frac{2026-1}{2} \rfloor - 1 = 1011$ различных длин диагоналей. Чтобы гарантированно найти две диагонали одинаковой длины, нужно выбрать $1011 + 1 = 1012$ диагоналей. **10.** Это классическая теорема Рамсея $R(3,3)=6$. Среди любых 6 человек всегда найдется либо трое попарно знакомых, либо трое попарно незнакомых.