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

Государственное бюджетное профессиональное образовательное учреждение города Москвы

«Политехнический колледж им. Н.Н. Годовикова»

(ГБПОУ ПК им. Н.Н. Годовикова)

Проектная работа.

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

Работу выполняли

ученики 11 «П» класса:

Владас Барисас

Олег Жалнин

Преподаватель: Шемелина М.А.

Оглавление.

Введение ……………………………………………………………… 3

Математик Петер Густав Лежен  Дирихле ….……………………… 4

Формулировка принципа Дирихле …..……...………………………. 5

Задачи математических олимпиад ………………………………….. 6

Принцип Дирихле в теории чисел …………….……..…………… 7-8

Принцип Дирихле для длин и площадей …………………..…… 9-10

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

Список литературы ………………………………………….……… 12

Введение.

У математиков встречаются весьма странные «принципы». Впрочем, любой здравомыслящий человек, ознакомившись с этими принципами, вынужден их признать. Вот, например, так называемый принцип Дирихле. Мы заинтересовались этим принципом  после осенней олимпиады по математике. Задания были разного типа. Затруднение у нас вызвала задача про Винни Пуха. Она была сформулирована примерно так: «У Винни Пуха было несколько банок меда. В каждой банке не более 1 литра меда. Доказать, что если в день он будет съедать не более 1 банки, то за 5 дней он съест не более 5 литров меда». Ее можно было решить только логическим путем, а точнее только при помощи принципа Дирихле.

Математик Петер Густав Лежен  Дирихле.

Дирихле Петер Густав Лежен (13.02.1805-5.05.1859) - немецкий математик (с учетом этимологии его правильнее было бы называть Диришле). Родился в вестфальском городе Дюрене в семье почтмейстера. Его предки были выходцами из бельгийского городка Ришле (Richelet), этим обусловлено происхождение необычной для немецкого языка фамилии. Часть фамилии «Лежён» имеет аналогичное происхождение - деда называли «молодым человеком из Ришле» (фр. Le Jeune de Richelet). В 12 лет Дирихле начал учиться в гимназии в Бонне, спустя два года - в иезуитской гимназии в Кёльне, где в числе прочих преподавателей его учил Георг Ом.

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

Формулировка принципа Дирихле.

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

Математики очень любят сводить объяснение этого принципа к примеру кроликов в клетках. Поступим также и мы.

«Если в n клетках сидит не менее n+1 кроликов, то хотя бы в одной клетке находится более одного кролика».

Заметим, что в роли зайцев могут выступать различные предметы и математические объекты - числа, отрезки, места в таблице и т. д.

Удивительно, что на основе такого простого и даже чуть наивного принципа математикам удаётся решать весьма трудные задачи, доказывать красивые теоремы, причём не только элементарные.

Задачи математических олимпиад.

Задача №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. В лесу растет миллион елок. Известно, что в лесу на каждой из них не более 600 000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.

Решение. Перед нами миллион «кроликов» (елок) и, увы, всего лишь 600 001 «клетка» (иголка) с номерами от  0 до 600 000. Каждого «кролика» сажаем в клетку с номером, равным количеству иголок на этой елке. Так как «кроликов»гораздо больше, чем «клеток», то в какой-то «клетке» сидят по крайней мере два «кролика», а если «два кролика сидят в одной клетке», то количество иголок у них одинаково.

Задача №4. В магазин привезли 34 ящика с яблоками трех сортов, причем в каждом ящике лежали яблоки какого-то одного сорта. Можно ли найти 12 ящиков с яблоками одного сорта.

Решение. Имеем 3 «клетки» (сорта), 34=3*11+1. В каждую «клетку» мы можем посадить 11 «кроликов» (ящиков) и еще у нас есть один ящик. Значит, в какую-то «клетку» мы посадим еще одного «кролика». Таким образом, можно утверждать, что, по крайней мере, в 12 ящиках находятся яблоки одного сорта.

Принцип Дирихле в теории чисел.

Теорема 1. «Пусть p, q – натуральные числа, p>q. Если обыкновенную дробь p/q обратить в десятичную, то получится либо конечная, либо бесконечная периодическая дробь, причем длина периода не превосходит q-1».

Доказательство. Будем делить p на q «уголком» и следить за остатками. Если на каком-то шаге остаток будет нулевым, то получится конечная дробь. Если же все остатки будут отличны от нуля, то рациональное число p/q запишется в виде бесконечной десятичной дроби. Докажем, что она будет периодической. Каждый раз при нахождении очередной цифры частного будет получаться в остатке одно из чисел 1, 2, …, q-1. Эти возможные значения остатков мы и будем считать «клетками», так что всего имеется q-1 «клеток». «Зайцами» же будут остатки, которые получаются в действительности при выполнении деления. Рассмотрим q «зайцев». Так как их на 1 больше, чем «клеток», то какие-то два «зайца» попадут в одну «клетку». Другими словами, не позже, чем через q-1 шагов начнут повторяться остатки, а вслед за этим – и цифры в частном. Действительно, если на некотором шаге повторился остаток, то, приписав как обычно к нему 0, мы получим то же число, что было прежде, а, значит, снесем в частное ту же самую цифру, что и раньше; поэтому наши действия начнут повторяться. Таким образом, получится периодическая десятичная дробь с периодом длиной не более q-1.

