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

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

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

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

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

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

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

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

А дети насчитали в сумме шишки, то есть действительно хотя бы одна (если они собрали в сумме шишек, то ровно одна; иначе ещё больше) шишка была потеряна.

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

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

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

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

Если же между каждыми соседними соснами с буквой А растёт хотя бы по одной ёлке, то деревьев с буквой А будет не менее чем а это не так.

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

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

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

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

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

Предположим противное. Согласно принципу Дирихле, какое-то из чисел от до встречается в таблице 6 раз либо меньше. Назовем его Количество строк и столбцов, в которых встречается число не превосходит так как каждая копия занимает одну строку и один столбец. Поскольку каждая строка/столбец пересекает главную диагональ по одной клетке, копии числа находятся в одной строке/столбце с не более чем клетками на главной диагонали. Значит существует клетка на главной диагонали, в “кресте” которой отсутствует число Тогда, по принципу Дирихле, какое-то число записано в ее “кресте” дважды, что противоречит предположению противного.

Рассмотрим всевозможные суммы нескольких из выписанных чисел. Количество таких сумм будет равно (мы учитываем пустую сумму). Согласно принципу Дирихле некоторые две из этих сумм и дают одинаковый остаток при делении на Разность этих сумм делится на и представляет собой сумму нескольких данных чисел со знаками или

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

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

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

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

Отметим, что разность делится на в том случае, если числа оканчиваются на одну и ту же цифру. Всего есть цифр, и на каждую цифру может оканчиваться только одно из выписанных чисел. Значит, выписанных чисел не больше, чем цифр, то есть не больше . Поэтому указанных в условии натуральных чисел не существует.

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

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

В случае ответа “Нет” нам достаточно привести контрпример. Пусть преподаватели распределились так: , , , , , . Нетрудно убедиться, что преподавателей действительно , но при этом ни в какой аудитории не собралось ровно пятеро.

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

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

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

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

Замечание.

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

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

Давайте воспользуемся условием про Кроша: минимальное число в таблице , а максимальное . Поэтому минимальная сумма чисел для Ёжика (он складывает десять чисел таблицы) это а максимальная это Натуральных чисел с до столько же, сколько чисел от до .

Если бы все эти суммы были различны, то у Ёжика получилось бы различных значения, но, как мы поняли выше, различных значений всего . Значит, какие-то две суммы, посчитанные Ёжиком, равны.

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