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

Содержание

Аннотация   ……………………………………………………………………….3

Введение   …………………………………………………………………………4

1. Краткая биография Петера Густава Лежена Дирихле   ………………....5
2. Формулировка и доказательство принципа Дирихле   ……………..…...6
3. Решения задач с помощью принципа Дирихле   ……………………….11

Заключение   ……………………………………………………………………..18

Список использованной литературы   …………………………………………19

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Аннотация

 

В работе мною был рассмотрен и изучен принцип Дирихле.

Проведен в работе анализ решения задач по принципу Дирихле.

Собраны и исследованы  фактические материалы о самом Петере Густава Лежене Дирихле, о его принципе решения задач.

Приведена демонстрация решения  задач с помощью принципа Дирихле.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

Моя работа касается одного из интересных эвристических методов решения математических задач - принципа Дирихле. Принцип назван в честь немецкого математика Петера Густава Лежена Дирихле (1805-1859г.г.), который успешно применял его к доказательству арифметических утверждений.

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

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

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

Целями работы являются следующие:

1. Изучить краткую биографию  немецкого математика;

2. Формулировка и доказательство принципа Дирихле;

3. Выявление круга задач, решение которых основывается на принципе Дирихле;

4. Демонстрация решения задач с помощью принципа Дирихле.

 

 

1. Краткая биография Петера Густава Лежена Дирихле

 

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

 

 

 

 

 

2. Формулировка и доказательство принципа Дирихле

 

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

Основная идея решения  задач, выводимая из принципа Дирихле, заключается в следующем:

- если при разбиении множества элементов на не пересекающие части удаётся установить факт взаимосвязи между количеством элементов данного множества (N) и числом его частей (n) в виде N>n, то тогда можно утверждать, что среди этих частей такая, которая содержит более одного элемента.

По традиции в популярной литературе принцип объясняется на примере «зайцев и клеток»: „Если десять зайцев сидят в девяти клетках, то в некоторой клетке сидят не менее двух зайцев".

Докажем принцип Дирихле.

Если n зайцев сидят в k клетках, причём n>k, то найдётся клетка, в которой сидят не меньше, чем n/k зайцев, и найдётся клетка, в которой сидят не больше, чем n/k зайцев».

Допустим, что в каждой клетке сидят меньше, чем n/k зайцев. Тогда во всех клетках вместе зайцев меньше, чем n•k/k=n. Противоречие с условием.

Аналогично, если допустить, что в каждой клетке сидят больше, чем n/k зайцев, то во всех клетках вместе зайцев будет больше, чем n•k/k=n. Это тоже противоречит условию утверждения. Следовательно, требуемое доказано.

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

Зная принцип Дирихле, можно догадаться, в каких случаях  его применять. Например, если каждому  элементу множества А соответствует ровно один элемент множества В, то элементы множества А можно назвать зайцами, а элементы множества В – клетками ².

Рассмотрим две простейшие задачи.

Задача № 1.

У мальчика 9 медных монет (Достоинством 1коп., 2коп., 3коп., 5коп.). Докажите, что у него есть хотя бы три монеты одинакового достоинства.

Решение.

Установим соответствие между  двумя множествами (А и В), где А - множество монет, а В - множество достоинств монет.

При этом монеты будут зайцами, а достоинства монет - клетками.

1 коп   2 коп   3 кон   5 коп

2мон.   2мон.   2мои.  2мон.

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

 

Задача № 2.

В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.

Решение.

В данной задаче ящики - это  «зайцы», а сорта - «клетки».

25 ящиков - «зайцев» рассадили  по 3 - «клеткам» - сортам. Так как 25=3-8+1, то получим, что в какой-то - «клетке» - сорте не менее 9 «зайцев» - ящиков.

Теперь рассмотрим решение более сложных задач.

 

 

Задача № 3.

Докажем, что в любой компании из 5 человек есть двое, имеющих одинаковое число знакомых в этой компании.

Решение.

