Принцип дирихле
Принципом Дирихле традиционно называют следующее утверждение:
если в 50 клетках сидит 51 кролик, то по крайней мере в одной клетке сидит не менее двух кроликов.
Доказательство этого принципа очевидно. Действительно, пусть это утверждение неверно, тогда в каждой клетке сидит не более одного кролика, и, следовательно, в 50 клетках — не более 50 кроликов, а их должно быть 51. Получили противоречие.
Решение задачи с помощью принципа Дирихле сводится к выбору «кроликов» и «клеток». Иногда не совсем очевидно, кто в данной задаче являчется «кроликом», и что служит «клеткой».
Пример 1.
Имеется 25 конфет 3 сортов. Верно ли, что не менее 9 из них будут какого-то одного сорта?
Решение
Пусть «клетками» у нас будут сорта конфет, а «кроликами» - сами конфеты. По принципу Дирихле найдется «клетка», в которой не менее 25 / 3 «кроликов». Так как 8 < 25 / 3 < 9, то найдется 9 конфет одного сорта.
Утверждение можно доказать, проводя сразу рассуждения от противного. Пусть конфет каждого сорта не более 9, то есть не превышает восьми. Тогда всего конфет не больше 3 × 8 = 24, а по условию их 25. Противоречие.
Пример 2.
В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Доказать, что какие-то три ученика сделали одинаковое количество ошибок.
Решение
По условию задачи, наибольшее число ошибок, сделанных в работе 13. Значит, ученики могли сделать 0, 1, 2,..., 13 ошибок. Эти варианты будут «клетками», а ученики станут «кроликами». Тогда по (обобщенному) принципу Дирихле (14 клеток и 30 зайцев) найдутся три ученика, попавших в одну «клетку», то есть сделавших одинаковое число ошибок.
Пример 3.
В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка — точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.
Решение
Весь ковер можно накрыть такими заплатками.
(1м2 = 10000см2,10000см2: (20*20) = 25) 25-ю заплатами. «Клетка» - заплатка, «кролики» - дырки. Если одна заплатка закрывает две дырки, то всего закроется 50 дырок, но по условию 51 одна дырка, значит, какая-то из заплаток закроет три дырки.
По принципу Дирихле какая-то из этих заплат накроет не менее трех дырок.
Пример 4.
1. a) Докажите, что в любой футбольной команде есть два игрока, которые родились в один и тот же день недели.
b) Докажите, что среди жителей Москвы найдутся десять тысяч, празднующих день рождения в один и тот же день.
Решение
а) Пусть футболисты - это кролики, а дни недели - это клетки. Получаем 7 клеток, в которые надо посадить по крайней мере 11 кроликов, а значит, по принципу Дирихле по крайней мере в одной клетке будут сидеть по крайней мере два кролика.
б) Предположим, что в каждый из 366 дней года родились менее 10000 москвичей. Но отсюда следует, что во всей Москве не больше 366 * 9999 = 3659634 жителей, что, конечно, неверно.
Пример 5.
В мешке лежат шарики двух разных цветов: черного и белого. Какое наименьшее число шариков нужно вынуть из мешка вслепую так, чтобы среди них заведомо оказались два шарика одного цвета?
Решение
Всего надо вынуть три шара, тогда у нас шары — это "кролики", а цвета — это "клетки". А так как клеток меньше, чем кроликов, то по принципу Дирихле найдется клетка, в которой сидят хотя бы два кролика. То есть два шара одного цвета. Легко заметить, что, вытащив два шара, мы можем получить шары разных цветов.
Ответ: 3 шара.
Пример 6.
В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.
Решение
Перед нами миллион ``кроликов''-елок и, увы, всего лишь 600001 клетка с номерами от 0 до 600000. Каждый ``кролик''-елка сажается нами в клетку с номером, равным количеству иголок на этой елке. Так как ``кроликов'' гораздо больше, чем клеток, то в какой-то клетке сидит по крайней мере два ``кролика'' - если бы в каждой сидело не более одного, то всего ``кроликов''-елок было бы не более 600001 штук. Но ведь, если два ``кролика''-елки сидят в одной клетке, то количество иголок у них одинаково.
Пример 7.
Можно ли разложить 44 шарика на 9 кучек так, чтобы количество шариков в разных кучках было различным?
Решение
Предположим, нам это удалось. Упорядочим кучки по возрастанию количества шариков. Тогда в первой кучке должно быть не меньше одного шарика, во второй — не меньше двух, в третьей — не меньше трех и т. д. Всего шариков должно быть не меньше, чем 1 + 2 + 3 +... + 9 = 45. А у нас только 44. Противоречие.
Пример 8.
100 человек сидят за круглым столом, причем более половины из них — мужчины. Докажите, что какие-то двое мужчин сидят друг напротив друга.
Решение
Разобьем всех на 50 пар людей, сидящих друг напротив друга. Тогда мы получаем, что у нас есть 50 пар («клетки»), в которые нужно рассадить не менее 51 мужчины («кролики»). Из принципа Дирихле следует, что в одной из этих пар-«клеток» оба человека — мужчины-«кролики».
Пример 9.
Докажите, что среди любых шести целых чисел найдутся два, разность которых кратна 5.
Решение.
При делении целого числа на 5 возможны пять различных остатков: 0, 1, 2, 3 или 4. Но у нас шесть чисел, значит, среди них обязательно найдутся два с одинаковыми остатками. Если мы рассмотрим их разность, то она будет давать при делении на 5 остаток 0, т. е. будет делиться на 5.
Пример 10.
Докажите, что на шахматной доске нельзя расставить более 8 ладей так, чтобы никакие две из них не били друг друга.
Решение:
На одной горизонтали не может стоять больше одной ладьи — иначе они будут бить друг друга. Значит, ладей можно поставить не больше, чем горизонталей у доски, а их 8. Следовательно, больше 8 ладей поставить на доску нельзя.
Пример 11.
Докажите, что никакая прямая не может пересекать все три стороны треугольника.
Решение: Прямая делит плоскость на две полуплоскости, которые мы назовем «клетками». Три вершины треугольника назовем «кроликами». По принципу Дирихле, «найдется клетка, в которой сидит по крайней мере два кролика», то есть найдутся две вершины, лежащие в одной полуплоскости относительно данной прямой. Сторона, соединяющая эти вершины, не пересекает данную прямую.
Пример 12.
Обязательно ли среди двадцати пяти "медных" монет (т.е. монет достоинством 1, 2, 3, 5 коп.) найдётся семь монет одинакового достоинства?
Решение
Да, обязательно. Если бы монет каждого из четырех типов было не более 6, то всего монет было бы не более 64 = 24, а их 25.
Ответ:
Да. Если бы каждого из четырех типов монет было не более 6, то всего монет было бы не более 6×4 = 24, а их 25.
Принцип крайнего.
Во многих олимпиадах встречаются задачи о сравнении по величине чисел из некоторого конечного набора, расположениях точек на прямой, оценках сумм, разностей и других функций, связанных с числовым набором или таблицей. Часто в таких задачах бывает полезным упорядочить числа набора по величине.
Решение многих задач удобно начинать с рассмотрения «граничного», «крайнего» объекта. Таким объектом может быть наибольшее число, ближайшая точка, граничный случай, наибольшая или наименьшая сторона, одним словом, элемент в котором некоторая величина принимает наибольшее или наименьшее значение. Этот метод решения задач иногда называют принципом (правилом) крайнего.
При решении многих задач ключевой идеей оказывается рассмотрение некоторой крайней или экстремальной величины (элемента, характеристики), связанной с задачей. Этот метод решения задач называется принципом (правилом) крайнего. Для решения многих задач бывает полезно рассмотреть какой¯либо «крайний», «граничный» элемент, т. е. элемент, на котором некоторая величина принимает наибольшее или наименьшее значение, например, наибольшую или наименьшую сторону треугольника, наибольший или наименьший угол и т. д. Этот метод решения задач иногда называют принципом (правилом) крайнего; название это, правда, не общепринятое.
Пример 1.
Зайчиха купила для своих семерых зайчат семь барабанов разных размеров и семь пар палочек разной длины. Если зайчонок видит, что у него и барабан больше, и палочки длиннее, чем у кого-то из братьев, он начинает громко барабанить. Какое наибольшее число зайчат сможет начать барабанить?
Решение
Все зайчата барабанить не могут, так как заведомо не будет барабанить зайчонок, которому достанется самый маленький барабан. С другой стороны, если дать этому же зайчонку и самые короткие палочки, то все остальные зайчата будут барабанить.
Ответ: 6 зайчат.
Пример 2.
По кругу выписано несколько натуральных чисел, каждое из которых не превосходит одного из соседних с ним. Докажите, что среди этих чисел точно есть хотя бы два равных.
Решение
Рассмотрим наибольшее из этих чисел (или одно из них, если таких чисел несколько). Так как оно не меньше и не больше одного из своих соседей, то оно равно ему. Мы нашли пару равных чисел.
Пример 3.
8 грибников собрали 37 грибов. Известно, что никакие двое не собрали грибов поровну и каждый нашёл хотя бы один гриб. Докажите, что какие-то двое из них собрали больше, чем какие-то пятеро.
Решение
Пронумеруем грибников так, чтобы первый набрал больше всех грибов, второй больше среди оставшихся и т.д. Ясно, что первый не мог набрать меньше 9 грибов, т.к. тогда бы все вместе набрали максимум 1 +... + 8 = 36 < 37 грибов. Также второй не мог набрать меньше 7 грибов. Значит, первый и второй вместе набрали хотя бы 7 + 9 = 16 грибов. Учитывая то, что третий набрал хотя бы 6 грибов, то 4-й, 5-й,...,8-й набрали вместе максимум 37 − 16 − 6 = 15 < 16 грибов
Пример 4.
На шахматной доске стоят несколько ладей. Обязательно ли найдется ладья, бьющая не более двух других? (Перепрыгивать через другие фигуры ладья не может.)
Решение
Рассмотрим самую верхнюю ладью, если таких несколько, то самую левую из них. Тогда выше и левее этой ладьи нет других ладей, значит, она бьет не более двух других.
Ответ. Да, обязательно.
Пример 5.
В стране есть несколько городов. Сумасшедший путешественник едет из города A в самый далёкий от него город B. Затем едет в самый далёкий от B город C и т.д. Докажите, что если город С не совпадает с городом А, то путешественник никогда не вернётся обратно в город A.
Решение
Предположим, что на втором шаге путешественник не возвратился в А, т.е. город С отличен от города А. Тогда маршрут от А до B короче маршрута из B в С (поскольку С — наиболее удаленный от B город). В дальнейшем каждый следующий маршрут будет не короче предыдущего, так как каждый раз мы в качестве следующего пункта назначения выбираем наиболее удаленный город. Пусть на некотором шаге путешетвенник все же вернулся в город А, выйдя из некоторого города Х. По доказанному, маршрут от Х до А длиннее маршрута от А до B, а это противоречит тому, что B — наиболее удаленный от А город.
Пример 6.
В космическом пространстве летают 2011 астероидов, на каждом из которых сидит астроном. Все расстояния между астероидами различны. Каждый астроном наблюдает за ближайшим астероидом. Докажите, что за одним из астероидов никто не наблюдает.
Решение
Рассмотрим два астероида A и B, расстояние между которыми наименьшее. Астроном на астероиде A смотрит на астероид B, а астроном на астероиде B смотрит на астероид A. Если найдется астроном, который смотрит на астероид A или B, то найдется астероид на которого никто не смотрит. В противном случае исключим из рассмотрения астероиды A и B. Получим систему из 2011 − 2=2009 астероидов, для которых очевидно выполняется условие задачи. Продолжая так далее, придем к случаю трех астероидов. Выбрав, среди них два, расстояние между которыми наименьшее получим, что на оставшийся астероид никто не смотрит.
Пример 7.
Гоша задумал четыре неотрицательных числа и посчитал их всевозможные попарные суммы (всего 6 штук). Какие числа он задумал, если эти суммы — 1, 2, 3, 4, 5, 6?
Решение
Пусть Гоша задумал числа a ≥ b ≥ c ≥ d ≥ 0. Все суммы различны, поэтому самая маленькая из посчитанных сумм — c + d, следующая за ней — d + b, также самая большая — a + b, а следующая за ней — a + c.
Значит,
c + d = 1,
d + b = 2,
a + b = 6,
a + c = 5.
Тогда
c = 1 − d,
b − c = 1,
b = c + 1 = 2 − d,
a = 5 − c = 4 + d.
Заметим, что a + d = 4 + 2 d и b + c = 3 − 2 d есть числа 3 и 4 в некотором порядке. Число d неотрицательно, значит, a + d ≥ 4 и b + c ≤ 3, значит, d = 0,тогда c = 1, b = 2, a = 4.
Ответ: 0, 1, 2, 4.
Пример 8.
По кругу выписано несколько чисел, каждое из которых равно среднему арифметическому двух соседних с ним. Докажите, что все эти числа равны.
Решение
Рассмотрим наибольшее из этих чисел(или одно из них, если таких чисел несколько). Из того, что оно не меньше своих соседей и равно их среднему арифметическому, следует, что оно равно своим соседям. Проводя аналогичные рассуждения, получаем, что все числа равны.
Математические задачи - Принцип Дирихле
У математиков встречаются весьма странные "принципы", которыми они никогда не поступаются. Впрочем, любой здравомыслящий человек, ознакомившись с этими принципами, вынужден их признать. Вот, например, так называемый принцип Дирихле. Математики очень любят объяснение этого принципа сводить к примеру кроликов в клетках. Поступим так же и мы.
Если в ста (или n) клетках сидит не менее 101 (или n+1) кроликов, то хотя бы в одной клетке находится более одного кролика. Удивительно, что на основе такого простого и даже чуть наивного принципа математикам удается решать весьма трудные задачи, доказывать красивые теоремы, причем не только элементарные.