Принцип Дирихле и его применение

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

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

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

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

Краткая биография

Дирихле Петер Густав Лежен (13. 2. 1805– 5. 5. 1859) – немецкий математик. Родился в Дюрене. В 1822-1827гг. был домашним учителем в Париже. Входил в кружок молодых ученых, которые группировались вокруг Ж. Фурье. В 1827 занял место доцента в Бреславе; с 1829 работал в Берлине. В 1831-1855гг. – профессор Берлинского университета, после смерти К. Гаусса (1855г. ) – Гёттингенского университета. Сделал ряд крупных открытий в теории чисел ; установил формулы для числа классов бинарных квадратичных форм с заданным определителем и доказал теорему о бесконечности количества простых чисел в арифметической прогрессии из целых чисел, первый член и разность которой взаимно просты. К решению этих задач применил аналитические функции, названные функциями (рядами) Дирихле. Создал общую теорию алгебр, единиц в алгебраическом числовом поле. В области математического анализа впервые точно сформулировал и исследовал понятие условной сходимости ряда, дал строгое доказательство возможности разложения в ряд Фурье кусочно-непрерывной и монотонной функций, что послужило обоснованием для многих дальнейших исследований. Значительны труды Дирихле в механике и математической физике , в частности в теории потенциала. С именем Дирихле связаны задача, интеграл (ввел интеграл с ядром Дирихле), принцип, характер, ряды. Лекции Дирихле имели огромное влияние на выдающихся математиков более позднего времени, в том числе на Г. Римана , Ф. Эйзенштейна, Л. Кронекера , Ю. Дедекинда.

Принцип Дирихле утверждает, что если множество из N элементов разбито на n непересекающихся частей, не имеющих общих элементов , где N > n ,то по крайней мере в одной части будет более одного элемента.

Самая популярная формулировка принципа Дирихле такова:

"Если в n клетках сидит N зайцев , причем N > n , то хотя бы в одной клетке сидят по крайней мере два зайца.

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

Авторские задачи, решаемые с помощью принципа

Дирихле.

Задача №1

К Новому Году в детском саду ребята делали фонарики. В группе 30 детей. Петя Пяточкин сделал 12 фонариков, а остальные – меньше. Докажите, что хотя бы три ребенка сделали одинаковое количество фонариков (может быть, по 0 шт. ).

РЕШЕНИЕ:

Здесь “зайцы”- дети ,а “клетки” - число сделанных фонариков. В клетку 0 “посадим” всех, кто не сделал ни одного фонарика ,в клетку 1- тех, у кого од ин фонарик ,в клетку

2- два фонарика,и так до клетки 12 ,куда

П опал Петя Пяточкин. Применим принцип

Дирихле. Докажем утверждение за д ачи от противного. Предположим , никакие три ребенка не сделали по одинаковому числу фонариков ,то есть в каждую из клеток 0,1,. ,11 попало мен ьше трех детей. Тогда в каждой из них два челов ека или меньше, а всего в этих 12 клетках не больше 24 человек. Добавив Петю Пяточкина, все равно не наберем 30 ребят. Получили противоречие.

Может быть и такое, что кроме Пети вообще никто не сделал ни одного фонарика ,то есть сделал по 0 штук.

Задача № 2

В научно-исследовательском институте 33 отдела. Всего работает 1150 человек. Найдется ли отдел, в котором меньше 35 сотрудников?

РЕШЕНИЕ:

Допустим,что в каждом отделе работает по 35 сотрудников. Тогда общее число сотрудников будет : 35 х 33 = 1155 человек , что противоречит условию. Следовательно , если в 32 отделах р аботает по 35 человек, то 35 х 32 = 1120 человек , и в 33-м отделе будет только 30 человек. Поэтому, хотя бы в одном отделе работает менее 35 человек.

Задача № 3

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

РЕШЕНИЕ:

Выберем любых двух гостей, которые не знакомы между собой. ( Если таких нет,то все гости знакомы между собой

,значит,у каждого имеется 24 знакомых, и задача решена).

Из оставшихся 23 гостей каждый знаком с одним из этих двух,иначе мы имели бы тройку гостей,среди которых не было бы знакомых. Тогда у одного из выбранны х двух гостей не менее12 з на к ом ых (23 "зайца" рассажены в двух "клетках").

Задача № 4

За пять лет дачники вырастили и собрали 31 кг. черной смородины. Причем каждый год они собирали урожай больший,чем в предыдущем году. На пятом году они собрали ягод втрое больше,чем в первый год. Какой был урожай смородины на четвертый год?

РЕШЕНИЕ:

Пусть каждый год дачники собирали

С1,С2,С3,С4,С5 кг. смородины.

Причем: С1 < C 2< C 3< C 4< C 5 , и С5=3С1

Если С1=3 , то С5=9 ,значит С2+С3+С4=19

