Принцип Дирихле

Разобьём наш квадрат на 25 квадратов со стороной По принципу Дирихле в какой-то из них попадёт по крайней мере три точки из 51 брошенной (иначе в каждом квадрате точек не больше двух, всего точек не больше 50, но ведь 51 больше 50). Эти три точки можно накрыть кругом радиусом, равным половине диагонали квадрата поэтому и кругом радиуса тоже накрыть получится.

Так как все числа натуральные и не превышают то их попарные положительные разности принимают значения от до Всего попарных разностей у чисел штук.

Заметим, что разность имеется не более, чем у одной пары: такое возможно только при наличии чисел и Тогда не менее попарных разностей принимают значения от до

Воспользуемся принципом Дирихле: клетками будем считать числа от до а кроликами — попарных разностей. Если бы в каждой клетке сидело бы не больше двух кроликов, то всего кроликов было бы не более Значит, в какой-то клетке сидит хотя бы кролика, что означает, что какое-то значение для разности принимается не менее трёх раз.

Обозначим общее число медведей через Тогда всего заплывов сделано не менее

С другой стороны, общее число заплывов равно количеству пар островов, то есть Таким образом,

откуда

и, следовательно,

Посчитаем, сколько медведей было в начале и в конце года на каждом из островов. В сумме получится не более потому что каждый медведь в начале и в конце года был на одном из островов. Поскольку

тогда по принципу Дирихле на каком-то острове в начале и в конце года в сумме было не более одного медведя.

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

Аналогично выясняется, что наоборот тоже не бывает: если в начале года на острове был один медведь, а в конце года – ноль, то число заплывов, начинающихся на на больше числа заплывов, заканчивающихся на что снова даёт нечётное общее число заплывов, связанных с (но чётно).

Итого на острове и в начале, и в конце года медведей не было, что и требовалось.

Выберем некоторый предмет — например, физику. По принципу Дирихле, найдётся оценка которую по физике получили не более 7 () учеников. Рассмотрим все возможные наборы оценок для 24-го ученика, в которых по физике стоит Всего таких наборов Каждый ученик, котороый получил по физике, «запрещает» наборов: свой набор и любой набор, в котором изменилась оценка по любому предмету, кроме физики. А остальные ученики «запрещают» всего по одному предмету. Таким образом, всего запретов не более

откуда остаётся вариант для 24-го ученика.

Рассмотрим наибольшие нечётные делители выбранных чисел. У чисел от 1 до нечетными делителями могут быть лишь числа По принципу Дирихле, два из выбранных чисел имеют одинаковые наибольшие нечётные делители. Это означает, что два выбранных числа отличаются только тем, что множитель 2 входит в них в разных степенях. Большее из них будет делиться на меньшее.

Докажем, что минимальное количество мальчиков равно 6. От противного, пусть мальчиков может быть не больше 5. Тогда из этого следует, что девочек хотя бы 15, каждая из них может дружить не больше, чем с 5 мальчиками. Тогда, по обобщённому принципу Дирихле, какие-то 3 девочки имеют одинаковое количество друзей-мальчиков, противоречие.

Пример: пусть …, — мальчики, а …, — девочки. Положим, что ни с кем не дружат; дружат только с дружат только с …, дружат со всеми мальчиками. Очевидно, что условие задачи выполняется.

Рассмотрим центральный квадрат Тогда он обязательно покрыт целиком квадратами со сторонами 9, 10, …, 15. Квадрат покрывает хотя бы одну из центральных клеток, она и будет покрыта хотя бы восьмью квадратами.

Будем считать учёного вершиной в графе, а знакомство — ребром между вершинами. Назовём галочкой тройку точек между которыми проведены рёбра и Будем считать, что — основание галочки, а и — её концы. По условию степень каждой вершины не менее Это значит, что каждая вершина является основанием хотя бы для галочек. Значит, в графе не менее

галочек. Заметим, что для решения задачи достаточно найти две галочки с общими концами. Всего есть пар вершин, то есть концов. Галочек больше, следовательно, найдутся две с общими концами.

Будем говорить, что человек видит тройку если дружит со всеми людьми из этой тройки. Каждый человек видит не менее троек, значит, всего видно не менее троек. С другой стороны, троек Остаётся заметить, что так что по принципу Дирихле какая-то тройка будет видна хотя быть три раза. Возьмём тех трёх человек которые видят и получим искомые две тройки.

Будем называть галочкой с центром в вершине тройку вершин такую, что рёбра и или оба есть, или оба отсутствуют. Пусть — степень вершины Тогда с центром в будет

галочек. Минимум при целых неотрицательных достигается при или и равен 25. Значит, всего в графе не менее 300 галочек. Пар вершин в графе Значит, по принципу Дирихле найдётся пара, на которую смотрят не менее 5 галочек, что и требовалось доказать.

