<><><>
КОНКУРСЫ
I Взмахом пера [1]
II Взмахом пера [1]
III Взмахом пера [0]
I Интересно знать [0]
II Интересно знать [0]
Мастер-класс [3]
Лучший сценарий [3]
Лучший конспект [1]
Внимание! Проект! [1]
Проект на пять [9]
Будущий ученый [4]
Скоро, скоро Новый год! [10]
23 февраля! [1]
КОПИЛКА ЖУРНАЛА

красивые награды:)
Главная » Файлы » Всероссийские конкурсы 2018-2019 уч.года » Будущий ученый

Принцип Дирихле и применение его в решении задач
03.02.2019, 15:12

Федотова Юлия, ученица 8 А классаМБОУ «Лицей №1 Брянского района» д. Добрунь Брянской области, 14 лет

Номинация: «Исследование»
Куратор: Соловьёва Наталья Александровна

Исследовательская работа

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

Введение

В прошлом году я  была в Сочи в ОЦ «Сириус». Там мы учились решать олимпиадные задачи. Я с детства любила решать  различные  логические задачи. И   для  их решения у меня всегда были свои методы . Эти же методы и помогли мне решить задачи, которые были в отборочном туре на поездку в Сириус . В Сириусе я узнала  о принципе Дирихле . По началу мне было  не легко  научиться применять  этот метод . Практически все дети , которые были  в Сириусе  уже были знакомы  с ним и с помощью его решали  задачи .  Они изучали этот метод решения задач    на дополнительных занятиях  по математике в своих школах. Поэтому учителя  Сириуса не  стали   много времени уделять на объяснение. Практически  сразу раздали задачи и сказали: решайте . Некоторые задачи я решила своим способом , но    у детей , которые решали задачи с помощью принципа Дирихле получалось решать гораздо быстрее и это побудило меня самостоятельно заняться изучением этого принципа .

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

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

Объект исследования - принцип Дирихле.

Предмет исследования - различные формулировки принципа Дирихле и их применение при решении задач.

Цель работы - научиться применять принцип Дирихле к решению олимпиадных задач.

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

1. Изучить литературу по данной теме;

2. Научиться решать задачи на принцип Дирихле;

3. Рассмотреть различные формулировки принципа Дирихле.

4. Классифицировать задачи в соответствии с их содержанием и научиться применять изученный принцип к решению задач.

5. Попробовать создать свои задачи на принцип Дирихле

6. Сделать   буклет « Принцип Дирихле и его применение в решении задач»

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

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

Дирихле родился в вестфальском городе Дюрене в семье почтмейстера.

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

С 1822 по 1827 г. жил в качестве домашнего учителя в Париже, где вращался в кругу Фурье.

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

В 1831 г. Дирихле женится на Ребекке Мендельсон-Бартольди, сестре знаменитого композитора Феликса Мендельсон-Бартольди.

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

В 1855 г. Дирихле становится в качестве преемника Гаусса профессором высшей математики в Гёттингенском университете. В числе его достижений — доказательство сходимости рядов Фурье.      

В теории чисел доказал теорему о прогрессии: последовательность  {a + nb}, где a, b — взаимно простые целые числа, содержит бесконечно много простых чисел.

Принцип Дерихле и его формулировки

Принцип Дирихле утверждает, что если множество из M элементов разбито на N непересекающихся частей, не имеющих общих элементов, где M > N, то по крайней мере в одной части будет более одного элемента.

В комбинаторике принцип Дирихле́ («принцип ящиков») - утверждение, устанавливающее связь между объектами («зайцами») и контейнерами («клетками») при выполнении определённых условий. В английском и некоторых других языках утверждение известно как «принцип голубей и ящиков», когда объектами являются голуби, а контейнерами - ящики.

Формулировки принципа Дирихле

 «Если в n клетках сидят n + 1 "кроликов", то есть клетка, в которой не менее 2-х «кроликов»

Например. Если в 4(или n) клетках сидит 5 (или n+1) зайцев, то хотя бы в одной клетке находится более одного зайца (2 зайца).

         

«Если в n клетках сидят не более n-1 "кроликов", то есть пустая клетка»

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

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

“Если в n клеток посадить kn+1 зайцев, то найдется хотя бы одна клетка, в которой находятся не менее чем k+1 заяц”.

"Если в n клетках сидят не более nk-1 "зайцев", то в какой-то из клеток сидят не более k-1 "зайцев ".

Докажем обобщенный принцип Дирихле. Используем доказательство от противного. Предположим, что не найдется такой клетки. Значит, в каждой клетке находится не более чем k зайцев. Тогда в n клетках не более чем kn зайцев. Но по условию у нас было kn+1 зайцев. Получилось противоречие, значит наше предположение неверно. Следовательно, найдется хотя бы одна клетка, в которой находятся не менее чем k+1 заяц.

Возможна следующая переформулировка принципа Дирихле:

"Среди n + 1 целых чисел найдутся два числа, дающие при делении на n один и тот же остаток".

Доказательство. Пусть заданные n + 1 чисел выступят в качестве кроликов, а остатки при делении этих чисел на n в качестве клеток. Всего может получиться n различных остатков: 0, 1, …, n – 1 (клеток), поэтому, хотя бы два числа будут иметь одинаковые остатки.

"Среди любых n + 1 целых чисел найдутся два числа таких, что их разность делится на n"

Доказательство. Применяя первую формулировку, по крайней мере, два числа из n + 1 дают одинаковый остаток при делении на n.

Пусть это будут c = n·a + r и d = n·b + r.

Тогда их разность делится на n: c – d = n(a – b).

Существует  еще одна формулировка принципа Дирихле, которая  применяется  к фигурам:

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

