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

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

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

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

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

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

Замечание.

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

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

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

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

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

Предположим, что на мишени НЕЛЬЗЯ выделить квадрат , внутрь которого Крош не попал. Тогда Крош попал во все квадратов. Но ведь он сделал выстрелов и каждым выстрелом мог попасть только в один квадрат. Значит, он сделал не больше попаданий и точно меньше . Следовательно, всё-таки на мишени МОЖНО выделить квадрат , внутрь которого Крош не попал.

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

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

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

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

Каждое число в вершине участвует ровно в четырёх суммах. Заметим, что для получения простой суммы к числам 6 и 12 можно прибавить только 1, 5, 7 и 11. Значит для вершин, в которых стоят числа 6 и 12, наборы соседних чисел и чисел, стоящих от них через две вершины, должны совпадать. Однако, для каждой вершины эти наборы различны, поэтому хотя бы одна из сумм не будет являться простым числом.

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

Разобьем всю доску на доминошки . Их будет 32. Значит в какой-то доминошке стоят 2 фишки и значит эти 2 фишки стоят в соседних по стороне клетках..

Разобьем всю доску на квадраты . Их будет 16. Значит, в каком-то квадрате стоят 2 короля, и значит, эти 2 короля бьют друг друга.

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

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

Пример размещения одиннадцати уголков на рисунке.

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

Покажем, что при такая пара может не найтись. Пронумеруем мальчиков и девочек числами от до Пусть мальчику с номером нравятся все девочки с номерами по модулю а девочке с номером нравятся все мальчики с номерами (также по модулю ). Легко проверить, что в этом случае требуемой пары нет.

Пусть на первом туре было кабинетов с участниками, кабинетов с участниками (все и по условию). Аналогично во второй тур пусть было кабинетов с участниками, кабинетов с участниками. Также очевидно, что и

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

То есть Но тогда по аналогичным соображениям  — противоречие.

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

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

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

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