Рассмотрим двудольный граф, в котором в одной доле будут школьники, а в другой — задачи. Ребро будем проводить, если школьник не решил задачу. Тогда степень каждой вершины в доле задач будет три. Будем называть галочкой с центром в тройку вершин такую, что рёбра и проведены. Галочек с центром в доле задач будет а пар учеников Значит, найдётся пара, на которую не смотрит ни одна галочка. Это и будут ученики, которые на двоих решили все задачи.

Предположим противное: любые две из данных бесконечных десятичных дробей совпадают лишь в конечном числе позиций. Для пары обозначим через число разрядов, где дроби и совпали. Обозначим

Тогда суммарное число совпадений по всем парам не превосходит

С другой стороны, по принципу Дирихле в каждом фиксированном разряде среди цифр найдутся хотя бы две равные , значит, в каждом разряде есть хотя бы одно совпадение. Следовательно, совпадений больше, чем — противоречие.

Разобьём доску на 8 прямоугольников Каждый из этих прямоугольников разобьём на 4 пары, как показано на рисунке.

Тут пары, отмеченные как клетки одного цвета, — это клетки, соединенные ходом коня. То есть если поставить двух коней на одноцветные клетки, они побьют друг друга. У нас есть 8 прямоугольников, каждый из которых разбит на 4 пары клеток. Всего выходит 32 пары клеток таких, что если на одной паре клеток стоят сразу два коня, то они бьют друг друга.

Получается, есть 32 пары и 33 коня. Тогда по принципу Дирихле найдется пара клеток, на которых стоят 2 коня. Они и будут бить друг друга.

Заметим, что если числа имеют одинаковый остаток при делении на 2021, то их разность делится на 2021.

Существует ровно 2021 возможный остаток при делении на 2021 — это числа от 0 до 2020. Получается, у нас есть 2022 числа и 2021 возможный остаток. По принципу Дирихле найдутся 2 числа, имеющие один и тот же остаток при делении на 2021. Тогда их разность будет кратна 2021.

Первое решение.

Покажем, что за первую контрольную работу хотя бы человек получили одинаковую оценку. Так как и если предположить, что каждую оценку получило не более человек, то учеников не более противоречие.

Теперь покажем, что среди человек хотя бы у совпадает оценка за первые две контрольные. Допустим, что это не так и учеников не более Тогда всего учеников не более а у нас противоречие.

Мы получили, что хотя бы у человек совпадают оценки за первые две контрольные. Так как всего вариантов оценок за третью контрольную работу то по принципу Дирихле хотя бы у двоих среди уже имеющихся совпадут оценки и за третью контрольную работу, а значит, у них одинаковые оценки за каждую из трех контрольных.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Посчитаем, сколько различных наборов из трех оценок.

Есть варианта оценок за первую работу, варианта оценок за вторую и варианта за третью. Тогда всего различных наборов: а учеников

Тогда по принципу Дирихле найдутся ученика с одинаковыми оценками за каждую из работ.

Всего пар людей:

Нужно доказать, что на какую-то пару придется минимум дежурств. При этом каждый день на дежурство ходит пар, тогда всего за дней на дежурство сходили пар. Так как

по принципу Дирихле найдется пара, дежурившая вместе хотя бы раз.

Пусть выписаны числа Обозначим Тогда по условию десять произведений …, — натуральные числа, не превосходящие 9. Значит, по принципу Дирихле среди них найдутся равные. Пусть это и где Тогда произведение Эти числа подойдут по условию.

Пусть выписаны цифры Обозначим Тогда среди по принципу Дирихле найдутся два числа, которые дают одинаковый остаток при делении на Пусть это и где Тогда что делится на Поскольку — нечётное число, не делящееся на 5, оно взаимно просто с Тогда также делится на Эта последовательность подойдет по условию.

Покажем, что при нужная фигура всегда найдётся. Занумеруем клетки в порядке обхода доски змейкой, начиная с верхнего левого угла. Будем называть клетки в порядке обхода Тогда рассмотрим связные фигуры состоящие из Если среди них есть фигура с суммой чисел, кратной 100, то мы уже нашли нужную фигуру. Если такой нет, то по принципу Дирихле найдутся две фигуры, которые дают одинаковый остаток при делении на Пусть это и где Тогда фигура будет связной, и сумма чисел в ней будет делиться на 100, то есть мы опять нашли нужную фигуру.

Теперь пусть Заполним все клетки единицами. Тогда в любой фигуре сумма чисел будет равна её площади, то есть что не делится на

Пусть выписаны цифры Будем расставлять знаки слева-направо следующим образом: если текущее значение выражения хотя бы 10, будем ставить минус, иначе плюс. Обозначим получившиеся префиксные значения выражений за Тогда среди по принципу Дирихле найдутся два равных числа (по построению Пусть это и где Тогда то есть можно расставить знаки среди так, чтобы в результате получился ноль. Если перед стоял минус, то инвертируем знаки, так что можно считать, что перед стоит плюс. Тогда возьмем в скобки а на остальные места поставим умножение. Таким образом, мы всегда можем получить ноль.