Учитывая условия задачи, это равенство может быть выполнено в двух случаях:

1) С2=4; С3=7; С4=8

2) С2=5; С3=6; С4=8

Таким образом ,на четвертый год дачники собрали 8 кг. смородины.

Задача № 5

При раскопках древнего храма археологи нашли клад. Смогут ли они увезти 50 сундуков з олота, веса которых равны

370 кг, 372 кг,. , 466 кг, 468 кг. на семи трехтонных грузовиках?

РЕШЕНИЕ:

Если каждая машина увезет по 7 сундуков, то они увезут только 49 сундуков, следова - тельно, одна машина должна будет взять

8 сундуков. 8 сундуков даже самого мало - го веса весят:

370+372+374+376+378+380+382+384=3016 кг.

Это больше трех тонн. Таким образом, семь трехтонок не смогут увезти 50 сундуков золота.

Задача № 6

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

РЕШЕНИЕ:

При делении на 11 получается один из 11остатков:0,1,2,,10.

У нас же дано 12 чисел, и по принципу Дирихле остатки от деления на 11 у каких-то двух из них совпадают. Разность этих двух делится на 11.

Задача № 7

На прослушивание пришло 65 пианистов. Им предложили для исполнения 3 инвенции И. С. Баха. За исполнение каждой инвенции ставилась одна из оценок : 2 ,3 ,4 ,5. Верно ли, что найдутся два исполнителя, получившие одинаковые оценки на всех экзаменах?

РЕШЕНИЕ:

Рассмотрим множество наборов из трех оценок за соответствующее исполнение. Количество таких наборов равно 4х4х4=64 (4 возможности за каждое из трех исполнений).

Поскольку число участников больше 64,то по принципу Дирихле каким-то двум исполнителям соответствует один набор оценок.

Применение принципа Дирихле к геометрическим задачам.

Некоторые геометрические задачи решаются методами ,в какой-то мере аналогичными принципу Дирихле. Сформулируем соответствующие утверждения:

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

2) Если на окружности радиуса 1 расположено несколько дуг, сумма длин которых больше 2р, то по крайней мере две из них имеют общую точку.

3) Если внутри фигуры площадью 1 расположено несколько фигур, сумма площадей которых больше

1,то по крайней мере две из них имеют общую точку.

Задача № 1

В квадрат со стороной 1 м. бросили 51 точку. Докажите,что какие-то три из них можно накрыть кругом радиуса 1 /7 м.

РЕШЕНИЕ:

Разобьем квадрат на 25 равных квадратов ( со стороной 1 /5 м).

Докажем,что в каком-то из них находятся по кайней мере три из данных точек. Применим принцип

Дирихле : если бы в каждом квадратике (внутри или на сторонах) было не больше двух точек, то всего их было бы не больше 50. Опишем окружность вокруг квадратика, в котором лежат три ( или более ) из данных точек. Нетрудно вычислить ее радиус, он меньше 1/7 м.

Задача №2

На клетчатом листе бумаги размером 8х8 Марина нарисовала 15 звездочек. Докажите, что найдется квадрат размером 2х2 , в котором не будет ни одной звездочки. (Каждая звездочка размещается внутри клетки размером 1х1 ).

РЕШЕНИЕ:

Разобьем прямоугольник на квадра- ты 2 х2 (см. рисунок). Получилось 16 квадратиков - это "клетки". Даже если звездочки "зайцы расположить по 1 в каждом квадрате, то заняты будут только

15 "клеток",а одна будет пустая.

Задача № 3

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

РЕШЕНИЕ:

Полуплоскости, на которые прямая разбивает плоскость треугольника

АВС, обозначим через q 1 и q 2 ; эти полуплоскости будем считать открытыми (то есть не содержащими точек прямой l ). Вершины рассматривае мого треугольника ( точки А, В, С) будут "зайцами", а полуплоскости q 1 и q 2 - "клетками". Каждый заяц попадает в какую-нибудь клетку

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

Пусть, скажем, точки А и В находятся в одной полуплоскости, то есть лежат по одну сторону от прямой l. Тогда отрезок АВ не пересекается с l. Итак, в треугольнике АВС нашлась сторона, которая не пересекается с прямой l.

Задача № 4

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

РЕШЕНИЕ:

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

Задача № 5

В прямоугольнике 5х6 закрашено 19 клеток. Докажите,что в нем можно выбрать квадрат 2х2 , в котором закрашено не менее трех клеток.

РЕШЕНИЕ:

Разделим прямоугольник на 6 частей по 5 клеток (см. рисунок).

Согласно принципу Дирихле в одной из этих частей будет закрашено не менее 4 клеток.

Тогда в квадрате 2х2,содержащемся в этой части, закрашено либо 3,либо

4 клетки. Это и будет искомый квадрат.