Научно-исследовательская работа "Принцип Дирихле"

МАОУ «Телембинская средняя общеобразовательная школа»

НПК «Шаг в будущее»

Секция «Математика»

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

Выполнил: Поротников Владимир, ученик 11 класса

Научный руководитель:

Хончинова Надежда Содномовна,

учитель математики

2019 год

Содержание

ВВЕДЕНИЕ…………………………………………………………………………….…........3

ЦЕЛЬ РАБОТЫ……………………………………………………………...............................3

Глава I. ОБЩАЯ ИНФОРМАЦИЯ…………………………………………………...………4

1.1. Биография Дирихле ……………..……………………………………………..…….…...4

1. 2. Принцип Дирихле ……………………………………………………………………......4

1. 3. Обобщенный принцип Дирихле ………………………………..……………………….5

Глава II. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ …………………………….………………….6                                                          2. 1. Принцип Дирихле в теории чисел и при решении логических задач…………….……6                                                                                                                                                       2.2. Принцип Дирихле в комбинаторных задачах и при решение алгебраических задач…8                                                                                                                                    2.3. Принцип Дирихле в моей школе………………………………………………………..…9 Заключение……………………………………………………………………………..............10 СПИСОК ЛИТЕРАТУРЫ……………………………………………………………….…….10 ПРИЛОЖЕНИЕ…………………………………………………………………………..........11

Введение

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

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

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

            Задачи данной работы:

1.      Систематизировать знания по теме принцип Дирихле;              

2.      Отобрать и систематизировать задачи, решаемые с помощью принципа Дирихле;

3.      Применить принцип Дирихле при решении математических задач и доказательств теорем;

4.      Обосновать и наглядно показать практическое значение принципа Дирихле;    

Актуальность данной работы: В данное время  в учебниках, олимпиадных заданиях, ЕГЭ и ОГЭ встречается огромное количество задач, которые привычным методом не решить. В таком случаи на помощь приходит принцип Дирихле. Поэтому, разносторонние исследование данного метода весьма актуально.                                                         Объект исследования: принцип Дирихле;

Методы исследования:

1.Теоретический метод – метод с использованием научной и учебной литературы;

2.Поисковый метод – метод нахождения нужной информации;

3.Метод анализа – обобщение полученных данных и результатов;

Глава I. Общая информация.

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

Дирихле Петер Густав Лежен (13.02.1805 – 05.05.1859) (Приложение №1- Портрет) – немецкий математик. Родился в Дюрене. В 1822-1827гг. был домашним учителем в Париже. Входил в кружок молодых ученых, которые группировались вокруг Ж.Фурье.                                                                                                                                   В 1825 г. Дирихле вместе с А. Лежандром доказал великую теорему Ферма для частного случая n=5. В 1827 занял место доцента в Бреславе; с 1829 работал в Берлине. В 1831-1855гг. – профессор Берлинского университета, после смерти К. Гаусса (1855г.) – Гёттингенского университета.

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

монотонной функций, что послужило обоснованием для многих дальнейших исследований. Значительны труды Дирихле в механике и математической физике, в частности, в теории потенциала. С именем Дирихле связаны задача, интеграл (ввел интеграл с ядром Дирихле), принцип, характер, ряды. Лекции Дирихле имели огромное влияние на выдающихся математиков более позднего времени, в том числе на Г. Римана, Ф. Эйзенштейна, Л. Кронекера, Ю.Дедекинда.

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

Знаете ли вы, что среди зрителей, сидящих в Большом театре во время спектакля, обязательно есть люди, родившиеся в один и тот же день одного и того же месяца? Подсчитаем: в зале большого театра 2000 мест. И даже если не все они заполнены (что в этом знаменитом театре бывает нечасто), можно смело утверждать, что на спектакле собралось более 366 человек. Но 366 - это максимально возможное число дней в году, считая 29 февраля. Итак, для 367-го зрителя просто не остаётся свободной от дней рождений его соседей по залу даты в году.

Просто? Тем не менее это рассуждение даже имеет своё название в математике: принцип Дирихле (в честь немецкого математика Иоганна Петера Густава Лежёна Дирихле). По традиции принцип Дирихле почему-то всегда объясняют на примере кроликов в клетках: если общее число кроликов больше числа клеток, в одной из этих клеток наверняка сидит более одного кролика.

Также этот принцип может выглядеть следующим образом: в n клетках невозможно рассадить поодиночке n+1 кроликов, т.е найдётся клетка, где сидят не менее двух кроликов .

