Занятие кружка. Принцип Дирихле.

ЗАНЯТИЕ КРУЖКА НА  ТЕМУ : «ПРИНЦИП  ДИРИХЛЕ» Учитель математики: Затеева В.П. МБОУ «СОШ  № 15 с углубленным изучением отдельных  предметов»  г.Энгельс Саратовской области

ЦЕЛЬ ЗАНЯТИЯ КРУЖКА:  Познакомить учащихся с новыми  математическим методом решения задач,  которые не рассматриваются в школьном  курсе  Научить решать  задачи с помощью принципа  Дирихле;  Показать его применение для решения  разнообразных задач

ВСТУПИТЕЛЬНОЕ СЛОВО  УЧИТЕЛЯ.   При решении различных олимпиадных  математических        задач применяется  специальный метод, получивший название:  принцип Дирихле  Автором является Петер Густав Лежен  Дирихле   (13.2.1805 ­ 5.5.1859)

ИСТОРИЧЕСКАЯ СПРАВКА Дирихле Петер Август Лежён (1805­1859) —  немецкий математик, иностранный член­ корреспондент Петербургской Академии наук  (1837), член многих других академий.    Дирихле родился в вестфальском  городе Дюрене в семье  почтмейстера.  В 12 лет Дирихле начал учиться в гимназии  в Бонне, спустя два года в иезуитской гимназии в Кёльне, где в  числе прочих преподавателей его учил Георг Ом. С 1822 по 1827  г. жил в качестве домашнего учителя в Париже, где   вращался в кругу Фурье. ­    В 1827г. устраивается на  должность приватдоцента университета Бреслау (Вроцлав).   В 1829 г. он перебирается в Берлин,  где проработал  непрерывно 26 лет,  сначала как доцент.  Затем с 1831 г. Как  экстраординарный профессор. С 1839 г. как ординарный  профессор Берлинского университета. В 1855 г. Дирихле  становится  качестве преемника Гаусса профессором  высшей математики в  Гёттингенском университете.

ОСНОВНЫЕ ЗАСЛУГИ П. ДИРИХЛЕ В  ОБЛАСТИ МАТЕМАТИКИ: — установил, что в арифметической  прогрессии аn = а1 + dn, где n = 1,2 ... с  целыми взаимно простыми а1 и d  содержится бесконечно много простых  чисел; — исследовал понятие условной  сходимости ряда, установил признак  сходимости ряда; — ввёл функциональные ряды особого  вида; — ввёл (вместе с Н. И. Лобачевским)  определение функции через  соответствие и т. д.

ИИ ЕИ В КОМБИНАТОРИКЕ ПР НЦИП ДИРИХЛ   (НЕМ. SCHUBFACHPRINZIP, «ПРИНЦИП ЯЩИКОВ») —  УТВЕРЖДЕНИЕ, СФОРМУЛИРОВАННОЕ НЕМЕЦКИМ  МАТЕМАТИКОМ ДИРИХЛЕ В 1834 ГОДУ,  УСТАНАВЛИВАЮЩЕЕ СВЯЗЬ МЕЖДУ ОБЪЕКТАМИ  («КРОЛИКАМИ») И КОНТЕЙНЕРАМИ («КЛЕТКАМИ»)  ПРИ ВЫПОЛНЕНИИ ОПРЕДЕЛЁННЫХ УСЛОВИЙ. В  АНГЛИЙСКОМ И НЕКОТОРЫХ ДРУГИХ ЯЗЫКАХ  УТВЕРЖДЕНИЕ ИЗВЕСТНО КАК «ПРИНЦИП ГОЛУБЕЙ  И ЯЩИКОВ» (АНГЛ.  PIGEONHOLE PRINCIPLE), КОГДА  ОБЪЕКТАМИ ЯВЛЯЮТСЯ ГОЛУБИ, А  КОНТЕЙНЕРАМИ — ЯЩИКИ.  9 клеток содержат 7  голубей,  по принципу  Дирихле хотя бы  9­7=2 клетки свободны  9 клеток содержат 10 голубей,  по принципу Дирихле хотя бы  в одной клетке находятся  более одного голубя

