Исследовательская работа " Применение принципа Дирихле в решении задач"

Муниципальное общеобразовательное учреждение

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

«Я – исследователь»

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

«Применение принципа Дирихле в решении задач»

         Выполнила: ученица 7 А класса

                                                         Демина Ангелина                                                                                                            

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

                                                                                    Шель Татьяна Борисовна

                                                     г. Самара, 2021

Содержание:

1.Введение………………………………………………………………2-4

2.Основная часть

Теоретическая часть

Исторические сведения. Биография Дирихле……………………………4-6

Различные формулировки принципа Дирихле…………………………  6-8

3.Практическая часть………………………………………………......8-13

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

Различные задачи

Выводы          4.Заключение………………………………………………………………15-16

5. Используемые источники информации……………………………...16-17

6. Приложения……………………………………………………………..18-19

1.Введение  

 В нашей школе проходила «Неделя математики».  Я стала победителем  в  математической игре среди учащихся  7класса. Мне подарили сборник решения логических задач. Из этого сборника я узнала, что некоторые  задачи решаются с помощью  «принципа Дирихле».  Мне стало  интересно, а кто такой Дирихле? Какой у него принцип решения задач? И  я  поставила себе цель - узнать о создателе  этого принципа, узнать можно ли  с помощью такого принципа решить сложные логические задачи. В нашей жизни встречается большое разнообразие логических задач, много способов их решения. При решении  различных задач мне встретился еще один метод — "от противного".  Задачи такого содержания встречаются и в ЕГЭ. Мне очень хочется научиться их решать и поэтому я решила рассмотреть данную тему на применение принципа Дирихле в решении задач.

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

Цель работы:

• эффективность принципа Дирихле в решении задач.

Задачи исследования:

• изучить литературу и собрать информацию о принципе Дирихле;

• найти задачи, решаемые с помощью принципа Дирихле;
• научиться самостоятельно решать задачи  с помощью принципа Дирихле.

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

2.Основная часть

Теоретическая часть

В дополнительной литературе [1],  мне  понравилось высказывание Д. Пойа: «Если вы хотите научиться плавать, то смело входите в воду, а если хотите научиться решать задачи, то решайте их!» Думаю, что это высказывание поможет мне достичь своей цели.

 Исторические сведения. Биография Дирихле

В детской энциклопедии. [4], я узнала о жизни  и деятельности Дирихле.

Дирихле Петер Густав Лежен (13.02.1805 – 05.05.1859)   немецкий математик, родился в вестфальском городе Дюрене в семье почтмейстера.

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

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

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

Я узнала о различных формулировках принципа Дирихле[2]

При решении многих задач используется логический метод рассуждения — "от противного". Такой метод носит название-принцип Дирихле.  Я поняла, что принцип этот это то, что если множество из n элементов разбито на m непересекающихся частей, не имеющих общих элементов, где n > m то, по крайней мере, в одной части будет более одного элемента.

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

 А это другая формулировка “ принципа Дирихле“: если n + 1 предмет поместить в n мест, то обязательно хотя бы в одном месте окажутся хотя бы два предмета.

Так же есть и в шутливой форме принцип Дирихле: “нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев “.

Я поняла,  что роль кроликов можно заменить различными предметами и математическими объектами - числа, отрезки, места в таблице . Главное для всех нас,  выяснить, что в ней — "клетки", а что — "кролики". Это обычно является самым трудным этапом в доказательстве.

Если nk+1 зайцев размещены в n клетках, то найдутся k+1 зайцев, которые посажены в одну клетку (n, k - натуральные числа).

Общем виде  принцип Дирихле: если бы в каждой клетке сидело не более k зайцев, то во всех клетках было бы не более nk зайцев, что противоречит условию.  Его используют, когда нужно выявить несколько объектов, обладающих каким-либо свойством.

3.Практическая часть

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

Изучая  подробно литературу[1], я выяснила для себя главное-порядок ( алгоритм ) применения принципа Дирихле

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, то хотя бы две из них имеют общую точку".

Меня заинтересовала, задача:

В магазин привезли 25 ящиков с тремя различными сортами яблок. В 1 ящике один сорт яблок. Требуется доказать, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта. [3],