Этот принцип можно сформулировать в терминах отображений между множествами: при отображения множества P, содержащего n+1 элементов, в множество Q, содержащее n элементов, найдутся два элементы множества P, имеющие дин и тот же образ.

Таким образом, чтобы применить принцип Дирихле к решению задач, надо указать, что принимать за "клетки", а что за "кроликов", а также указать способ, которым надо усаживать "кроликов" в "клетки". В терминах отображений между множествами это означает , что надо указать не только множества Р и Q, но и задание отображение между ними.

1.3.Обобщенный принцип Дирихле.

Чаще всего в задачах применяется не Принцип Дирихле, а некоторое его свойство, которое называется обобщённый принцип Дирихле.

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

Обобщение принципа Дирихле: даны n клеток и nk + 1 кроликов размещены в эти клетки. Тогда найдется клетка, где сидят не менее k + 1 кроликов.

Задача 1. В классе учится 29 человек. Саша Иванов допустил в диктанте 13 ошибок, и никто другой не сделала большего числа ошибок. Доказать, что по крайней мере трое учащихся сделали одинаковое число ошибок.

Решение. Примем за "клетки" всевозможные варианты количества ошибок. Их 14, так как школьники могут сделать 0, 1, ..., 13 ошибок. А за "кроликов" примем школьников, которые писали диктант. Их по условию 29. Каждого из них сажаем в клетку, которая соответствует количеству ошибок сделанных им. Тогда получим, что найдётся "клетка", в которой сидят по меньшей мере три "кролика", а это и означает , что найдутся трое школьников, сделавших одинаковое число ошибок.

Задача 2. В пяти классах школы учатся 160 человек. Доказать, что найдутся 4 человека, у которых день рождения приходится на одну и туже неделю.               Решение. В году может быть максимально 53 недели. Их и примем за "клетки" а, за "кроликов" приме ребят. Рассаживаем "кроликов" по тем "клеткам", которые соответствуют их дням рождения. В силу принципа Дирихле найдётся "клетка" по меньшей мере с четырьмя "кроликами", а это и означает, что найдётся неделя, когда день рождения сразу у четырёх человек.                                                                                             При решении задач с использованием принципа Дирихле можно поступать двояко:

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

2) Выбирать, что принять за "клетки" и что взять за "кроликов". Применяя непосредственно принцип Дирихле, устанавливаем существование того, что искали .

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

Задача 3. В ящике лежат 10 пар чёрных и 10 пар красных перчаток одного размера. Сколько перчаток надо вытащить из ящика наугад, чтобы наверняка среди них были:

а) Две перчатки одного цвета;

б) Одна пара перчаток одного цвета;

Решение. а) Если за "клетки" принять цвета перчаток, то, взяв любые три печатки, получится, что в одной из "клеток" находятся два "кролика"- перчатки. А это и требуется.

б) Можно взять 20 перчаток на одну руку и из них нельзя будет выбрать одноцветную пару перчаток, поэтому искомое число не меньше 21. Доказать, что число 21 является искомым.

Примем за "клетки" цвета перчаток (их два). В качестве "кроликов" возьмём перчатки. Согласно обобщённому принципу Дирихле в одной из "клеток" будет не меньше 11 "кроликов". Это означает, что найдётся 11 перчаток одного цвета. Но имеется только 10 пар перчаток одного цвета, поэтому все они не могут быть на одну руку. Значит, среди этих 11 перчаток найдётся одна пара перчаток одного цвета.

Глава II. Практическое применение.

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

Возможна следующая переформулировка принципа Дирихле: "Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток".

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

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

два числа, разность которых делится на 10.

Решение: По крайней мере два числа из 11 дают одинаковый остаток при

делении на 10 (принцип Дирихле). Пусть это будут A = 10a + r и B = 10b + r.

Тогда их разность делится на 10: A - B = 10(a - b).

Задача 2. Из любых трёх целых чисел можно выбрать два, сумма которых чётна. Докажите это.

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

