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

Легко видеть, что фиксированное животное из первого загона встретит животное того же вида ровно раз (то есть при поворотах карусели из ). Тогда суммарное количество встреч животных одного типа равно Тогда по принципу Дирихле при каком-то повороте количество встреч было не меньше, чем то есть при таком повороте не менее животных встретили животное того же вида.

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

Положим для краткости На доске выписаны натуральные числа от до . Рассмотрим выписанные числа, взаимно простые с 6. Таких чисел ровно поскольку среди любых шести подряд идущих чисел ровно два числа взаимно просты с (это числа, дающие остатки и при делении на ). Выпишем делители, которые мы выбрали у этих чисел. Эти делители по крайней мере в раз меньше исходного числа, значит, все они меньше . Кроме того, они взаимно просты с значит, их всего не более Таким образом, мы сопоставили каждому из чисел делитель, причем всего делителей Следовательно, какие-то два делителя совпадают.

Рассмотрим числа Так как их всего то какие-то три из них попадут в одно множество. Сумма любых двух из этих трех чисел больше и, следовательно, больше третьего числа. Значит, существует треугольник с соответствующими длинами сторон, что и требовалось доказать.

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

Вырежем из нашего куба куб и разобьём его на 64 куба .

Предположим, что в каждом кубике закрашено не более трёх ячеек, то есть всего не более 192.

В исходном кубе после этого остались кубики на трёх гранях, имеющих общую вершину. Рассмотрим 64 клетки на одной из этих граней, которые не лежат ни на какой из двух других. Они разбиваются на 16 квадратов , в каждом из которых не более трёх закрашенных ячеек. Итого на трёх гранях получаем не более .

У нас остались не рассмотренными 25 ячеек, образующих три ребра исходного куба, сходящиеся в одной вершине. Среди них закрашены не более 24, так как общая ячейка трёх этих рёбер и три её соседних лежат в одном кубике , значит, среди этих четырёх ячеек не более трёх закрашенных.

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

Правильный шестиугольник можно разбить на шесть правильных треугольников со стороной 1. Тогда хотя бы в одном из этих треугольников будет лежать две отмеченные точки. Расстояние между ними не будет превосходить стороны треугольника.

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

Пусть сёл расположены на левом берегу, а — на правом. Пар сёл на левом берегу Если на правом берегу есть хотя бы села, из которых выходит хотя бы по два рейса фирмы «Сцилла», то по принципу Дирихле из них найдутся два села, из которых ведут по два рейса фирмы «Сцилла» в одну и ту же пару. В этом случае будет выполнено первое условие задачи. В противном случае на правом берегу будет хотя бы сёл, из которых ведут хотя бы шесть рёбер фирмы «Харибда». Так как на левом берегу мы можем выбрать сёл семью способами, по принципу Дирихле на правом берегу найдутся хотя бы сёл ( из которых ведут по шесть рёбер фирмы «Харибда» в одну и ту же шестёрку сёл левого берега. В этом случае выполнено второе условие задачи.

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

Так как

то квадраты этих чисел дают одинаковые остатки при делении на 100. А значит, разность этих квадратов делится на 100.

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

Разобьем доску на квадрата в каком-то из них не меньше коней(по принципу Дирихле, иначе Разделим клетки этого квадрата на группы следующим образом:

По принципу Дирихле, в какой-то из этих групп хотя бы коня(снова, если то Два коня из этой группы и будут бить друг друга.

(a) Заметим, что Тогда по принципу Дирихле, если “ящиками” будут дети, а “кроликами” рублей, то у кого-нибудь из детей будет хотя бы рублей. Значит, он и сможет купить сок.

(b) Рассмотрим двух друзей, у которых наибольшее количество денег. Если они не могут купить шоколадку, то у них не больше рублей. Значит у какого-то из них по принципу Дирихле не больше Так как его количество денег максимально, то у оставшихся не больше рублей. Итого, общее число денег не больше Противоречие.

(c) Рассмотрим теперь троих друзей с наибольшей суммой денег. Если они не могут купить торт, то у них не больше рублей. Значит у какого-то из них по принципу Дирихле не больше Так как его количество денег максимально, то у оставшихся не больше рублей. Итого, общее число денег не больше Противоречие.

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

Можно считать, что таблички стоят в вершинах правильного -угольника. Всего мы можем сделать различный поворот, переводящий -угольник сам в себя, после чего снова получим начальное положение. Следовательно, вместе с начальным мы получим различных сочетаний табличек и неподвижно сидящих дипломатов. Так как мы будем двигать таблички по кругу, каждый дипломат на каком-нибудь шаге будет сидеть против своей таблички. Заметим, что в начальном положении все они сидели против чужих табличек. Поэтому на оставшиеся сочетание приходится правильных положений(так как дипломатов всего По принципу Дирихле найдётся поворот, при котором произойдут по крайней мере два правильных положения, что и означает, что можно повернуть стол так, чтобы не менее двух дипломатов сидело бы против своих табличек.

Рассмотрим множество наборов из трёх оценок за соответствующие контрольные работы. Количество таких наборов равно (4 возможности за каждую из трёх контрольных работ). Поскольку число учащихся больше 64, то по принципу Дирихле каким-то двум ученикам соответствует один набор оценок.

У данного человека среди остальных пяти есть либо не менее трёх знакомых, либо не менее трёх незнакомых ему. Разберём, например, первый случай. Среди этих трёх людей есть либо двое знакомых — тогда они вместе с выбранным нами исходно человеком образуют нужную тройку, либо они все трое попарно незнакомы.

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

Рассмотрим последовательность из 100 чисел: Построим частичные суммы:

Рассмотрим остатки от деления частичных сумм на 100. Эти остатки могут принимать значения от 0 до 99. Таким образом, у нас есть 100 остатков и 100 частичных сумм.

Если хотя бы один из остатков равен 0, то существует частичная сумма, которая делится на 100, и утверждение доказано.

Если ни один остаток не равен 0, то по принципу Дирихле среди 100 остатков, каждый из которых принимает одно из 99 возможных значений (от 1 до 99), найдутся два одинаковых остатка. Пусть это будут остатки частичных сумм и для Тогда:

что означает, что сумма делится на 100.

Замечание. Нам даются условия на квадраты и на бесконечной клетчатой доске. Чтобы привести условия к одному виду, переформулируем их в терминах квадратов Легко видеть, что произвольный квадрат можно разбить на непересекающихся квадратов или на непересекающихся квадратов

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

По условию в каждом квадрате не более пяти белых клеток, значит, не менее четырёх чёрных клеток. А тогда в каждом квадрате не менее чёрных клеток. Отсюда сразу же по принципу Дирихле получаем требуемое ( чёрных котика нужно рассадить в домиков, тогда хотя бы в одном домике будет хотя бы котиков).

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

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

Замечание. На самом деле можно было просить доказать, что квадратов с хотя бы чёрными клетками бесконечно много. Для бесконечной клетчатой доски после разбиения на квадраты это значит то же самое, что в каждом найдётся хотя бы один, ведь эти квадраты обладают одинаковыми свойствами.