РАССМОТРИМ ПРИМЕРЫ РАЗЛИЧНЫХ  ЗАДАЧ, РЕШАЕМЫХ С ПОМОЩЬЮ  ПРИНЦИПА ДИРИХЛЕ  1.   В классе 15 учеников. Докажите,                             что найдутся как минимум 2 ученика,                             отмечающих дни рождения в один  месяц.                                                                                            РЕШЕНИЕ:         Пусть 15 учеников будут «зайцы». Тогда «клетками»  будут месяцы года, их 12. Так как 15 > 12, то, по  принципу Дирихле, найдется, как минимум, одна  клетка, в которой будет сидеть, по крайней мере, 2  «зайца». То есть, найдется месяц, в котором будут  отмечать дни рождения не менее          2 учеников класса.

2. ВНУТРИ РАВНОСТОРОННЕГО ТРЕУГОЛЬНИКА СО СТОРОНОЙ  1 СМ РАС­ПОЛОЖЕНО 5 ТОЧЕК. ДОКАЖИТЕ, ЧТО РАССТОЯНИЕ  МЕЖДУ НЕКОТО­РЫМИ ДВУМЯ ИЗ НИХ МЕНЬШЕ 0,5 СМ.  РЕШЕНИЕ:             Это наиболее трудная задача на принцип Дирихле . Но  на примере ее решения очень хорошо видны все достоинства  принципа Дирихле. Итак, при решении сначала надо  выбрать что­то за «зайцев». Так как в условии задачи  фигурирует число «5», то пусть 5 точек будут «зайцами». Так  как «клеток» должно быть меньше, и чаще всего на 1, то их  должно         быть 4. Как получить эти 4 «клетки»? Так как в  условии     задачи есть еще 2 числа; 1 и 0,5; причем второе  меньше первого в 2 раза, то можно получить 4 « клетки »,  разбив равносторонний треугольник с помощью проведения  отрезков, соединяющих середины сторон. Тогда получим 4  равносторонних треугольника со сторонами по 0,5 см,  которые и будут у нас «клетками». Так как  «зайцев» ­ 5,  «клеток» ­ 4 и 5>4,то, по принципу Дирихле, найдется  «клетка» ­ равносторонний треугольник со стороной 0,5 см, в  который попадут не менее двух «зайцев» ­  точек.  Так как 4  треугольника равны и расстояние между точками в любом  треугольнике меньше, чем 0,5 см. т.е. некоторыми двумя  точками из пяти расстояние будет меньше, чем 0,5.

ДАНО 12 ЦЕЛЫХ ЧИСЕЛ. ДОКАЖИТЕ, ЧТО ИЗ  НИХ МОЖНО ВЫБРАТЬ 2, РАЗНОСТЬ  КОТОРЫХ ДЕЛИТСЯ НА 11. РЕШЕНИЕ     Примем числа за «зайцев».  Так как их 12, то «клеток»  должно быть меньше. Пусть  «клетки» —это остатки от  деления целого числа на 11.  Всего «клеток» будет 11: О, 1,  2, 3, 4, 5, 6, 7, 8, 9,10. Тогда, по  принципу Дирихле, найдется  «клетка», в которой будут  сидеть не менее чем 2 «зайца»,  то есть найдутся 2 целых  числа с одним остатком. А  разность двух чисел с  одинаковым остатком от  деления на 11, будет делиться  на 11

В КОВРЕ РАЗМЕРОМ 3X3 МЕТРА КОЛЯ ПРОДЕЛАЛ 8 ДЫРОК.  ДОКАЖИТЕ, ЧТО ИЗ НЕГО МОЖНО ВЫРЕЗАТЬ КОВРИК  РАЗМЕРОМ 1X1 МЕТР, НЕ СОДЕРЖАЩИЙ ВНУТРИ СЕБЯ  ДЫРОК.  (ДЫРКИ МОЖНО СЧИТАТЬ ТОЧЕЧНЫМИ.)  РЕШЕНИЕ           Здесь дырки будут «зайцами». Разрежем  ковер на 9 ковриков размерами 1x1 метр. Так  как ковриков­«клеток» — 9, а дырок­«зайцев»  — 8, то найдется хотя бы одна «клетка», в  которой не будет «зайцев», то есть найдется  коврик без дырок внутри.

ЗАДАЧА. В ХВОЙНОМ ЛЕСУ РАСТУТ 800000 ЕЛЕЙ. НА  КАЖДОЙ ЕЛИ ­ НЕ БОЛЕЕ 500000 ИГОЛОК. ДОКАЗАТЬ,  ЧТО СУЩЕСТВУЮТ ХОТЯ БЫ ДВЕ ЕЛИ С  ОДИНАКОВЫМ ЧИСЛОМ ИГОЛОК.

