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

Государственное бюджетное общеобразовательное учреждение

средняя общеобразовательная школа №655

Приморского района Санкт-Петербурга

                         Научно-исследовательская конференция

                                           «Открытие»

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

  Математика, информатика, программирование.

                                                                   Балсанов Савва, Верма Ману

                                                                   5в класс

                                                                   Мороз Ю.В., учитель математики.

                                             Санкт-Петербург

                                               2015-2016гг

Содержание

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

1. Биография Дирихле…………………………………………..5
2.  Формулировка принципа Дирихле………………………….6

      3. Задачи на принцип Дирихле………………………………….7

     3.1. Арифметические задачи……………………………………..8

     3.2. Комбинаторные задачи……………………………………...9

    3.3. Геометрические задачи……………………………………...11

    4. Заключение…………………………………………………….12

    5.Литература………………………………………………………13

                                                  Введение.

 «Со времен греков говорить «математика» - значит  говорить                                          доказательство»

                                                                                                                                               Н.Бурбаки.

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

Первую попытку охватить единым трактатом всю математику предпринял древнегреческий математик Евклид в 3 веке до н.э. В результате появились знаменитые «Начала» Евклида. Таким образом, эти два слова –« математика» и «доказательство»- объявляются почти синонимами.

Но что же такое доказательство? Доказательство-это рассуждение, которое убеждает того, кот его воспринял, настолько, что он готов убеждать других с помощью этого рассуждения.

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

В математике большое значение имеют так называемые доказательства существования. Например, чтобы доказать, что уравнение имеет решение достаточно привести какое-то его решение. Доказательства существования такого рода называют прямыми или конструктивными.

Но бывают и косвенные доказательства существования, когда обоснование факта, что искомый объект существует, происходит без прямого указания на сам объект. Одним из способов  косвенно доказать существование является логический прием названный принципом Дирихле – по имени Петера Густава Дирихле, немецкого математика.

Разнообразие логических задач велико, велико и количество способов их решения. В своей работе мы рассмотрели задачи, решаемые с помощью принципа Дирихле.

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

В своем исследовании мы выделила несколько видов логических задач:

а) арифметические; б) комбинаторные. в) геометрические.

Цель: научиться применять принцип Дирихле к решению  задач.

Задачи:

1. Ознакомиться с  биографией Дирихле.

2. Рассмотреть  различные  формулировки принципа Дирихле.

3. Классифицировать  задачи в соответствии с  их содержанием и научиться применять  изученный  принцип к решению  задач.

1.Биография Дирихле.

Ио́ганн Пе́тер Гу́став Лежён-Дирихле́

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

В 12 лет Дирихле начал учиться в гимназии в Бонне, спустя два года — в иезуитской гимназии в Кёльне, где в числе прочих преподавателей его учил Георг Ом.

С 1822 по 1827 г. жил в качестве домашнего учителя в Париже, где вращался в кругу Фурье.

В 1825 г. Дирихле вместе с А. Лежандром доказал великую теорему Ферма для частного случая n=5. В 1827 г. молодой человек по приглашению Александра фон Гумбольдта устраивается на должность приват-доцента университета Бреслау. В 1829 г. он перебирается в Берлин, где проработал непрерывно 26 лет, сначала как доцент, затем с 1831 г. как экстраординарный, а с 1839 г. как ординарный профессор Берлинского университета.

В 1831 г. Дирихле женится на Ребекке Мендельсон-Бартольди, сестре знаменитого композитора Феликса Мендельсон-Бартольди.

В 1855 г. Дирихле становится в качестве преемника Гаусса профессором высшей математики в Гёттингенском университете. В числе его достижений — доказательство сходимости рядов Фурье.      

В комбинаторике принцип Дирихлем (нем. Schubfachprinzip, “принцип ящиков”) — утверждение, сформулированное немецким математиком Дирихле в 1834 году, устанавливающее связь между объектами (“кроликами”) и контейнерами (“клетками”) при выполнении определённых условий. В английском и некоторых других языках утверждение известно как “принцип голубей и ящиков” (англ. Pigeonhole principle), когда объектами являются голуби, а контейнерами — ящики.

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

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

. "Если в n клетках сидит (n+1) или больше зайцев, то найдётся клетка, в которой сидят, по крайней мере, два зайца".

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

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

При решении многих задач используется логический метод рассуждения — "от противного". Этот метод заключается в том, что делается противоположное предположение тому, что нужно доказать. Одна из форм  метода рассуждения «от противного»— принцип Дирихле.

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

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

