XVII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Принцип Дирихле в Астраханской области
Автор работы награжден дипломом победителя I степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Исследовательская работа
Принцип Дирихле и применение его в решении задач
Актуальность работы. Принцип Дирихле не рассматривается в учебниках математики, поэтому знакомство с новыми методами расширяет для обучающихся круг решаемых задач, учит мыслить, развивает сообразительность, полученные знания пригодятся для сдачи экзаменов и решении олимпиадных и практических задач в жизни.
Гипотеза. Применение соответствующих формулировок принципа Дирихле – наиболее рациональный подход при решении задач олимпиадного уровня.
Объект исследования - принцип Дирихле.
Предмет исследования - различные формулировки принципа Дирихле и их применение при решении задач.
Цель работы - научиться применять принцип Дирихле к решению олимпиадных задач.
Задачи работы:
1. Изучить литературу по данной теме;
2. Рассмотреть различные формулировки принципа Дирихле.
3. Классифицировать задачи в соответствии с их содержанием и научиться применять изученный принцип к решению задач.
4. Научиться решать задачи на принцип Дирихле;
5. Попробовать создать свои задачи на принцип Дирихле на тему «Астраханская область»
6. Сделать буклет «Принцип Дирихле и его применение в решении задач»
Введение
Дирихле Петер Густав Лежен немецкий математик. Родился 13.02.1805г в вестфальском городе Дюрене в семье почтмейстера.
В 12 лет Дирихле учился в гимназии в Бонне, через два года — в иезуитской гимназии в Кёльне, где в числе прочих преподавателей его учил немецкий физик Георг Ом.
С 1822 по 1827 г. жил в качестве домашнего учителя в Париже, где вращался в кругу Фурье.
В 1825 г. Дирихле вместе с А. Лежандром доказал великую теорему Ферма для частного случая n=5. В 1827 г. молодой человек по приглашению Александра фон Гумбольдта устраивается на должность приват-доцента университета Бреслау. В 1829 г. он перебирается в Берлин, где проработал непрерывно 26 лет, сначала как доцент, затем с 1831 г. как экстраординарный, а с 1839 г. как ординарный профессор Берлинского университета.
В 1831 г. Дирихле женится на Ребекке Мендельсон-Бартольди, сестре знаменитого композитора Феликса Мендельсон-Бартольди.
Дирихле принадлежит ряд крупных открытий в самых разных областях математики, а также в механике и математической физике.
В 1855 г. Дирихле становится в качестве преемника Гаусса профессором высшей математики в Гёттингенском университете. В числе его достижений — доказательство сходимости рядов Фурье.
В теории чисел доказал теорему о прогрессии: последовательность {a + nb}, где a, b — взаимно простые целые числа содержит бесконечно много простых чисел.
Принцип Дирихле и его формулировки
Принцип Дирихле утверждает, что если множество из M элементов разбито на N непересекающихся частей, не имеющих общих элементов, где M > N, то по крайней мере в одной части будет более одного элемента.
В комбинаторике принцип Дирихле́ («принцип ящиков») - утверждение, устанавливающее связь между объектами («зайцами») и контейнерами («клетками») при выполнении определённых условий. В английском и некоторых других языках утверждение известно как «принцип голубей и ящиков», когда объектами являются голуби, а контейнерами - ящики.
Применение принципа Дирихле для решения различных задач
Порядок ( алгоритм ) применения принципа Дирихле
1.Определить, что в задаче является "клетками", а что-"зайцами".
2.Применить соответствующую формулировку принципа Дирихле:
Если в n клетках сидят не более (n-1) "зайцев", то есть пустая "клетка".
Если в n клетках сидят (n+1) «зайцев", то есть клетка, в которой не менее 2-х "зайцев".
Если в n клетках сидят не более (nk-1) "зайцев", то в какой-то из клеток сидят не более (k-1) "зайцев".
Если в n клетках сидят не менее (nk+1) "зайцев", то в какой-то из клеток сидят не менее k+1 "зайцев".
Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток
"Среди любых n + 1 целых чисел найдутся два числа таких, что их разность делится на n"
"Если на отрезке длины L расположено несколько отрезков с суммой длин больше L, то хотя бы два из них имеют общую точку".
"Если внутри фигуры площади S находится несколько фигур, имеющих сумму площадей больше S, то хотя бы две из них имеют общую точку".
Разберемся на примере:
Пример 1. В хвойном лесу растут 800000 елей. На каждой ели - не более 500000 иголок. Доказать, что существуют хотя бы две ели с одинаковым числом иголок.
Решение. Предположим противное, то есть, предположим, что в этом лесу не существуют две ели с одинаковым числом иголок. Тогда существует не более одной ели (одна ель или ни одной), имеющей одну иголку. Аналогичным образом, существует не более одной ели с двумя иголками и т.д., не более одной ели с 499999 иголками, не более одной ели с 500000 иголками. Таким образом, не более 500000 елей обладают числом иголок от 1 до 500000. Поскольку всего растут 800000 елей, и каждая ель имеет не долее 500000 иголок, следует, что найдутся хотя бы две ели с одинаковым числом иголок.
Замечание. Легко заметить, что решение в сути не зависит от конкретных чисел 800000 (количество елей) и 500000 (наибольшее число иголок). Принципиально был использован тот факт, что число 800000 строго больше 500000. В доказательстве предполагалось, что нет ни одной ели без иголок, хотя задача и доказательство справедливы и в этом случае.
Теперь сформулируем принцип Дирихле.
Пусть в n коробок помещены k предметов. Если количество предметов больше количества коробок (k > n), тогда существует хотя бы одна коробка, в которой бы находилось 2 предмета.
Примечание. Отметим, что не важно, в какой именно коробке находятся по крайней мере два предмета. Также не имеет значение, сколько предметов в этой коробке, и сколько всего таких коробок. Важно то, что существует хотя бы одна коробка с не менее чем двумя предметами (два или более).
В литературе этот принцип также встречается под названиями: "принцип кроликов и клеток", "принцип ящиков и объектов".
Вернемся к примеру 1. Решим эту задачу, используя принцип Дирихле. Пусть имеются 500000 коробок, соответственно пронумерованных 1,2,3,...,500000. Помещаем (мысленно) в эти коробки 800000 елей следующим образом: в ящик с номером s помещаем ели, на которых ровно s иголок. Поскольку елей, то есть "предметов", больше, чем коробок, следует, что по крайней мере одна коробка будет содержать не менее двух предметов, то есть, не менее двух елей. Так как в одной и той же коробке находятся ели с одинаковым числом иголок, приходим к выводу, что существуют хотя бы две ели с одинаковым числом иголок.
Конечно, задача 1, как мы убедились, очевидна, и легко может быть решена без помощи принципа Дирихле. Поэтому, естественно, возникает вопрос: "Для чего тогда нужен принцип Дирихле?" В дальнейшем мы увидим, что некоторые задачи не так очевидны при непосредственном решении, но в то же время достаточно просто решаются при помощи принципа Дирихле. Простота решения в значительной степени зависит от того, насколько удачно будут выбраны "коробки" и "предметы". То есть, при использовании принципа Дирихле необходимо указать, что (кто) будет "коробкой", а что (кто) - "предметом".
В дальнейшем, для закрепления материала, приведем решения ряда задач.
Пример 2. 100 человек сидят за круглым столом, причем более половины из них — мужчины. Докажите, что какие-то двое мужчин сидят друг напротив друга.
Решение
Разобьем всех на 50 пар людей, сидящих друг напротив друга. Тогда мы получаем, что у нас есть 50 пар («клетки»), в которые нужно рассадить не менее 51 мужчины («кролики»). Из принципа Дирихле следует, что в одной из этих пар-«клеток» оба человека — мужчины-«кролики».
Вывод: таким образом, имея принцип Дирихле, мы можем каждый раз не расписывать решение задачи, а лишь ссылаться на Дирихле фразой «согласно с принципом Дирихле».
Пример 3. Дано 11 различных целых чисел. Доказать, что из них можно выбрать два числа, разность которых делится на 10.
Решение. По крайней мере два числа из 11 дают одинаковый остаток при делении на 10 (принцип Дирихле). Пусть это будут A = 10a + r и B = 10b + r. Тогда их разность делится на 10: A -B = 10(a -b).
Задача. Из любых трёх целых чисел можно выбрать два, сумма которых чётна. Докажите это.
Решение. Все числа можно разбить на два класса: чётные и нечётные. Невозможно распределить три числа по двум классам так, чтобы ни в какой класс не попало более одного числа. Значит, среди любых трёх целых чисел найдутся два числа одинаковой чётности. Их сумма чётна.
УЧИМСЯ СОСТАВЛЯТЬ ЗАДАЧИ
Изучив классические задачи, которые решаются с помощью принципа Дирихле, я решил попробовать самостоятельно составить несколько подобных задач.
Задача №1. В дельте Волги 25 рыбных хозяйств с тремя разными видами рыб (в каждом хозяйстве рыбы только одного вида). Докажите, что среди них есть по крайней мере 9 хозяйств с рыбами одного и того же вида.
Решение:
25 хозяйств -«кроликов» рассадим по 3 «клеткам»-видам.
Так как 25 = 3 ∙ 8 + 1, то применим утверждение (Если в n клеток посадить kn+1 зайцев, то найдется хотя бы одна клетка, в которой находятся не менее чем k+1 заяц для N= 3, k= 8) и получим, что в какой-то «клетке» - виде не менее 9 хозяйств.
Задача №2 В новом микрорайоне Астрахани было построено 30 новых домов. 21 из них были трехэтажные, 22 выкрашены в персиковый цвет, у 18 домов крыша красного цвета. Докажите, что на улице обязательно найдется двухэтажный дом персикового цвета с красной крышей.
Решение.
Возьмем 21 карточку и на каждой из них напишем двухэтажный дом. Еще на 22 карточках напишем – персиковый цвет, и на 18 – красная крыша. Всего у нас окажется 21 + 22 + 18 = 61карточка.
Пронумеруем дома от 1 до 30 и будем раскладывать карточки.
Так как 61 = 30∙2 + 1, значит по крайне мере на одном доме будет три карточки. Следовательно, на улице обязательно найдется двухэтажный дом персикового цвета с красной крышей.
Задача №3. В 500 ящиках лежат помидоры. Известно, что в каждом ящике находятся не более 240 томатов. Доказать, что существуют хотя бы 3 ящика, которые содержат одинаковое количество помидор.
Решение. Пусть в первых 240 ящиках находится различное количество томатов (1,2,...,240) , в следующих 240 ящиках - аналогично (то есть, анализируется экстремальный случай; более подробно об этом методе рассказывается в теме "принцип крайнего"). Таким образом, остались 500 - 2·240 = 20 ящиков, в которые необходимо поместить помидоры от 1 до 240.
Задача №4. Всем известно, что Астрахань – Каспийская столица. В международном форуме Прикаспийских государств участвуют 17 человек. Каждый знает не более трех языков и любые два участника могут общаться между собой. Доказать, что хотя бы три участника, знают один и тот же язык.
Решение. Пусть A - один из участников. Он может общаться с каждым из 16 участников на не более одном из трех известных ему языков. Тогда существует язык, на который A говорит с не менее чем шестью участниками. Пусть B - любой из них. Ясно, что среди остальных 5 участников есть 3, с которыми B может общаться на одном языке (назовем его "второй язык"). Если среди этих троих участников хотя бы два, скажем C и D, могут говорить на "втором языке", то B, C и D и есть те три человека, говорящие на одном языке.
Задача №5. Среди учащихся трёх седьмых и трёх восьмых классов Астраханской гимназии проводились соревнования по гандболу. Каждые два класса должны были сыграть между собой одну игру. Доказать, что в любой момент соревнований есть два класса, которые сыграли одинаковое количество игр.
Решение.
Команда каждого класса должна 5 игр.
Рассмотрим два случая.
1) в данный момент есть команда, которая еще не участвовала в соревнованиях;
2) в данный момент каждая команда сыграла хотя бы одну игру.
Возьмем 6 карточек (по количеству команд) и напишем на каждой из них число сыгранных игр.
В первом случае это будут числа от 0 до 4 (всего 5 чисел); во втором случае это будут числа от 1 до 5 (тоже всего 5 чисел).
Так как карточек 6, а чисел 5. То хотя бы на двух карточках будут написаны одинаковые числа. Значит в любой момент соревнований есть два класса, которые сыграли одинаковое количество игр.
Заключение
Изучив литературу по теме принцип Дирихле, проанализировав виды и типы задач, которые решаются с использованием данного принципа, я сделал следующие выводы:
Принцип Дирихле важен и полезен, этот принцип является мощным логическим методом, с помощью которого решаются не только арифметические задачи, но и задачи с геометрическим содержанием, комбинаторные задачи. Его можно применять в повседневной жизни, что развивает логическое мышление.
Многие олимпиадные задачи решаются с помощью этого специального метода, поэтому его целесообразно изучать самостоятельно или во внеурочной деятельности.
Несмотря на совершенную очевидность этого принципа, его применение является весьма эффективным методом решения задач, дающим во многих случаях наиболее простое и изящное решение.
Самым интересным и сложным было находить, казалось бы, в простых задачах "зайцев" и "клетки", т.к. это иногда было совсем не очевидно. Из-за неправильного выбора задачи не решались, а как только определялись "зайцы" и "клетки", принцип Дирихле начинал работать.
Гипотеза, высказанная в начале работы, полностью подтвердилась. Действительно, принципа Дирихле – наиболее рациональный подход при решении многих задач, особенно олимпиадного уровня.
Я считаю, что проделанная мною работа, дала положительные результаты. Во время моего исследования я познакомился с биографией известного немецкого математика, изучил разнообразие формулировок принципа Дирихле и попробовал свои силы в решении необычных задач. В итоге, гипотеза «принцип Дирихле позволяет решать сложные логические задачи, ответ на которые тяжело найти другим способом» подтверждена. Я считаю, что проделанная мною работа, дала положительные результаты. Больше всего мне понравилось составлять логические задачи самим, основываясь на тематике Астраханского края. Я считаю, что этот метод необходимо знать и применять его на практике. Я собираюсь продолжить мои исследования дальше и найти еще новые способы решения логических задач. Элементы моей работы можно использовать для ознакомления с принципом Дирихле среди одноклассников, при подготовке к олимпиадам, на занятиях математического кружка, к подготовке к экзаменам.
По итогам проекта мною составлен буклет «Принцип Дирихле и применение его в решение задач»
Список используемой литературы:
1) Бородин А.И., Бугай А.С. Биографический словарь деятелей в области математики. - Киев, Радяньская школа, 1979
2) Бабинская И.Л. Задачи математических олимпиад - М., Наука, 1975
3) Большая российская энциклопедия - М.,
4) Математика// Первое сентября, 1996, № 7
5) Я познаю мир: Дет. энцикл. Математика.- М.:ООО "Издательство АСТЛТД", 1999 Интернет - источники:
6) http://www.mccme.ru/courses/dirihle.html.
7) http://ru.wikipedia.org/wiki/ Дирихле_Петер_Густав_Лежён
8) http://ru.wikipedia.org/wiki/Принцип_Дирихле