Теорема 2. «Среди p+1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток».

Доказательство. При делении с остатком на p может встретиться конечное число различных остатков: 0, 1, 2, …, p-1. Они то и играют здесь роль «клеток», а сами целые числа являются «зайцами». Так как чисел («зайцев») больше, чем остатков («клеток»), то хотя бы два числа «сидят в одной клетке», то есть имеют одинаковые остатки при делении на p.

Пример №1. Дано 11 различных целых чисел. Доказать, что из них можно выбрать два числа, разность которых делится на 10.

Решение. По крайней мере два числа из 11 дают одинаковый остаток при делении на 10 (принцип Дирихле). Пусть это будут A=10a+r и B=10b+r. Тогда их разность делится на 10. A-B=(10a+r)-(10b+r)=10a+r-10b-r=10(a-b).

Пример №2. Доказать, что если имеется 100 целых чисел х1, х2, …, х100, то из них можно выбрать несколько чисел (может быть, одно), сумма которых делится на 100.

Решение. Рассмотрим 100 следующих сумм:

S1=x1

S2=x1+x2

S3=x1+x2+x3

………………………………

S100=x1+x2+x3+…+x100.

Если хотя бы одна из этих сумм делится на 100, то наша цель достигнута. Допустим, что ни одно из чисел S1, S2, …, S100 не делится на 100. Значит, два из них при делении на 100 дают равные остатки (так как сумм у нас 100, а различных остатков может быть лишь 99). Пусть это Sn и Sm (n

Sm-Sn=(x1+…+xm)-(x1+…+xn)=xn+1+…+xm

делится на 100, и поэтому сумма xn+1+…+xm является искомой.

Принцип Дирихле для длин и площадей.

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

Теорема 2. «Если внутри фигуры площади S находится несколько фигур, имеющих сумму площадей больше S, то хотя бы две из них имеют общую точку».

В ряде задач используется обобщение принципа, а также утверждение, в некотором смысле ему обратное:

Теорема, обратная теореме 1. «Если на отрезке длины L расположено несколько отрезков, сумма длин которых больше L*k, то по крайней мере одна точка покрыта не менее, чем k+1 из этих отрезков».

Теорема, обратная теореме 2. «Если сумма площадей нескольких фигур меньше S, то ими нельзя покрыть фигуру площади S».

Пример №1. В квадрате площадью S расположено 100 фигур, сумма площадей которых больше 99S. Доказать, что у всех этих фигур есть общая точка.

Решение. Пусть S1, S2, …, S100 - площади данных фигур, а Sy1, Sy2, …, Sy100 - площади фигур, дополняющих их до квадрата. Понятно, что Sk+Syk=S. По условию S1+S2+…+S100>99S, поэтому Sy1+Sy2+…+Sy100=(S-S1)+(S-S2)+…+(S-S100)=100S-(S1+S2+…+S100)<100S-99S=S

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

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

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

Пример №3. Грани куба окрашены в 2 цвета. Докажите, что найдутся две соседние одноцветные грани.

Решение. Рассмотрим три грани куба, имеющие общую вершину. Назовем их «кроликами», а данные цвета - «клетками». По принципу Дирихле, найдутся две грани, окрашенные в один цвет. Они и будут соседними.

Пример №4. В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка - точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.

Решение. Весь ковер можно накрыть такими 25-ю заплатами. По принципу Дирихле какая-то из этих заплат накроет не менее трех дырок.

Заключение.

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

Список литературы.

● Дирихле П. Г. Л. О сходимости тригонометрических рядов, служащих для представления в данных пределах произвольной функции. В кн.: Разложение функций в тригонометрические ряды. Харьков, 1914. c. 1–23.

● Дирихле П. Г. Л. Лекции по теории чисел. М.–Л., 1936.

● Андреев А.А., Горелов Г.Н., Люлев А.И., Савин А.И. "Принцип Дирихле", Самара "Пифагор", 1997г

● И. Л. Бабинская. Задачи математических олимпиад. М.: Наука, 1975.

● Д. X. Муштари. Подготовка к математическим олимпиадам: задачи, темы, методы. Казанский ун-т, 1990.

● В. В. Прасолов. Задачи по планиметрии. Ч. 2. М.: Наука, 1991.

● В. Г. Болтянский. Шесть зайцев в пяти клетках. // Ж-л «КВАНТ», 1977,No2.

● А. А. Леман. Сборник задач московских математических олимпиад. Под ред. В.Г. Болтянского. М.: Просвещение, 1965.

● Ю. Ф. Фоминых. Принцип Дирихле. // Ж-л «Математика в школе», 1996, No3.

● Mircea Ganga, Teme si probleme de matematica, Ed. Tehnica, Bucuresti, 1991, 331p.

● V.A.Ufnarovski, Acvariu Matematic, "Stiinta", Chisinau, 1988, 237p.

●В.В.Прасолов, Задачи по планиметрии, ч.2, Москва, Наука, 1991, 139стр.

● И.Л.Бабинская, Задачи математических олимпиад, Москва, Наука, 1975, 112стр.

● V.A.Gusev, A.I.Orlov, A.L.Rozental, Lucrul in afara orelor de curs la matematica in clasele VI-VIII, Chisinau, Lumina, 1980, 293p.