А для площадей применяют следующую формулировку:

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

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

Порядок ( алгоритм ) применения принципа Дирихле

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 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.

Решение: 

25 ящиков -«кроликов» рассадим по 3 «клеткам»-сортам.

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

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

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

Задача: В классе 35 учеников. Докажите, что среди них найдутся два ученика, фамилии которых начинаются с одной и той же буквы.

Решение. В русском алфавите 33 буквы. Учеников в классе – 35. Примем буквы алфавита за “клетки”, а учеников – за “зайцев”, то по принципу Дирихле найдутся хотя бы два ученика, чьи фамилии начинаются в одной и той же буквы.

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

Решение. В году может быть максимум 366 дней, то по принципу Дирихле учеников может быть максимум n+1, то есть 366+1=367 учеников.

Задача. Сто человек сидят за круглым столом, причем более половины из них – мужчины. Докажите, что найдутся два мужчины, сидящие друг напротив друга.

Решение. Число пар, сидящих друг напротив друга равно 50. Так как мужчин как минимум n+1, то есть 50+1, то по принципу Дирихле найдется хотя бы одна пара мужчин, сидящих друг напротив друга.

Задача. На экзамене  10 школьников решили в сумме 35 задач, причем среди них были решившие ровно 1 задачу, ровно 2 задачи и ровно 3. Доказать, что кто-то из них решил не менее пяти задач.

Решение. Т.к. трое школьников в сумме решили 6 задач (1+2+3=6), то останется еще 7 школьников, решивших в сумме 29 задач. Задачи – это «зайцы», «клетки» -ученики 29:7=4(ост1), 29=7 * 4 + 1.В каждую «клетку» (ученику) мы можем посадить 4 «зайца» (задачи) и ещё одна останется. Значит её решил один из учеников, т.е. один ученик решил 5 задач.

Принцип Дирихле в теории чисел

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

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

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

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

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

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

Решение.

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

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

Решение.

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

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

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

Задача. Доказать, что среди n целых чисел можно выбрать несколько чисел (может быть, одно), сумма которых делится на n. [3]

Решение. Рассмотрим n следующих сумм:

S1 = x1, S2 = x1 + x2, ..., Sn = x1 + x2 + x3 + ... + xn. Если какая-то одна из этих сумм делится на n, то берём её.

Пусть ни одно n из чисел S1, S2, ... , Sn (зайцев) не делится на n. Тогда при делении этих сумм на n может быть n – 1 остатков (клеток): 1,…, n – 1. То два из них при делении на n обязательно дадут равные остатки (по доказанному выше). Пусть это Sk и Sm (k m), тогда разность Sm – Sk = (x1 +. . .+ xm) – (x1 +. . .+ xk) = xk + 1+. . .+ xm делится на n, и поэтому сумма xk + 1+. . .+ xm является искомой.

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

Задача. Какое наибольшее число королей можно расставить на шахматной доске так, чтобы они не били друг друга?

Решение. Начнем с того, что на шахматной доске 64 клетки. Король может ходить в любую сторону, но только на одну клетку. Всего на шахматной доске можно расположить 16 королей так, как показано на рисунке 1. Теперь докажем, почему 16 – это максимальное число королей, которые мы можем расположить на шахматной доске. Тут мы воспользуемся методом “от противного”. Предположим, что мы можем разместить на доске 17 королей, разбив доску на 16 равных квадратов, как показано на рисунке 2. Давайте примем эти квадраты за “ящики”, а королей – за “зайцев”, то по принципу Дирихле хотя бы в одном “ящике” будет больше одного короля, то есть на одной клетке располагаются 2 короля, а такое невозможно, то на шахматной доске можно разместить не больше 16 королей.

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

Задача. Восемь футбольных команд провели турнир (каждая сыграла с каждой один раз). При этом не было «ничьих». Докажите, что можно выделить такие четыре команды А, В, С, 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.Вот мы и нашли четыре команды, удовлетворяющие условию задачи.

Задача:

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

Решение:

Если  в  турнире k+1  участник,  то  количество  сыгранных  партий  у каждого  спортсмена  меняется  от  0  до k.  Однако,  если  хотя  бы  у  одного

участника не сыграно ни одной партии. То ни у кого не может быть сыграно k партий (т. е. количество групп -k). Если же хотя бы один сыграл все k партий, то ни  у  кого  не  может  быть  0.  Если k+1  игрока  распределять  по k группам,  то найдется группа, в которой не менее 2 игроков.

Задача. В коробке лежат карандаши: 7 красных и 5 синих. В темноте берут карандаши. Сколько карандашей надо взять, чтобы среди них было не менее 2 красных и не менее 3 синих?

Решение. Если предположить, что сначала будут попадаться только красные карандаши, то для того, чтобы было 3 синих, нужно взять 7(красные)+3(синие)=10. Это «худший» вариант развития событий, т.к. красных карандашей больше.

УЧИМСЯ СОСТАВЛЯТЬ ЗАДАЧИ

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

Задача 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. 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
  8. http://lobanovaoe.narod.ru/posle_ur/principdirihle.htm

Приложения:

Приложение № 1

Приложение № 2 (Сборник задач)

Приложение № 3 (буклет)

Категория: Будущий ученый | Добавил: NikElena
Просмотров: 25 | Загрузок: 0 | Рейтинг: 5.0/1
Вход на сайт
Поиск



Календарь



МЫ В СОЦ.СЕТЯХ



Статистика






Свидетельство о регистрации СМИ - Эл № ФС77-59240 от 04.09.14 зарегистрировано Роскомнадзором
Возрастное ограничение: 0+
Контакты: электронная почта - pedagogika-vsem@yandex.ru, тел. 8-977-695-33-67