Принцип Дирихле.

Дирихле Петер Густав Лежен (1805 –1859) – немецкий математик. Родился в Дюрене. В 1822-1827гг. был домашним учителем в Париже. Входил в кружок молодых ученых, которые группировались вокруг Ж. Фурье. 

При́нцип Дирихле́ — утверждение, сформулированное немецким математиком Дирихле в 1834 году, устанавливающее связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий.

Самая популярная формулировка принципа Дирихле такова: «Если в n клетках сидит m зайцев, причем m > n, то хотя бы в одной клетке сидят по крайней мере два зайца».

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

На первый взгляд даже непонятно, почему это совершенно очевидное замечание является весьма эффективным методом решения задач. Дело в том, что в каждой конкретной задаче нелегко бывает понять, что же здесь «зайцы» и «клетки» и почему зайцев больше, чем клеток. Выбор зайцев и клеток часто неочевиден; далеко не всегда по виду задачи можно определить, что следует воспользоваться принципом Дирихле. А главное, этот метод дает неконструктивное доказательство (мы, естественно, не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть), а попытка дать конструктивное доказательство, т. е. доказательство путем явного построения или указания требуемого объекта, может привести к гораздо большим трудностям.

Алгоритм решения:

Принцип Дирихле:

Если в N клетках сидит N+1 или больше кроликов, то найдется клетка, в которой сидят, по крайней мере, два кролика.

  Доказательство:

Докажем принцип Дирихле методом «от противного». Пусть после того, как мы рассадили всех кроликов по клеткам, в каждой из них сидит не более одного кролика. Тогда во всех N клетках не может сидеть более чем N кроликов. Но по условию, рассаженных кроликов не меньше, чем N+1. Возникает противоречие. Следовательно, хотя бы в одной клетке имеется не меньше двух кроликов. Этот простой и очевидный принцип позволяет эффективно решать многие арифметические, алгебраические, геометрические и логические задачи.

 

Пример 1.

Докажите, что никакая прямая не может пересекать все три стороны треугольника.

Решение: Прямая делит плоскость на две полуплоскости, которые мы назовем «клетками». Три вершины треугольника назовем «кроликами». По принципу Дирихле, «найдется клетка, в которой сидит по крайней мере два кролика», то есть найдутся две вершины, лежащие в одной полуплоскости относительно данной прямой. Сторона, соединяющая эти вершины, не пересекает данную прямую.

Пример 2.

Имеется 25 конфет 3 сортов. Верно ли, что не менее 9 из них будут какого-то одного сорта?

Решение: Пусть «клетками» у нас будут сорта конфет, а «кроликами» -сами конфеты. По принципу Дирихле найдется «клетка», в которой не менее 25 / 3 «кроликов». Так как 8 < 25 / 3 < 9, то найдется 9 конфет одного сорта.

Утверждение можно доказать, проводя сразу рассуждения от противного. Пусть конфет каждого сорта не более 9, то есть не превышает восьми. Тогда всего конфет не больше 3 × 8 = 24, а по условию их 25. Противоречие.

Пример 3.

В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Доказать, что какие-то три ученика сделали одинаковое количество ошибок.

Решение: По условию задачи, наибольшее число ошибок, сделанных в работе 13. Значит, ученики могли сделать 0, 1, 2, ..., 13 ошибок. Эти варианты будут «клетками», а ученики станут «кроликами». Тогда по (обобщенному) принципу Дирихле (14 клеток и 30 зайцев) найдутся три ученика, попавших в одну «клетку», то есть сделавших одинаковое число ошибок.

 Задачи для самостоятельного решения.

ЗАДАЧА 1.

Пятеро молодых рабочих получили на всех зарплату - 1500 рублей. Каждый из них хочет купить себе магнитофон ценой 320 рублей. Докажите, что кому-то из них придется подождать с покупкой до следующей зарплаты.

ЗАДАЧА 2.

Можно ли разложить 44 шарика на 9 кучек так, чтобы количество шариков в разных кучках было различным?

Подсказка

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

ЗАДАЧА 3.

Дано 8 различных натуральных чисел, не больших 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.

Задача 4.(новое)

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

               Задача 5.( новое)

Шесть школьников съели семь конфет. Докажите, что один из них съел не менее двух конфет.

 Задача 6.(новое)

Докажите, что в любой футбольной команде из 11 человек есть два игрока, которые родились в один и тот же день недели.