Решение.

25 ящиков – это «кролики» расположим их по 3 «клеткам» - сортам. Так как 25 = 3 ∙ 8 + 1, то применяя обобщенный принцип Дирихле (для N = 3, k = 8) и получим, что в какой-то «клетке» - сорте не менее 9 ящиков.

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

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

 Решение. Перед нами миллион «кроликов» - елок и всего лишь 600001 «клетка» с номерами от 0 до 600000. Каждый «кролик» - елка сажается нами в «клетку» с номером, равным количеству иголок на этой елке. Так как «кроликов» больше, чем «клеток», то в какой-то «клетке» сидит по крайней мере два «кролика» – если бы в каждой сидело не более одного, то всего «кроликов» - елок было бы не более 600001 штук. Но ведь, если два «кролика» - елки сидят в одной «клетке», то количество иголок у них одинаково.

Задача 2. В  нашей школе 536 учеников. Требуется доказать, что хотя бы двое из них родились в один день года.

Решение: 536 > 366.  Действительно, на самом деле, найдутся такие ученики.

3 Задача. Мне стало интересно, в моем классе -29 учеников. Найдётся ли такой месяц в году, в котором отмечают свой день рождения не меньше, чем 3 моих одноклассника?

Оказывается, найдется. Вот решение.

Решение:  В году 12 месяцев. Обозначим их как «клетки», а учеников как «зайцев». Так как 29˃12×2, то по обобщенному принципу Дирихле найдется «клетка», в которой сидят не менее 3 «зайцев» т. е. найдется месяц, в котором дни рождения празднуют не менее 3 учеников.

Различные задачи

Изучая дополнительную литературу[5], я заметила, что  принцип Дирихле применяется  в теории чисел, а теория чисел встречается в задачах ЕГЭ по математике. "Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток". При делении с остатком на p может встретиться конечное число различных остатков: 0, 1, 2, . . . , p-1. Они то и играют здесь роль "клеток", а сами целые числа являются "зайцами". Так как чисел ("зайцев") больше, чем остатков ("клеток"), то хотя бы два числа "сидят в одной клетке", т.е. имеют одинаковые остатки при делении на p.

При изучении литературы [9], [10], я нашла такие задачи.

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

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

 Принцип Дирихле  можно увидеть и в задачах по геометрии. [8]

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

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

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

Решение:  Можно провести 3 отрезка, которые соединяют середины противоположных сторон треугольника. Эти отрезки делят треугольник  на четыре равных треугольника со сторонами 0,5. Представим, что треугольники – это “клетки”, а точки – “зайцы”, то по принципу Дирихле хотя бы две точки окажутся в одном из четырех треугольников. Расстояние между этими двумя точками будет меньше, чем 0,5, так как они не лежат в вершинах маленьких треугольников

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

Решение.

Полуплоскости, на которые прямая l разбивает плоскость треугольника ABC,обозначим через q1 и q2. Полуплоскости q1 и q2 будем считать открытыми, так как они не содержат точек прямой l. Представим, что вершины рассматриваемого треугольника (точки A, B, C) – это "зайцы", а полуплоскости q1 и q2 - "клетки". Каждый "заяц" попадает в какую-нибудь "клетку" так как прямая l не проходит ни через одну из точек A, B, C. Если учесть, что "зайцев" трое, а "клеток" только две, то найдутся два "зайца", попавшие в одну "клетку", то есть, найдутся такие две вершины треугольника ABC, которые принадлежат одной полуплоскости.

Задача 3. В квадрате площадью S расположено 100 фигур, сумма площадей которых больше 99S. Доказать, что у всех этих фигур есть общая точка. Решение. Пусть S1, S2, . . . , S100 - площади данных фигур, а , …, - площади фигур, дополняющих их до квадрата. Понятно, что . По условию S1+S2+. . .+S100 > 99S, поэтому

+ + … + = (S- S1)+ (S- S2)+. . .+ (S- S100) = 100S-(S1+ S2+. . .+ S100) < 100S-99S = S.

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

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

Задача 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 – нечетна. Противоречие.