У каждого члена компании может быть от 0 до 4 знакомых. Если у  каждого компаньона 0 знакомых, то утверждение  доказано. Заметим, что если у кого-то из компаньонов 4 знакомых, то ни у кого не может быть 0 знакомых. То есть 0 и 4 знакомых исключают друг друга.

Рассмотрим вариант, когда  у каждого члена компании от 1 до 4 знакомых. Тогда количество знакомых - клетки, а компаньоны » зайцы.

1зн.  2зн.  3зн.  4зн.

  1    1    1    1

Получаем, что «зайцев» - компаньонов на 1 больше чем «клеток» -количество знакомых. Поэтому как минимум у двоих компаньонов есть одинаковое число знакомых,

 

Задача № 4.

10 школьников на олимпиаде  решили 35 задач, причём известно, что среди них есть школьники,  решившие ровно одну задачу, школьники,  решившие ровно две задачи  и школьники, решившие ровно  три задачи. Докажите, что есть, по крайней мере один школьник, решивший не менее пяти задач,

Решение.

Пусть школьники «клетки», а задачи «зайцы». Установим соответствие между этими двумя множествами.

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10

1 2 3 4 4 4 4 4 4 4 4

 

Согласно условию найдутся 7 школьников, решивших 29 задач.

35-(1+2+3)=29 (задач).

Но 29=7-4+1! Значит, «оставшийся» 1 «заяц», который попадёт в одну из семи клеток с номерами 4-10. Следовательно, по крайней мере один из школьников решил 5 задач.

Задача № 5.

В классе 41 ученик написал  по три контрольных работы. В результате учитель не поставил ни одной неудовлетворительной отметки, и каждый ученик получил  все остальные отметки. Узнав  об этом, один ученик заметил, что, по крайней  мере, 7 человек получили одинаковые отметки по всем трём контрольным  работам, а другой, подумав, сказал, что таких учеников, наверное, будет 8. Кто из них прав?

Решение.

Разобьём класс на группы в соответствии со всевозможными  наборами отметок. Пусть отметки - это  «клетки», а ученики - «зайцы».

Тогда    3,4,5     3,5,4    4,3,5    4,5,3     5,3,4     5,4,3

6 6     6       6          6            6

Если в каждой группе не больше 6 человек, то всего в классе не больше 36 учащихся, что противоречит условию задачи.

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

Возможен, однако, и случай, когда в каждой группе не больше 7 человек. Например, в одной группе 6, а в остальных - по 7 человек, ведь 41=7-5+6.

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

 

Задача № 6.

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

Решение.

Пусть число матчей, сыгранных командами (0,1,2,3,..., n-2, n-1) «клетки», а команды - «зайцы» (их n).

Заметим, что случай 0 и  n-1 матчей исключают друг друга, так как, если одна команда сыграла n-1 матчей, (то есть все!), то остальные команды сыграли минимум по одному матчу. Итак, имеем n-1 «клеток» (матчей) и n «зайцев» (команд). Очевидно, что две команды, сыгравшие одинаковое количество матчей в любой момент турнира найдутся.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Решения задач с помощью принципа Дирихле

 

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

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

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

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

Рассмотрим решение задач  с геометрическим содержанием ³.

Задача № 7.

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

Решение.

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

 

Задача № 8.

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

Решение.

Разобьем данный квадрат  на 25 квадратиков со стороной 20см

(1м- 1м =20•см•20см•25).

Имеем 25 «клеток» (квадратов) и 51 «зайца» (точку). 51=25•2+1. Ясно, что на основании принципа Дирихле, в какой-то один из квадратиков попадут, по крайней мере, три точки.

 

Задача № 9.

В квадрате АВСО находятся 5 точек. Докажите, что расстояние между какими-то двумя из них не превосходит ¹ /₂ АС.

Решение.

Проведя через центр квадрата прямые (а и Ь), параллельные его сторонам, разрежем его на 4 одинаковых квадрата.