ФОРМУЛИРОВКА 2. "При любом отображении множества M, содержащего n+1 элементов, во множество N, содержащее n элементов, найдутся два элемента множества M, имеющие один и тот же образ".

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

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

3.Задачи на принцип Дирихле.

 3.1.Арифметические задачи

Пример 1 В классе 26 учеников, из них больше половины мальчики. Докажите, что какие-то 2 мальчика сидят за одной партой, если известно, что парт 13.

Решение:

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

Пример 2

При каком наименьшем кол-ве учеников школы среди них найдутся двое, у которых совпадают день и месяц рождения

  Решение:

1. Если в году 365 дней, то по принципу Дирихле учеников должно быть 366.

2. Если в году 366 дней, то учеников - 367

Пример 3

В Санкт-Петербурге живет более 4 млн. человек. Докажите, что у каких-то двух из них одинаковое кол-во волос (известно , что у чел-ка на голове не более 1 млн. волос)

Решение:

Давайте предположим ,что у всех людей разное кол-во волос на голове, то таких людей будет 1 млн., а по условию задачи их – 4 млн. , по принципу Дирихле найдутся хотя бы два человека с одинаковым кол-вом в

Пример 4

В школе учатся 1200 учеников найдется ли день в который отмечают свои дни рождения не меньше чем 4 ученика

Решение:

1200:366=3(ост.102) к=3,N=365-366 так как 366 кол-во дней в високосном году m>n значит по обобщенному принципу Дирихле найдутся хотя бы 4 ученика у которых дни рождения в один день

3.2.Геометрические задачи.

Пример 1

 В квадрат со стороной 1 метр бросили 51 точку. Докажите, что

         какие-то три из них можно накрыть квадратом со стороной 20 см

Решение:

Разобьем наш квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле, в какой-то из них попадает, по крайней мере, три точки из 51 брошенной

Пример 2

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

Решение:

Можно получить 4 клетки разбив равносторонний треугольник с помощью проведения отрезков соединяющих середину сторон тогда получим 4 равносторонних треугольника со сторонами 0,5 см которые и будут у нас <<клетками>>

• Треугольники - клетки 5 точек - 5 зайцев
• 5>4 по принципу Дирихле найдется равносторонних треугольник со стороной 0,5 см в который попадут не менее двух точек (зайцев

           3.3.Комбинаторные задачи.

Пример 1

В шкафу лежат 5 пар светлых ботинок и 5 пар темных одинаковых размеров и фасонов какое наименьшее кол-во ботинок надо взять наугад из шкафа чтобы среди них была хоть одна пара на правую и левую ногу одинакового цвета

Решение:

Возьмем 10 ботинок может оказаться что среди них 5 светлых на одну ногу и 5 темных тоже на одну ногу в этом случае если взять 11-Й ботинок он с одним из ранее взятых дает пару светлых или темных ботинок

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

Решение. Первый ключ находит свой чемодан в худшем случае за 4 пробы, второй - за 3, третий - за 2, четвертый - за 1, пятый подходит к оставшемуся чемодану. В худшем случае всего будет 10 проб.

                                             Заключение

В ходе работы над исследованием задач мы познакомилась с литературой по этой теме, рассмотрели исторический материал, изучили принцип Дирихле,

подготовили презентацию, научились применять его при решении задач,  выступили перед учащимися 5 классов.

 Применяя данный метод, мы научились:

1.Определить, что удобно в задаче принять за «клетки», а что за «зайцев».

2. Получить «клетки»;  чаще всего «клеток» меньше (больше), чем «зайцев» на одну (или более).

3.Выбрать для решения требуемую формулировку принципа Дирихле.

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

   Многие олимпиадные задачи решаются, используя это специальный метод. Он дает возможность обобщать.

                                               Литература.

1.Генкин С.А., Итенберг И.В., Фомин Д.В., Ленинградские математические кружки, глава 5. Принцип Дирихле

 2.Прасолов В.В., Задачи по планиметрии, глава 21. Принцип Дирихле

3.ВМШ 57 школы, 7 класс, 2001/02, 2. Принцип Дирихле

 4.Кружки МЦНМО, 7 класс, 2004/2005, Занятие 8. Принцип Дирихле

 5.ВМШ 57 школы, 7 класс, 2005/06, 3. Принцип Дирихле

6. Математика. Дополнительные главы 5 класс. Смыкалова Е. В.

Ресурсы.

1. http://logo-rai.ru/index.php/princip-dirihle
2. http://www.mccme.ru/courses/dirihle.html
3. konkurs2011/1433/1/9940_1433
4. http://portfolio.1september.ru/