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

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