РЕШЕНИЕ. Число "клеток" – 500000  (на каждой  ели может быть от 1 иголки до 500000  иголок, 800000 ели – число  "кроликов", так как, "кроликов"  больше чем клеток, значит, есть  "клетка", в которой сидит не менее  двух "кроликов". Значит, существуют  хотя бы две ели с одинаковым числом  иголок.

ЗАДАЧА КОЛИЧЕСТВО ВОЛОС НА ГОЛОВЕ У ЧЕЛОВЕКА НЕ  БОЛЕЕ 140 000 ДОКАЗАТЬ, ЧТО СРЕДИ 150 000 ЧЕЛОВЕК НАЙДУТСЯ 2 С  ОДИНАКОВЫМ ЧИСЛОМ ВОЛОС НА ГОЛОВЕ

РЕШЕНИЕ  Число "клеток" – 140 000  (у каждого человека может  быть от 0 до 140 000), 150 000 человек – число  "кроликов", так как, "кроликов" больше чем клеток,  значит, есть "клетка", в которой сидит не менее двух  "кроликов". Значит, существуют хотя бы два  человека с одинаковым числом волос

ЗАДАЧА НА КОМБИНАТОРИКУ В КОРОБКЕ ЛЕЖАТ ШАРИКИ 4­Х РАЗНЫХ ЦВЕТОВ (МНОГО БЕЛЫХ,  МНОГО ЧЕРНЫХ, МНОГО СИНИХ, МНОГО КРАСНЫХ). КАКОЕ  НАИМЕНЬШЕЕ КОЛИЧЕСТВО ШАРИКОВ НАДО НАОЩУПЬ ВЫНУТЬ ИЗ  МЕШКА, ЧТОБЫ СРЕДИ НИХ ЗАВЕДОМО ОКАЗАЛИСЬ ДВА ОДНОГО  ЦВЕТА?

РЕШЕНИЕ Возьмем  за  «кроликов»  шары,  а  за  «клетки»  ­  черный,  белый,  синий,  красный  цвета.  Клеток  4,  поэтому  если  кроликов,  хотя  бы  5,  то  какие­то  два  попадут  в  одну  клетку  (будет  2  одноцветных  шарика).

ЗАДАЧА НА ДЕЛИМОСТЬ ЗАДАЧА . ДАНО 11 РАЗЛИЧНЫХ ЦЕЛЫХ ЧИСЕЛ.  ДОКАЗАТЬ, ЧТО ИЗ НИХ МОЖНО ВЫБРАТЬ ДВА ЧИСЛА,  РАЗНОСТЬ КОТОРЫХ ДЕЛИТСЯ НА 10.  Решение. По крайней мере, два числа из 11 дают  одинаковый остаток при делении на 10 . Пусть это  будут A = 10a + r и B = 10b + r. Тогда их разность  делится на 10: A ­ B = 10(a ­ b).

ЗАДАЧА  ДОКАЗАТЬ, ЧТО ЧИСЛО N5  ОКАНЧИВАЕТСЯ НА ТУ ЖЕ  ЦИФРУ,               ЧТО ЧИСЛО N            Докажем, что N 5­N кратно 10          N 5  NNN ( 4  )1 ( NN 2  2 )(1 N  )1 NN (  )(1 N  )(1 N 2  )1 ( N  N )(1 N(N­1) Кратно 2 2  )1 Кратно 5

ЗАДАЧИ   Задача 1. В классе 35 учеников. Докажите, что среди них  найдутся два ученика, фамилии которых начинаются с  одной и той же буквы.   Решение. В русском алфавите 33 буквы. Следовательно,  среди 35 учеников найдутся два ученика, фамилии  которых начинаются с одной и той же буквы.   Задача 2. В школе 20 классов. В ближайшем доме живет  22 ученика этой школы. Верно ли, что среди них найдутся  хотя бы два одноклассника?   Ответ. Верно.   Задача 3. При каком наименьшем количестве учеников  школы среди них обязательно найдутся двое, у которых  день и месяц рождения совпадают?   Ответ. 367.

 Задача 5. Сто человек сидят за круглым столом, причем более  половины из них – мужчины. Докажите, что найдутся два  мужчины, сидящие друг напротив друга.   Решение. Число пар, образованных людьми, сидящими  напротив друг друга равно 50. Так как число мужчин больше 50,  то хотя бы в одной паре найдутся два мужчины.   Задача 6. В ящике лежат 105 яблок четырех сортов. Докажите,  что среди них найдутся, по крайней мере, 27 яблок одного сорта.   Решение. Если бы число яблок одного сорта было не более 26, то  общее число яблок должно было быть не более 104.   Задача 7. Докажите, что из 82 выкрашенных в определенный  цвет кубиков, можно выбрать или 10 кубиков разных цветов, или  10 кубиков одного цвета.   Решение. Если число кубиков одного цвета не больше 9, то  число кубиков хотя бы одного цвета должно быть больше 9. так  как в противном случае общее число кубиков было бы не больше  81.

 Задача 8. 65 школьников за год написали три контрольные работы, за  которые ставились оценки 2, 3, 4, 5. Верно ли, что среди этих школьников  найдутся двое, получившие одинаковые оценки за все контрольные работы?   Решение. Число различных оценок равно 43 = 64. Следовательно, среди 65  школьников найдутся двое, получившие одинаковые оценки за все  контрольные работы   Задача 9. В классе 25 учеников. Среди любых трех из них есть двое друзей.  Докажите, что в этом классе есть ученик, у которого не менее 12 друзей.   Решение. Предположим, что в классе есть два ученика, не являющихся  друзьями. Каждый человек из оставшихся 23 учеников является другом  одного из этих двух учеников. Значит, у одного из них число друзей не менее  12.   Задача 10. В бригаде 7 человек. Их суммарный возраст – 332 года.  Докажите, что среди них найдутся три человека, сумма возрастов которых не  меньше 142 лет.   Решение. Число различных троек из семи человек равно 35. Каждый  человек участвует в 15 тройках. Суммарный возраст всех человек во всех  тройках равен 332∙15 = 4980. Следовательно, должна быть тройка, в которой  суммарный возраст не меньше 4980:35, что больше 142.   Задачи

ЗАДАЧИ НА ДЕЛИМОСТЬ   Задача 1. Докажите, что среди любых n + 1 натуральных чисел найдутся два числа, которые  при делении на n дают одинаковые остатки.   Решение. Остатками могут быть n чисел: 0, 1, …, n. Следовательно, среди любых n + 1  натуральных чисел найдутся два числа, которые при делении на n дают одинаковые остатки.   Задача 2. Дано 12 целых чисел. Докажите, что из них можно выбрать два, разность которых  делится на 11.   Решение. Число различных остатков при делении на 11 равно 11. Среди 12 целых чисел  найдутся два, имеющие одинаковые остатки и, следовательно, их разность будет делиться на  11.   Задача 3. Докажите, что среди любых 10 целых чисел найдется несколько чисел, сумма  которых делится на 10.   Решение. Обозначим числа a1, a2, …, a10. Среди чисел 0, a1, a1 + a2, …, a1 + …+ a10 найдутся  два, имеющие одинаковые остатки при делении на 10. Тогда их разность будет делиться на 10.   Задача 4. Верно ли, что из любых семи натуральных чисел найдутся три, сумма которых  делится на 3?   Решение. Число различных остатков при делении на 3 равно трем. Из семи чисел найдутся  три, имеющие одинаковые остатки. Сумма этих чисел будет делиться на 3.   Задача 5. Докажите, что среди любых 52 целых чисел найдутся два числа, сумма или  разность которых делится на 100.   Решение. Разобьем все остатки при делении на 100 на группы {0}, {1, 99}, …, {49, 51}, {50}.  Число таких групп равно 51. Среди 52 целых чисел найдется два числа, у которых остатки  попадают в одну группу. Сумма или разность этих чисел будет делиться на сто.

ГЕОМЕТРИЧЕСКИЕ ЗАДАЧИ   Задача 1. На плоскости проведены 10 прямых, никакие две из которых  не параллельны. Докажите, что среди этих прямых найдутся две, угол  между которыми не больше 18о.   Решение. Если бы все углы были больше 18о, то их сумма была бы  больше 360о, что невозможно.   Задача 2. В квадрате 4х4 нарисовано 15 точек. Докажите, что из него  можно вырезать квадратик 1x1, не содержащий внутри себя ни одной из  этих точек.   Решение. Разобьем квадрат на 16 равных квадратиков. Хотя бы в один  из них не будет содержать внутри себя точку.   Задача 3. Докажите, что в круге радиуса 1 нельзя выбрать более 5  точек, попарные расстояния между которыми больше 1.   Решение. Разобьем круг на 6 равных секторов. Ни в одном из них не  может быть двух точек, так как в этом случае расстояние между ними  будет не больше 1. Предположим, что в каждом секторе имеется по точке.  Тогда найдутся две точки, для которых центральный угол, образованный  лучами, проходящими через эти точки, не больше 60о. Тогда расстояние  между этими точками не больше 1. Следовательно, нельзя выбрать более  5 точек, попарные расстояния между которыми больше 1.

  Задача 3. (Ленинградская и др. олимпиады) Можно ли в  клетках квадратной таблицы 5 ∙  5 расставить числа 0, +1,  –1 так, чтобы все суммы в каждом столбце, в каждой  строке и на каждой из двух диагоналей были различны?   Решение. Если предположить, что такая расстановка  чисел 0, +1, –1 возможна, то из этих чисел можно составить  12 = 5 + 5 + 2 различных сумм чисел. Но из чисел 0, +1, –1  можно со­ставить только 11 их сумм, причем наименьшее  из них равно 5 (cid:215) (–1),  а наибольшее равно 5 (cid:215) (+1);  при этом  все такие суммы являются целыми числами. Поэтому  расставить числа тре­буемым способом нельзя.   Задача 4. В ряд выписано пять натуральных чисел: a1, a2,  a3, a4, a5. Докажите, что либо одно из них делится на 5,  либо сумма нескольких рядом стоящих чисел делится на 5.

 Задача 11. В квадрате со стороной 1 отметили  51 точку. Докажите, что три из них можно  покрыть кругом диаметра 1 / 7.   Решение. Разобьем квадрат прямыми,  параллельными его сторонам, на 25 равных  квадратов со стороной 1 / 5 . По принципу  Дирихле найдется, по крайней мере, один из  них, который содержит (внутри или на  сторонах) не менее трех отмеченных точек.  Опишем окружность около этого квадрата  (рис. 9); тогда AB2 = DC2 + AC2 = 1/25+ 1/25=    1 /50

ТАКИМ ОБРАЗОМ, ПРИМЕНЯЯ ДАННЫЙ МЕТОД,  НАДО:  Определить, что удобно в задаче принять за  «клетки», а что за «зайцев».  Получить «клетки»; чаще всего «клеток» меньше  (больше), чем «зайцев» на одну (или более).  Выбрать для решения требуемую формулировку  принципа Дирихле.      Принцип Дирихле важен, интересен, полезен.  Его можно применять в повседневной жизни, что  развивает логическое мышление.          Многие олимпиадные задачи решаются,  используя это специальный метод. Он дает  возможность обобщать.

ЛИТЕРАТУРА   1.А.В. Спивак «Математический праздник». С.А. Генкин, И.В. Итенберг, Д.В. Фомин  2.«Ленинградские математические кружки» 3.А.Я. Канель­Белов, А.К. Ковальджи «Как  решают нестандартные задачи». 4.С.А. Дориченко, И.В.Ященко «57 Московская  математическая олимпиада. Сборник  подготовительных задач».  5. Н.В. Горбачев. Сборник олимпиадных задач по  математике. М.: МЦНМО, 2004.

ЛИТЕРАТУРА   6. Андреев А. А., Горелов Г. Н., Люлев А. И., Савин А. Н. Принцип  Дирихле. Учебное издание.  7.Серия А: Математика. Вып. 1. — Самара: Пифагор, 1997. — 21 с.,  ил.  8. Севрюков П. Ф. Школа решения олимпиадных задач по  математике. — М. : Илекса; Ставрополь:  Сервисшкола, 2012. — 176 с.  9. Бабинская И. Л. Задачи математических олимпиад. — М. :  Наука, 1975.  10. Васильев Н. Б., Егоров А. А. Задачи всесоюзных математических  олимпиад. — М. : Наука, 1988.  11. Вышенский В. А., Карташов Н. В., Михайлов­  ский В. И., Ядренко М. И. Сборник задач киевских математических  олимпиад. — К. : Вищашкола, 1984.  12 . Генкин С. А., Итенберг И. В., Фомин Д. В. Ленинградские  математические кружки. — Киров:  АСА, 1994.