Задача. Восемь футбольных команд провели турнир (каждая сыграла с каждой один раз). При этом не было «ничьих». Докажите, что можно выделить такие четыре команды А, В, С, D, что А выиграла у В, С и D; В выиграла у С и D; С выиграла у D.

Решение. Так как по условию в турнире участвовали 8 команд, каждая из них сыграла с каждой по одному разу, и не было “ничьих”, то всего было произведено …матчей, каждый из которых заканчивались победой какой-либо команды. Распределим все 28 побед между 8 командами, приняв победы за “кроликов”, а 8 команд – за “ящики”, то по принципу Дирихле найдется хотя бы одна команда A, у которой не меньше n+1=3+1=4 побед. Эти четыре команды провели между собой 6 матчей, то было 6 побед. И снова, воспользовавшись “принципом ящиков и кроликов” примем 4 команды за “ящики”, а 6 побед – за “кроликов”, то по принципу Дирихле найдется такая команда B, одержавшая не менее 2-ух побед над командами C и D. Теперь предположим, что в матче между командами C и Dпобедили команда C, то получим: A победила B, C и D. B победила C и D. И C победила D.Вот мы и нашли четыре команды, удовлетворяющие условию задачи.

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

Задача 1

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

Решение.

Возьмем 21 карточку и на каждой из них напишем двухэтажный дом. Еще на 22 карточках напишем – розовый цвет, и на 18 – красная крыша. Всего у нас окажется 21 + 22 + 18 = 61карточка.

Пронумеруем дома от 1 до 30 и будем раскладывать карточки.

Так как 61 = 30∙2 + 1, значит по крайне мере на одном доме будет три карточки. Следовательно, на улице обязательно найдется двухэтажный дом розового цвета с красной крышей.

Задача 2.

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

Решение.

Команда каждого класса должна 5 игр.

Рассмотрим два случая.

1) есть команда, которая еще не участвовала в соревнованиях;

2) каждая команда сыграла хотя бы одну игру.

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

В первом случае это числа от 0 до 4 (всего 5 чисел); во втором случае это числа от 1 до 5 (тоже всего 5 чисел).

Так как карточек 6, а чисел 5. То хотя бы на двух карточках будут написаны одинаковые числа. Значит, в любой момент соревнований есть два класса, которые сыграли одинаковое количество игр.

Задача 4.

В нашем школьном дворе размером 8м×10м в произвольном порядке посадили 19 деревьев.

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

Решение.

Эту поляну можно разделить на 20 равных квадратов со стороной 2м.

Так как посажено только 19 деревьев, то обязательно найдется квадрат, внутри которого нет ни одного дерева.

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

Задача .

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

Решение. Ковер можно «Разделить» на 10 квадратов со стороной 1м.Так как 21 = 10∙2+1, то найдется квадрат со стороной 1м, в котором мышь прогрызла минимум три дырки. И эту дырку можно залатать одной заплаткой.

Я  своими силами и знаниями постаралась составить «Сборник задач». Их можно решить с помощью принципа Дирихле. А для желающих потренироваться в решении задач на принцип Дирихле. А так же я составила буклет « Принцип Дирихле и его применение в решении различных задач».

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

Заключение

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

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

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

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

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

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

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

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

Я считаю, что проделанная мною работа, дала для меня положительные результаты. Большое количество логических задач можно решить только этим способом. Этот метод необходимо знать и применять его на практике.

Литература

1.Математика, Принцип Дирихле, Выпуск 1, Андреев А.А., Горелов Г.Н., Люлев А.И., Савин А.Н., 1997

2.Бородин А.И., Бугай А.С. Биографический словарь деятелей в области

математики. - Киев, Радяньская школа, 1979

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

4. Большая российская энциклопедия

5. Математика// Первое сентября, 1996, № 7

6. Я познаю мир: Дет. энцикл. Математика.- М.:ООО "Издательство АСТ ЛТД", 1999

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

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

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

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

Интернет-источник

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/
5. http://www.zaba.ru/cgi-bin/tasks.cgi?tour=books.mk1.dirikhle
6. http://www.problems.ru/articles/216.php
7. http://bars-minsk.narod.ru/teachers/dirichle.html