Тема: Принцип Дирихле и его применение в решении задач на доказательство. Шаравии Бимбажап Алексеевич, 10 класс. Россия, Республика Тыва, г.Кызыл, МБОУ. - презентация

1 Тема: Принцип Дирихле и его применение в решении задач на доказательство. Шаравии Бимбажап Алексеевич, 10 класс. Россия, Республика Тыва, г.Кызыл, МБОУ СОШ 12. Руководитель: Донгак Шончалай Хажыт-ооловна – учитель математики МБОУ СОШ 12.

2 Цель работы: Рассмотреть задачи на доказательство, решаемые с помощью принципа Дирихле. Задачи исследования: 1. Изучить литературные источники о жизни П.Г.Л. Дирихле. 2. Познакомиться с принципом Дирихле для решения задач на доказательство. 3. Выяснить, где еще применяют этот принцип Дирихле. 4. Научиться решать задачи по принципу Дирихле.

3 1. Введение. Принцип Дирихле - это утверждение, согласно которому в любой совокупности из «N» множеств, содержащих более «n» элементов, есть хотя бы одно множество содержащее не менее двух элементов.

4 Биография ученого Дирихле Петер Густав Лежен (с учетом этимологии правильнее Дирищле) родился 13 февраля 1805 года в вестфальском г.Дюрине. В 12 лет начал учиться в гимназии в Боне, в 14 лет в Кёльне,(учителем был Георг Ом). В 1827 году -доцент в Бреславе. В 1829 году-работал в Берлине. В годах - профессор Берлинского университета, а после - Гёттингенского университета. В 1831 г. Дирихле женится на Ребекке Мендельсон Бартольди, сестре знаменитого композитора Феликса Мендельсон-Бартольди. Дирихле умер 5 мая 1859 года в Геттингенсе.

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

6 2. Принцип Дирихле. Общая формулировка: «Если n кроликов сидят в k ящиках, то найдется ящик, в котором сидят не меньше чем n/k кроликов, и найдется ящик, в котором сидят не больше чем n/k кроликов». Самая популярная формулировка принципа Дирихле звучит так: ФОРМУЛИРОВКА 1. "Если в n клетках сидит n+1 или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца". Заметим, что в роли зайцев могут выступать различные предметы и математические объекты - числа, отрезки, места в таблице и т. д.

7

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

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

10 Конечно, задача 1, как мы убедились, очевидна, и легко может быть решена без помощи принципа Дирихле. Поэтому, естественно, возникает вопрос: "Для чего тогда нужен принцип Дирихле?" В дальнейшем мы увидим, что некоторые задачи не так очевидны при непосредственном решении, но в то же время достаточно просто решаются при помощи принципа Дирихле. Простота решения в значительной степени зависит от того, насколько удачно будут выбраны «клетки" и «кролики". То есть, при использовании принципа Дирихле необходимо указать, что будет «клеткой", а что - «кроликом".

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

12 Доказательство: Используя принцип Дирихле, мы должны распределить данные из задачи на «кроликов и клеток», тогда мы увидим, что у нас больше «кроликов» или «клеток». Итак, на голове может быть 0, 1, …, волос - всего вариант. Каждого москвича отнесем к одной из групп в зависимости от количества волос; если 34 москвича с одинаковым количеством волос не найдутся, то это значит, что в любую из созданных групп входит не более 33 человек; тогда всего в Москве живёт не более 33* = < человек по условию. Значит, такие 34 москвича найдутся.

13 ФОРМУЛИРОВКА 3. "Если nk+1 зайцев размещены в n клетках, то найдутся k+1 зайцев, которые посажены в одну клетку (n, k - натуральные числа)".

14 Пример 3. В классе 25 человек. Известно, что среди любых трёх из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.

15 Решение: Выберем любых двух учеников класса, которые не дружат между собой. (Если таких нет, то все ученики класса дружат между собой, значит, у каждого имеется 24 друга, и задача решена.) Из оставшихся 23 учеников каждый дружит с одним из этих двух, иначе мы имели бы тройку учеников, среди которых не было бы друзей. Тогда у одного из выбранных двух учеников не менее 12 друзей. (23 "зайца" рассажены в двух "клетках".)

16 3. Практическая часть. Рассмотрим некоторые задачи, которых составил и решил сам. Задача 1. В классе 20 человек. Учитель составляет 17 ячеек, где располагаются фамилии учеников класса. Известно, что в двух ячейках находятся одинаковые фамилии и они не более 3. Доказать, что существуют хотя бы 2 различных совпадающих фамилий.

17 Доказательство: Здесь «кролики» - ученики класса, «клетки» - число ячеек, в которые помещаются фамилии учеников. Получается, есть 17 клеток для 20 зайцев, так как имеется 2 одинаковых фамилий. В клетку «1» впишем фамилию одного ученика класса, в клетку «2» другого, и так до «17-го». Теперь применим «принцип Дирихле». Оставшиеся три зайца должны войти в 2 различные ячейки, т.к. в некоторую ячейку входят не более трех однофамильцев. Получается в 17 клеток из 20 кроликов, трое обязательно должны поместиться в некоторую клетку, и двое должны поместиться в другую клетку. Докажем утверждение задачи от противного. Предположим, что никаких 3 и 2 учеников не имеют одинаковых фамилий, т. е. в каждую из «клеток» 1, 2, 3, …,17 попало меньше по 2 и 3 одинаковых фамилий. Тогда в каждой из них есть по 1 человеку или отсутствует, значит всего в этих клетках 1*17=17 (учеников). Противоречие.

18 Использованная литература: et.html et.html Андреев А.А., Горелов Г.Н., Люлев А.И., Савин А.И. "Принцип Дирихле", Самара "Пифагор", 1997 г.

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