Логика → .11 Принцип Дирихле

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

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

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

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

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

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

откуда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так как

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

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

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

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

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

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

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