#5 Принцип Дирихле I

Есть \(12\) месяцев и \(13\) человек. По принципу Дирихле в каком-то месяце родились хотя бы двое.

Ящики — последние цифры \(0,1,\ldots,9\). Чисел \(11\), значит два попали в один ящик.

Предположим, что нет трёх одного цвета. Тогда каждого цвета не более \(2\), всего не более \(4\), но носков \(5\). Противоречие.

Остатков по модулю \(n\) всего \(n\). Среди \(n+1\) чисел два имеют одинаковый остаток. Их разность делится на \(n\).

Пары: \((1,10),(2,9),(3,8),(4,7),(5,6)\). Выбрано \(6\) чисел, пар \(5\), значит из одной пары выбраны оба числа. Их сумма \(11\).

Есть \(8\) классов остатков. Если в каждом не более \(2\) чисел, всего не более \(16\), но чисел \(17\). Значит в каком-то классе не менее \(3\).

У каждого человека число знакомых от \(0\) до \(5\). Если есть человек с \(0\) знакомых, то нет человека с \(5\) знакомых; если есть с \(5\), то нет с \(0\). Значит реально возможны не более \(5\) значений для \(6\) человек. По принципу Дирихле два значения совпадают.

Каждое число имеет вид \(2^k m\), где \(m\) нечётно. Возможных нечётных частей в диапазоне \(1,\ldots,18\) всего \(9\). У \(10\) выбранных чисел две нечётные части совпадают. Тогда эти числа имеют вид \(2^a m\) и \(2^b m\), и меньшее делит большее.

Есть \(100\) остатков по модулю \(100\). Среди \(101\) чисел два имеют одинаковый остаток, значит их разность делится на \(100\).

Есть \(10\) пар, каждая имеет сумму \(21\). Выбрано \(11\) чисел, значит одна пара выбрана полностью.

После разбиения на \(4\) единичных квадрата \(5\) точек дают две точки в одном маленьком квадрате. Расстояние между любыми двумя точками единичного квадрата не больше его диагонали \(\sqrt{2}\).

Пусть \(s_i\) — сумма первых \(i\) чисел. Если какой-то \(s_i\) делится на \(10\), готово. Иначе \(10\) частичных сумм имеют только \(9\) ненулевых остатков, значит две имеют одинаковый остаток. Их разность — сумма подряд идущего блока, кратная \(10\).

Рассмотрим \(s_1,\ldots,s_n\). Если некоторый \(s_i\equiv0\pmod n\), то сумма первых \(i\) чисел подходит. Иначе все \(s_i\) имеют один из \(n-1\) ненулевых остатков. Две суммы имеют одинаковый остаток; их разность является суммой непустого подряд идущего блока и делится на \(n\).

Есть \(6\) ящиков остатков: \(0\), \(5\), пары противоположных остатков. Семь чисел дают два в одном ящике. Если остатки равны, разность делится на \(10\). Если они противоположны, сумма делится на \(10\).

Каждая точка имеет тип чётности \((x\bmod2,y\bmod2)\), всего \(4\) типа. Среди \(5\) точек две имеют одинаковый тип. Тогда суммы их \(x\)-координат и \(y\)-координат чётны, значит середина имеет целые координаты.

Выберем человека \(A\). Среди остальных \(5\) либо есть \(3\) знакомых с \(A\), либо \(3\) незнакомых с \(A\). В первом случае, если среди этих троих есть знакомая пара, вместе с \(A\) получаем троих попарно знакомых; если нет, эти трое попарно незнакомы. Второй случай аналогичен: если среди трёх незнакомых с \(A\) есть незнакомая пара, вместе с \(A\) получаем троих попарно незнакомых; иначе эти трое попарно знакомы.

Соединим середины сторон и получим \(4\) маленьких равносторонних треугольника со стороной \(1\). Пять точек дают две в одном маленьком треугольнике. Расстояние между любыми двумя точками такого треугольника не больше \(1\).

Есть \(50\) пар соседних чисел. Выбрано \(51\) число, значит в одной паре выбраны оба числа. Они последовательные.

Остатков по модулю \(5\) всего \(5\). Среди \(6\) чисел два имеют одинаковый остаток, поэтому их разность делится на \(5\).

Непустых подмножеств \(2^{10}-1=1023\). Сумма любого подмножества лежит от \(1\) до \(1000\), то есть возможных сумм не более \(1000\). По принципу Дирихле две разные непустые группы имеют одинаковую сумму.

Непустых подмножеств \(1023\). Их суммы лежат от \(1\) до \(990\), возможных сумм не более \(990\). Значит есть два разных непустых подмножества с равной суммой. Удалим из них общие элементы. Оставшиеся части имеют равные суммы; они не обе пусты, иначе исходные подмножества совпадали бы. Получили две непустые непересекающиеся группы с равной суммой.

Выберем произвольного человека \(A\). Среди остальных \(9\) каждый либо знаком с \(A\), либо не знаком. Два ящика: знакомые и незнакомые. По усиленному принципу Дирихле в одном из них не менее \(\lceil9/2 ceil=5\) человек. Значит у \(A\) есть \(5\) знакомых или \(5\) незнакомых.

Запишем числа в любом порядке и применим лемму о частичных суммах к этой последовательности длины \(n\). Получим непустой подряд идущий блок, сумма которого делится на \(n\). Такой блок является подмножеством выбранных чисел.

Для каждого числа \(a_i\) запишем пару \((u_i,d_i)\), где \(u_i\) — максимальная длина возрастающей подпоследовательности, начинающейся с \(a_i\), а \(d_i\) — максимальная длина убывающей, начинающейся с \(a_i\). Если нет монотонной подпоследовательности длины \(4\), то \(u_i,d_i\in\{1,2,3\}\), всего \(9\) пар. Для \(10\) чисел две пары совпадают: пусть \(iu_j\), противоречие равенству пар. Если \(a_i>a_j\), аналогично \(d_i>d_j\). Противоречие.