II Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

ПРИНЦИП ДИРИХЛЕ

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Данилов В.А. 1

---

1

Мухаметзянова Г.Р. 1

---

1

Работа в формате PDF

204.4 KB

Автор работы награжден дипломом победителя III степени

Диплом школьникаСвидетельство руководителя

 Введение

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

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

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

Цель работы:

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

• получение знаний о применении и сферах использования принципа Дирихле.

В ходе выполнения работы мной были решены следующие задачи:

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

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

• научиться самостоятельно решать задачи данным методом.

Мной использовались следующие методы исследования:

• теоретические;

• поисковые;

• сравнение;

• анализ.

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

I. Общая информация о принципе Дирихле

Дирихле Петер Густав Лежен (13.02.1805 – 05.05.1859) – немецкий математик. Родился в Дюрене. В 1822-1827гг. был домашним учителем в Париже. Входил в кружок молодых ученых, которые группировались вокруг Ж. Фурье.

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

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

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

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

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

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

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

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

I. 3. Обобщение принципа Дирихле

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

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

Рассмотрим задачу:

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

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

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

II. Применение принципа Дирихле для решения различных задач

II. 1. Принцип Дирихле и арифметика

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

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

Решение: 400 > 366.

Задача 3. В классе 40 учеников. Найдётся ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 ученика этого класса?

Решение: Рассуждаем от противного. Если бы такого месяца не нашлось, то в каждом из 12 месяцев день рождения отмечали бы не более трёх учеников. Значит, всего учеников было бы не более 12 · 36. Но 40 > 36. Противоречие.

II. 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 = 10(a - b).

II. 3. Принцип Дирихле и геометрия

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

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

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

Решение: Можно получить 4 «клетки», разбив равносторонний треугольник с помощью проведения отрезков, соединяющих середину сторон. Тогда получим 4 равносторонних треугольника со сторонами по 0,5 см, которые и будут у нас «клетками».

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

+ + … + = (S- S₁)+ (S- S₂)+. . .+ (S- S₁₀₀) = 100S-(S₁+ S₂+. . .+ S₁₀₀) < 100S-99S = S.

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

II. 4. Принцип Дирихле и комбинаторные задачи

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

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

Заключение

Изучив и систематизировав материал по выбранной мной теме, я сделал следующие выводы:

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

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

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

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

Литература

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

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

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

3. Большая российская энциклопедия - М.,

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

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

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

Понятийный аппарат

Доказательство «от противного» (лат. contradictio in contrarium) в математике — один из самых часто используемых методов доказательства утверждений. Доказательство от противного — вид доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения — антитезиса.

Комбинато́рика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка).

Круги́ Э́йлера — геометрическая схема, с помощью которой можно изобразить отношения между подмножествами, для наглядного представления. Изобретены Леонардом Эйлером. Используется в математике, логике, менеджменте и других прикладных направлениях.

Нечётное число — целое число, которое не делится на 2 без остатка: …−3,−1,1,3,5,7,9…

Отображе́ние или фу́нкция ( лат. functio — «исполнение, осуществление») — одно из основных понятий математики, выражающее зависимость одной величины от другой.

Теорема Ферма, - утверждение, что для любого натурального числа n > 2 уравнение xn + yn = zn (уравнение Ферма) не имеет решений в целых ненулевых числах x, y, z. Теорема была сформулирована Пьером Ферма примерно в 1630 году на полях книги Диофанта "Арифметика"

Теория чисел, или высшая арифметика — раздел чистой математики, изучающий свойства натуральных и целых чисел.

Чётное число — целое число, которое делится на 2 без остатка: …−4,−2,0,2,4,6,8,10...