Рассмотрим применение принципа Дирихле при решении логических задач.                       Задача 3. В школе учится 962 ученика. Доказать, что по крайне мере у двух учеников совпадают инициалы.                                                                                        Решение. Заметим, что из двух букв можно создать 2∙2=4 различных пары инициалов. (если это, например, буквы А и Б, то имеем А.А., А.Б., Б.А., Б.Б.)                   В русском алфавите 33 буквы. Т.к. инициалы не могут начинаться с ь и ъ, то существует только 31 буква, которая может входить в состав инициалов. Поэтому можно создать 31∙31=961 различных пар инициалов.                                                                 Возьмем 961 «клетку» и на каждой из них нанесем пару инициалов. Напишем для каждого ученика его инициалы на карточке и каждую карточку положим в ту «клетку», на которой написаны именно эти инициалы. Поскольку раскладываем 962 карточки в 961 «клетку», то, соответственно принципу Дирихле, по крайне мере в одной «клетке» будет не меньше одной карточки. Следовательно, по крайне мере у двух учеников совпадают инициалы. Что и требовалось доказать.                                                                                           Задача 4. В турнире принимают участие 12 шахматистов. Каждые два из них должны сыграть между собой одну партию. Доказать, что в любой момент соревнований есть два шахматиста, которые сыграли одинаковое количество партий.                         Решение. Каждый из 12 шахматистов может сыграть 11 партий.               Рассмотрим два случая.                                                                                                         1) в данный момент есть шахматист, который не сыграл еще ни одной партии;                                2) в данный момент нет шахматиста, который не сыграл еще ни одной партии.  Пронумеруем шахматистов и запишем на карточках для каждого шахматиста число партий, которое он сыграл на данный момент. Получим 12 карточек.                                             В первом случае на каждой карточке будет записано одно из чисел от 0 до 10 (шахматиста, который сыграл все 11 партий нет, т.к. известно, что есть шахматист, который не сыграл еще ни одной партии). Среди 12 карточек, на которых записано одно из11 чисел, есть по крайне мере две одинаковых. Таким образом, в первом случае утверждение задачи справедливо.                                                                                               Во втором случае на каждой карточке будет одно из чисел от 1 до 11, и снова по принципу Дирихле утверждение задачи справедливо.                                                                       Задача 5. В классе 29 учеников. Во время диктанта один ученик допустил 13 ошибок, а все остальные ученики – меньше. Доказать, что в классе найдутся по крайне мере 3 ученика допустивших одинаковое количество ошибок.                                               Решение. Создадим «клетки». На каждой «клетке» напишем число, соответствующее количеству ошибок, допущенных в диктанте. Таких «клеток» будет 14. На каждой из них записано одно из чисел от 0(нет ошибок) до 13.                               Запишем на карточках фамилии учеников (таких карточек будет 29) и будем опускать карточки в «клетки» номер которой соответствует количеству ошибок.                    В «клетку» №14 положим только одну карточку. Остальные 28 карточек надо разложить в 13 клеток.                                                                                                          Поскольку 28 = 13∙2 + 2, значит по крайне мере в одной из «клеток» будет лежать не меньше 3 карточек, то есть что в классе найдутся по крайне мере 3 ученика допустивших одинаковое количество ошибок. Что и требовалось доказать.

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

Рассмотрим принцип Дирихле на решении комбинаторных задач.                                         Задача 1. Докажите, что в любой момент турнира по шашкам (в котором каждый встречается с остальными участниками по одному разу) найдется два игрока, сыгравшие одинаковое число партий.                                                                                                  Решение: Если в турнире k+1 участник, то количество сыгранных партий у каждого спортсмена меняется от 0 до k. Однако, если хотя бы у одного участника не сыграно ни одной партии. То ни у кого не может быть сыграно k партий (т. е. количество групп-k).        Если же хотя бы один сыграл все k партий, то ни у кого не может быть 0. Если k+1 игрока распределять по k группам, то найдется группа, в которой не менее 2 игроков.                   Задача 2. Натуральные числа записаны в произвольном порядке. Для каждого числа найдена сумма с его порядковым номером. Могут ли все суммы оканчиваться разными цифрами?                                                                                                                    Решение: Нет. Докажем, что хотя бы две суммы оканчиваются одинаковой цифрой. Способ 1. В начальной расстановке (все числа записаны по порядку) все суммы – четные. При перестановке двух чисел либо четность сумм не изменится, либо появится две нечетные суммы. Следовательно, в любой расстановке числа Nч четных сумм и Nн нечетных сумм – четны (причем Nч+Nн=10), поэтому одно из чисел Nч, Nн больше 5. А четных и нечетных цифр – по 5.                                                                                                          Способ 2. Сумма всех сумм четна, так как каждое число в нее входит дважды. Пусть все суммы оканчиваются разными цифрами, тогда сумма последних цифр 0+1+…+9=45 – нечетна. Противоречие.                                                                                            Следующие задачи из раздела алгебры:                                                                          Задача 3. Докажите, что среди 25 различных натуральных чисел найдутся хотя бы 2 числа a и b, таких, что число a²-b² делятся на 24.                                                  Решение. Среди данных чисел в соответствии с принципом Дирихле найдутся хотя бы 2 числа, дающие одинаковые остатки при делении на 24, тогда a-b=(24q1+r)-(24q2+r)=24(q1-q2), т. е.(a-b) делится на 24, т. к. a²-b²=(a-b)(a+b), и (a-b) делится на 24(доказано выше), то a²-b² делится на 24.                                                                                  Задача 4. Первый член и разность арифметической прогрессии — натуральные числа. Доказать, что найдётся такой член прогрессии, в записи которого участвует цифра 9.                                                                                                                                   Решение: Предположим, что первый член и разность арифметической прогрессии по абсолютной величине меньше 10^k. Тогда найдётся член прогрессии, у которого (k + 1)-я цифра — любая заданная цифра. В частности, эта цифра может быть девяткой.

