"Помни принцип Дирихле, кролики сидят в тебе!" - народная мудрость
Формулировка 1: Если в n "клетках" сидят не менее n+1 "кроликов", то в какой-то из "клеток" сидят не менее 2-х "кроликов".
Доказательство: Противоречие к формулировке звучит так: "в каждой клетке сидит не более одного кролика". Но тогда кроликов, очевидно, не больше, чем клеток?! Поэтому есть клетка, где кроликов не менее двух ч.т.д.
Формулировка 2: Если в n клетках сидит не менее kn+1 кроликов, то хотя бы в одной клетке сидит по крайней мере k+1 кроликов. (При k = 1 это случай Ф.1)
Доказательство: Действительно, если бы во всех клетках сидело не более k кроликов, то тогда в n клетках сидело бы не более kn кроликов, что противоречит условию.
Формулировка 3: Если сумма n чисел равна S, то среди них есть число, не меньшее S/n, и число, не большее S/n. (Это утверждение обобщает принцип Дирихле на случай нецелого числа кроликов.)
Доказательство: Действительно, если все числа (строго!) меньше S/n, то их сумма меньше S, а если все числа (строго!) больше S/n, то их сумма больше S. В обоих случаях получаем противоречие ч. т.д.
(!) Принцип Дирихле и различные его усиления - едва ли не самая частая идея в олимпиадных задачах, поэтому на данную лекцию стоит обратить особое внимание.
Простенькие задачки
Задача 1. В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.
Доказательство: 25 ящиков - "кроликов" рассадим по 3 клеткам-сортам. Так как 25 = 3 · 8 + 1, то применим "обобщенный принцип Дирихле" для N = 3, k = 8 и получим, что в какой-то клетке-сорте не менее 9 ящиков.
Комментарий: В целом довольно несложно увидеть, что 25 = 3 · 8 + 1, что сразу дает правильный ход мысли.
__________________________________________________________________________________________
Задача 2 В стране Курляндии m футбольных команд (по 11 футболистов в каждой). Все футболисты собрались в аэропорту для поездки в другую страну на ответственный матч. Самолет сделал 10 рейсов, перевозя каждый раз по m пассажиров. Еще один футболист прилетел к месту предстоящего матча на вертолете. Докажите, что хотя бы одна команда была целиком доставлена в другую страну.
Доказательство: Так как перевезено всего 10m + 1 (из условия) футболистов, то, рассадив по клеткам-командам, получаем, что в какой-то клетке сидит 11 футболистов.
Комментарий: Здесь мы используем Ф.2 и догадаться до него несложно. Ведь всего перевезли 10m + 1, а команд m, отсюда и выходит применение данной формулировки.
Задачи многоходовки
Задачи 3. В бригаде 7 человек и их суммарный возраст – 332. Доказать, что из них можно выбрать 3 человека, сумма возрастов которых не меньше 142 лет.
Решение 1. Выберем трех старших членов бригады. Если им вместе 142 года, то хотя бы одному из них больше 47 лет. Если самому младшему из троих больше 47 лет, то им троим больше 142 лет. Пусть самому младшему из троих 47 лет или меньше, им троим вместе менее 142 лет. Тогда на долю остальных четверых приходится более 320 – 142 = 190 лет. Разделим 190 на 4 с остатком: 190 =4•47 + 2. Тогда по принципу Дирихле одному из четверых больше 47 лет. Это противоречит выбору троих самых старших в бригаде.
Решение 2. Рассмотрим все возможные тройки рабочих бригады. Всего таких троек = 35. Сумма их суммарных возрастов равна 332 ∙ 35 = 4980. Значит по принципу Дирихле есть тройка, суммарный возраст в которой не меньше, чем 4980 : 35, что больше 142.
Решение 3 . Средний возраст трех самых старших не меньше среднего возраста по бригаде, который равен . Поэтому сумма их возрастов по меньшей мере года.
Комментарий: Решения на любой вкус и цвет)))
__________________________________________________________________________________________
Задача 4. На планете Тау Кита суша занимает больше половины всей площади. Докажите, что таукитяне могут прорыть через центр планеты шахту, соединяющую сушу с сушей.
Решение: Возьмем на планете множество точек суши и множество точек, диаметрально противоположных суше. Сумма площадей этих множеств - удвоенная площадь суши, что строго больше площади планеты. Тогда эти 2 множества перекроются. В точке перекрытия и можно будет начать рыть туннель.
Комментарий: Будем считать кроликами точки суши, а клетками - пары диаметрально противоположных точек планеты. "Количество" кроликов в данном случае - это площадь суши, а "количество" клеток - половина площади планеты. Поскольку площадь суши больше половины площади планеты, то "кроликов больше, чем клеток". Тогда есть клетка, в которой сидит не менее двух кроликов, т. е. пара противоположных точек, обе из которых - суша. Эти точки и надо соединить туннелем.
Остатки сладки (Задачи на теорию чисел)
Задача 5. Докажите, что существует степень тройки, оканчивающаяся на 001.
Доказательство:
Комментарий: Есть очень хорошее и короткое решение по теореме Эйлера. Если хотите сделаю отдельную статью по этому поводу (правда когда я сам изучу это).
__________________________________________________________________________________________
Задача 6. Докажите, что среди чисел, записываемых только единицами, есть число, которое делится на 1987.
Доказательство: Рассмотрим 1988 чисел-«кроликов» 1, 11, 111, …, 111 … 11 (1988 единиц) и посадим их в 1987 клеток с номерами 0, 1, 2, …, 1986 – каждое число попадает в клетку с номером, равным остатку от деления этого числа на 1987. Тогда (по принципу Дирихле) найдутся два числа, которые имеют одинаковые остатки при делении на 1987. Пусть это числа 11 … 11 (m единиц) и 11 … 11 (n единиц), причем m > n. Но их разность, которая делится на 1987, равна 11 … 1100 … 00 (m – n единиц и n нулей). Сократим все нули – ведь они не имеют никакого отношения к делимости на 1987 – и получим число из одних единиц, которое делится на 1987.
Из данных задач вытекает четвертая формулировка принципа Дирихле для делимости:
Формулировка 4. Для доказательства делимости на n достаточно рассмотреть набор n+1 чисел и остатки от их делимости на n.
Задачки на закуску (Лучше сначала решите, а потом читайте решение)
Задача 7. Докажите, что среди любых шести человек всегда найдутся либо трое попарно знакомых, либо трое попарно незнакомых.
Доказательство: Поставим шесть точек, соответствующие шести людям. Если люди знакомы между собой, соединим соответствующие точки красным отрезком, если не знакомы, то синим. Тогда, если на нашем рисунке есть красный треугольник, это означает, что существует три попарно знакомых между собой человека, а если есть синий треугольник, то существует три попарно незнакомых между собой человека.
Рассмотрим любую из шести точек. Из неё выходит пять отрезков. Из пяти отрезков есть по крайней мере три одного цвета. Предположим, есть три синих отрезка (случай, когда есть три красных отрезка, рассматривается аналогично.)
Если какие-то два конца этих отрезков соединены между собой синим, то есть синий треугольник (см. первый рис.).
Если же все концы этих отрезков соединены между собой красным, то получается, что есть красный треугольник (см. второй рис.).
Комментарий: Данная задача является ярким примером полезности знания теоремы Рамсея и чисел Рамсея.
__________________________________________________________________________________________
Задача 8. В узлах клетчатой плоскости отмечено 5 точек. Доказать, что есть две из них, середина отрезка между которыми тоже попадает в узел.
Доказательство: Обозначим четную координату точки буквой Ч, нечетную - Н. У каждой точке две координаты, поэтому возможны случаи (Ч,Ч), (Ч,Н), (Н,Ч), (Н,Н). Возможны четыре случая, а точек дано пять, следовательно, обязательно найдется по крайней мере две точки, имеющие координаты одной четности. Возьмем две точки с координатами одной четности и найдем координаты середины этого отрезка. Осталось заметить, что координаты получаются как полусумма соответствующих координат. В нашем случае это будут целые числа, и соответствующая точка попадает в узел.
Комментарий: Важно помнить, что помнить целые числа бывают четные и нечетные.
__________________________________________________________________________________________
Задача 9*. Дано 11 различных натуральных чисел, не больших 20. Докажите, что из них можно выбрать два числа, одно из которых делится на другое.
Ну и последнюю задачку я оставлю без решения, а в следующем посте вы увидите решение. Кто хочет присылайте свои решения мне или в комментарии, а также пишите как вам такой формат и статья в целом)