2.3.Принцип Дирихле в моей школе.

            В октябре 2018 года я рассказал о принципе Дирихле в старших классах моей школе. Многих эта тема заинтересовала, и было решено провести олимпиаду среди 9-11 классов. В ней приняло участие 16 человек – 5 человек из 9 класса, 6 человек из 10 класса и 5 человек из 11 класса.                                                                                                    Олимпиадные задания были основаны на принципе Дирихле, то есть содержали задачи, которые можно было решить с помощью принципа Дирихле (Приложение № 2). Каждое задание оценивалось в 5 баллов. Максимально возможный бал – 25 баллов.           По итогам олимпиады места распорядились следующим образом:                                    I место – Богдан Александр ученик 11 класса – (21,5 балла)                                                     II место – Хончинов Гончик ученик 10 класса – (17 баллов)                                    III место – Свиридов Иван ученик 11 класса – (15 баллов)                                           Также был проведен анализ выполнения заданий учащимися. Данные представлены в диаграмме (Приложение №3). Результаты олимпиады весьма удовлетворительны. Каждый участник решил хотя бы одну задачу. Это говорит о том, что ребята поняли принцип Дирихле. Знания это метода решения задач пригодится им не только при решении олимпиадных задач, но и при сдаче Единого государственного экзамена.

Заключение.

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

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

1.       Андреев А.А., Горелов Г.Н., Люлев А.И., Савин А.Н. «Принцип Дирихле». Учебное издание. Серия А, 1999,Самара.

2.       Болтянский В. Г. Шесть зайцев в пяти клетках//Квант, – 1997. - №2, – С.17 – 37

3.       Горбачев Н.В. Сборник олимпиадных задач по математике Москва МЦНМО, - 2004

4.       Газета «Математика» № 25-26. Изд. дом. «Первое сентября».

5.       Школьная энциклопедия Математика. Гл. ред. С. М. Никольский. – Москва. Изд. дом «Дрофа», 1997.

6.       Энциклопедический словарь юного математика. Сост. А. П. Савин – Москва. Педагогика – Пресс, 1999.

Приложение.

Приложение №1- Портрет Дирихле Петер Густав Лежен.

Приложение №2 – Задачи олимпиады.

Задача 1. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.

Решение. Всего в году 365 дней. Назовём дни ящиками, а учеников кроликами. Тогда в некотором ящике сидят не меньше 400/366 кроликов, т.е. больше одного. Следовательно, не меньше двух.

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

 Задача 2. На планете Земля океан занимает больше половины площади

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

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

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

Решение. Рассмотрим множество наборов из трёх оценок за соответствующие самостоятельные. Количество таких наборов равно 4³ или 64 (4 возможности за каждую из трёх самостоятельных). Поскольку число учащихся больше 64, по принципу Дирихле каким-то двум учащимся отвечает один набор оценок.           Задача 4. В шкафу лежат вперемешку 5 пар светлых ботинок и 5 пар темных ботинок одинаковых размера и фасона. Какое наименьшее количество ботинок надо взять наугад из шкафа, чтобы среди них была хоть одна пара (на правую и левую ноги) одинакового цвета?                                                                                                        Решение: Возьмем 10 ботинок. Может оказаться, что среди них 5 светлых на одну ногу и 5 темных тоже на одну ногу. В этом случае, если взять 11-й ботинок, он с одним из ранее взятых дает пару светлых или темных ботинок.                                  Задача 5.  Принесли 5 чемоданов и 5 ключей от этих чемоданов, но неизвестно, какой ключ от какого чемодана. Сколько проб придется сделать в самом худшем случае, чтобы подобрать к каждому чемодану свой ключ?                                         Решение: Первый ключ находит свой чемодан в худшем случае за 4 пробы, второй за 3, третий за 2, четвертый за 1, пятый подходит к оставшемуся чемодану. В худшем случае всего будет 10 проб.

Приложение №3 – Диаграмма результатов выполнения заданий учащимися.