Принцип дирихле что это
Принцип Дирихле и его применение
Самая популярная формулировка принципа Дирихле такова:
Принцип Дирихле представляет собой настолько очевидное утверждение, что на первый взгляд даже непонятно, почему он является весьма эффективным методом решения задач. Дело в том, что в каждой конкретной задаче нелегко бывает понять, что же здесь «зайцы» и «клетки» и почему зайцев больше, чем клеток. Выбор зайцев и клеток часто неочевиден ; далеко не всегда по виду задачи можно определить, что следует воспользоваться принципом Дирихле.
Авторские задачи, решаемые с помощью принципа
К Новому Году в детском саду ребята делали фонарики. В группе 30 детей. Петя Пяточкин сделал 12 фонариков, а остальные – меньше. Докажите, что хотя бы три ребенка сделали одинаковое количество фонариков (может быть, по 0 шт. ).
П опал Петя Пяточкин. Применим принцип
В научно-исследовательском институте 33 отдела. Всего работает 1150 человек. Найдется ли отдел, в котором меньше 35 сотрудников?
На свой юбилей отец пригласил 25 сослуживцев. Известно,что среди любых трех из них есть двое знакомых друг с другом. Докажите,что есть такой гость,у которого не менее 2 знакомых.
Выберем любых двух гостей, которые не знакомы между собой. ( Если таких нет,то все гости знакомы между собой
,значит,у каждого имеется 24 знакомых, и задача решена).
Из оставшихся 23 гостей каждый знаком с одним из этих двух,иначе мы имели бы тройку гостей,среди которых не было бы знакомых. Тогда у одного из выбранны х двух гостей не менее12 з на к ом ых (23 «зайца» рассажены в двух «клетках»).
За пять лет дачники вырастили и собрали 31 кг. черной смородины. Причем каждый год они собирали урожай больший,чем в предыдущем году. На пятом году они собрали ягод втрое больше,чем в первый год. Какой был урожай смородины на четвертый год?
Принцип дирихле что это
ПРИНЦИП ДИРИХЛЕ
Автор работы награжден дипломом победителя III степени
Введение
Объектом моих исследований являются способы и методы решения логических задач. Логическая задача – это особый вид задачи, который развивает логику, образное и творческое мышление, поэтому часто такие задачи являются олимпиадными. Решение таких задач увлекательное занятие, поскольку для решения большинства из них требуется не только знание определенного программного материала, но и логическое мышление. Я уже рассматривал применение кругов Эйлера и задачи на шахматной доске.
Разнообразие логических задач велико, велико и количество способов их решения. При решении многих задач я столкнулся с еще одним методом рассуждения — «от противного». Меня заинтересовала одна из его форм — принцип Дирихле. Способ решения задач с помощью данного принципа я сделать предметом исследования данной работы.
Гипотеза: принцип Дирихле позволяет решать некоторые логические задачи, которые сложно решать другими способами.
Цель работы:
исследование эффективности применения принципа Дирихле в решении задач;
получение знаний о применении и сферах использования принципа Дирихле.
В ходе выполнения работы мной были решены следующие задачи:
изучить литературу и собрать информацию о принципе Дирихле;
отобрать и систематизировать задачи, решаемые с помощью принципа Дирихле;
научиться самостоятельно решать задачи данным методом.
Мной использовались следующие методы исследования:
Моя работа весьма актуальна, так как принцип Дирихле не рассматривается в учебниках математики, а полученные знания пригодятся для сдачи экзаменов и решении практических задач в жизни.
I. Общая информация о принципе Дирихле
I. 1. Биография Дирихле
Дирихле Петер Густав Лежен (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. Обобщение принципа Дирихле
Обобщенный принцип Дирихле также достаточно очевиден: если бы в каждой клетке сидело не более k зайцев, то во всех клетках было бы не более nk зайцев, что противоречит условию. Обобщение принципа используют, когда требуется выявить несколько (три и более) объектов, обладающих некоторым свойством.
В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта. Решение.
Вывод: таким образом, имея принцип Дирихле, мы можем каждый раз не расписывать решение задачи методом от противного, а будем лишь ссылаться на Дирихле фразой «согласно с принципом Дирихле».
II. Применение принципа Дирихле для решения различных задач
II. 1. Принцип Дирихле и арифметика
Задача 2. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.
Решение: 400 > 366.
Задача 3. В классе 40 учеников. Найдётся ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 ученика этого класса?
Решение: Рассуждаем от противного. Если бы такого месяца не нашлось, то в каждом из 12 месяцев день рождения отмечали бы не более трёх учеников. Значит, всего учеников было бы не более 12 · 36. Но 40 > 36. Противоречие.
II. 2. Принцип Дирихле в теории чисел
Возможна следующая переформулировка принципа Дирихле:
«Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток».
Задача 1. Дано 11 различных целых чисел. Доказать, что из них можно выбрать два числа, разность которых делится на 10.
Задача 2. Из любых трёх целых чисел можно выбрать два, сумма которых чётна. Докажите это.
Решение: Все числа можно разбить на два класса: чётные и нечётные. Невозможно распределить три числа по двум классам так, чтобы ни в какой класс не попало более одного числа. Значит, среди любых трёх целых чисел найдутся два числа одинаковой чётности. Их сумма чётна.
II. 3. Принцип Дирихле и геометрия
Задача 1. В квадрат со стороной 1 метр бросили 51 точку. Докажите, что какие-то три из них можно накрыть квадратом со стороной 20 см.
Решение: Разобьем наш квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле, в какой-то из них попадёт, по крайней мере, три точки из 51 брошенной.
Задача 2. Внутри равностороннего треугольника со стороной 1см расположено 5 точек. Докажите, что расстояние между некоторыми двумя из них меньше 0,5см.
Решение: Можно получить 4 «клетки», разбив равносторонний треугольник с помощью проведения отрезков, соединяющих середину сторон. Тогда получим 4 равносторонних треугольника со сторонами по 0,5 см, которые и будут у нас «клетками».
Теория чисел, или высшая арифметика — раздел чистой математики, изучающий свойства натуральных и целых чисел.
Чётное число — целое число, которое делится на 2 без остатка: …−4,−2,0,2,4,6,8,10.
math4school.ru
Принцип Дирихле
Немного теории
Этот принцип достаточно прост и очевиден, иногда им пользуются из соображений логики, даже не зная его формулировки. Но, зная этот принцип, легче догадаться в каких случаях его применять. Проще всего принцип Дирихле выражается в такой шуточной форме: «Если в n клетках больше чем n+1 зайцев, то хотя бы в одной клетке сидят не меньше двух зайцев».
А теперь так: «Если множество, состоящее из nk+1 элементов, разбить на k подмножеств, то хотя бы в одном подмножестве найдётся не менее чем n+1 элементов».
Доказательство принципа Дирихле можно провести, применив метод от противного. Приведем еще несколько похожих на принцип Дирихле (и столь же очевидных) утверждений, используемых в геометрических и аналитических задачах:
а) если сумма площадей нескольких фигур меньше S, то ими нельзя покрыть фигуру площади S;
б) если на отрезке длины 1 расположено несколько отрезков с суммой длин L, то найдется точка, покрытая не более чем [L] этими отрезками;
в) если тело с объёмом V разбили на n частей (которые не имеют общих внутренних точек), то объём наибольшей части не меньше V/n, а объём наименьшей – не больше V/n;
г) если среднее арифметическое нескольких чисел больше А, то хотя бы одно из этих чисел больше А.
Задачи с решениями
1. Доказать, что среди 101 целого числа всегда можно выбрать два таких, что их разность делится на 100.
2. В розыгрыше первенства по футболу участвуют 30 команд. Каждые две команды должны сыграть между собой один матч. Доказать, что в любой момент состязаний имеются две команды, сыгравшие к этому моменту одинаковое число матчей.
3. Задача Рамсея. Докажите, что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых.
Выберем одного произвольного человека из шести. Среди оставшихся пяти обязательно найдутся либо трое (как минимум) знакомых с ним, либо трое (как минимум) незнакомых с выбранным. Разберем, например, первый случай. Среди этих троих людей либо найдутся двое знакомых – тогда они вместе с выбранным нами человеком образуют нужную тройку, либо они все трое попарно незнакомы. Другой случай разбирается аналогично.
4. Имеется n целых чисел. Доказать, что среди них найдутся несколько (или, быть может, одно), сумма которых делится на n.
Пусть а1, а2, …, аn – данные числа. Рассмотрим n сумм:
Либо одна из этих сумм делится на n и значит является искомой, либо ни одна не делится на n. Во втором случае найдутся две суммы с одинаковым остатком, ведь сумм n, а ненулевых остатков только n–1. Разность этих сумм
– тоже сумма и делится на n.
5. Ежедневно на протяжении года ученик решал не менее одной задачи, причём еженедельно он решал не более 12 задач. Доказать, что найдётся несколько последовательных дней, за которые он решил ровно 20 задач.
Будем считать, что год имеет ровно 52 недели. Введём обозначения:
a1 – количество задач, решённых за один первый день;
a2 – количество задач, решённых за два первых дня;
a3 – количество задач, решённых с первого по третий день;
a364 – количество задач, решённых за год, т.е. 52 недели.
Замечание 1. На протяжении года было 84 таких промежутков времени, когда ученик решал по 84 задачи.
Замечание 2. В данной задаче достаточно ограничится промежутком времени гораздо меньшим, чем год. Можно показать, например, что на протяжении 77 дней тоже найдётся несколько последовательных дней за которые было решено ровно 20 задач.
6. Каждая из девяти прямых разбивает квадрат на два четырёхугольника, площади которых относятся как 2:3. Докажите, что, по крайней мере, три из этих прямых проходят через одну точку.
Каждая прямая, разбивающая квадрат на два четырёхугольника, (либо две трапеции, либо два прямоугольника) с отношением площадей 2:3, в таком же отношении делит среднюю линию квадрата. Докажем это. Пусть дан квадрат АВСD (рис. 1).
Его пересекает прямая МN. Пусть РQ – средняя линия квадрата (Р – середина АВ, Q – середина СD) и К – точка пересечения РQ и МN. Площади трапеций АВМN и MNDС равны соответственно АВ·РК/2 и АВ·КQ/2. Поэтому если они относятся как 2:3, то и РК:КQ = 2:3.
Таких точек, которые делят средние линии квадрата в отношении 2:3, всего четыре (рис. 2), а прямых – девять. Согласно принципу Дирихле найдется точка, через которую проходят, по крайней мере, три прямые, что и требовалось доказать.
8. Каждая точка плоскости окрашена в один из двух цветов. Доказать:
а) на этой плоскости существует равнобедренный треугольник, все три вершины которого окрашены в один и тот же цвет;
б) на этой плоскости существует равносторонний треугольник, все три вершины которого окрашены в один и тот же цвет;
в) на этой плоскости найдётся треугольник с углами 30°, 60°, 90° и гипотенузой n, вершины которого окрашены в один и тот же цвет.
а) Рассмотрим пять точек, расположенных в вершинах правильного пятиугольника.
Среди них, согласно принципу Дирихле, есть, как минимум, три точки одинакового цвета. Поскольку расстояния между этими тремя точками принимают лишь два значения (длина стороны и длина диагонали пятиугольника), то одно из них, опять же по принципу Дирихле, встречается дважды, и треугольник с вершинами в этих точках – равнобедренный.
б) Для доказательства можно использовать, например, девять точек, которые расположены так, как показано на рисунке ниже (точки расположены в вершинах восьми равных равносторонних треугольников) и провести рассуждения аналогичные тем, которые были приведены в задаче а).
в) Сначала найдём две одноцветные точки, расстояние между которым n. Для этого достаточно рассмотреть равносторонний треугольник со стороной n. По крайней мере, две его вершины окрашены в один цвет. Пусть они красные, обозначим их А и В. Построим правильный шестиугольник AKLBMN.
Если из точек K, L, M, N хоть одна красная, то А, В и эта точка являются вершинами искомого треугольника. Если же K, L, M, N синие, то искомым является, например, треугольник KLM.
9. Пусть у выпуклого 24-угольника все стороны и диагонали окрашены либо в красный, либо в синий цвет. Можно ли выбрать 4 вершины так, чтобы все стороны и диагонали образованного четырехугольника имели одинаковый цвет?
1) крупный и мелкий пунктиры красные;
2) крупный пунктир красный, мелкий – синий;
3) мелкий пунктир красный, крупный – синий;
4) крупный и мелкий пунктиры синие.
Рассмотрим каждый из случаев.
Случай 1. А1А2А3А13, например, – красный четырехугольник, т.е. такой, все стороны и диагонали которого окрашены в красный цвет.
Случай 2. Если какой-то из отрезков А4А5, А5А6, А6А7, А4А6, А5А7, А4А7 красный, то четырехугольник, имеющий противоположными сторонами этот отрезок и отрезок А1А13, является красным. Если же все эти шесть отрезков синие, то синий – четырехугольник А4А5А6А7.
Случай 3. Если какой-то из отрезков А3А4, А4А5, А3А5 является красным, то четырехугольник, имеющий противоположными сторонами этот отрезок и отрезок А2А13, является красным. Если же все эти три отрезка синие, то синим является четырехугольник А1А3А4А5.
Случай 4. Если какой-то из отрезков А3А4, А4А5, А3А5 является синим, то четырехугольник, имеющий противоположными сторонами этот отрезок и отрезок А1А2, является синим. Если же три названные отрезки красные, то четырехугольник А3А4А5А13 – красный.
10. Ограниченная плоская фигура имеет площадь S > 1. Докажите, что её можно “перенести” на вектор с целыми коэффициентами так, чтобы начальная фигура и образ пересекались.
Пусть данная фигура F содержится в квадрате со стороной d. Выберем систему координат так, чтобы точка О(0;0) была внутренней точкой данной фигуры. При произвольном натуральном k рассмотрим все возможные образы фигуры F при параллельных переносах на вектор a(m;n), где m,n – натуральные и принадлежат отрезку [0;k].
Очевидно, что каждый из таких образов расположен внутри квадрата Q, каждая точка которого имеет координаты (хQ;уQ) и при этом хQ и уQ – числа из отрезка [–d;k+d].
Допустим, что никакие два образа не пересекаются. Тогда их общая площадь не превышает площади квадрата Q, то есть (k+1) 2 S–(k+2d) 2 – неположительное число, или (S–1)k 2 +2(S–2d)k+S–4d 2 – не больше нуля.
Но вследствие условия S–1 > 0 и свойств квадратичной функции это невозможно при достаточно больших k. Значит некоторые два образа F1и F2, которые получаются при параллельном переносе фигуры F на векторы а1 и а2, соответственно, пересекаются. Очевидно, что параллельный перенос на вектор а = а1 – а2 отображает фигуру F1 в фигуру F2.
Задачи без решений
11. Группа людей состоит из 40 человек. Найдётся ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 человека из этой группы?
12. Дано n+1 различных натуральных чисел, меньших 2n. Доказать, что из них можно выбрать три таких числа, что одно из них равно сумме двух других.
13. Можно ли найти такой натуральный показатель степени числа 3, чтобы значение этой степени оканчивалось на 0001?
14. Каждая сторона и диагональ выпуклого 17-угольника окрашена в один из трёх цветов. Докажите, что всегда можно выбрать три вершины так, что получившийся треугольник будет иметь стороны одного цвета.
15. В пространстве расположено n точек так, что любые четыре из них являются вершинами тетраэдра с объёмом не большим k. Докажите, что все эти точки можно заключить в некоторый тетраэдр, объём которого равен 5k.
Принцип Дирихле
Математические олимпиады являются одной из форм внеклассной работы и массовым соревнованием учащихся. На олимпиадах учащиеся показывают свой уровень знаний в области математики. Олимпиады способствуют повышению интереса учащихся к предмету. Задачи для своего решения требуют сообразительности и умения рассуждать.
Подготовка учащихся к решению олимпиадных задач является одной из функций учителя математики. Но вместе с тем учителям общеобразовательных школ не хватает современной методической литературы, предназначенной для работы с более способными учащимися по организации и проведению кружковых занятий, олимпиад по математике. Учителя готовят учащихся к олимпиадам, опираясь на свой собственный опыт и обычно работа ведется на эмпирическом уровне без теоретической основы.
Объект исследования – методы решения олимпиадных задач.
Предмет исследования – принцип Дирихле.
Цель – изучить принцип Дирихле и научиться применять его для решения задач.
Результаты исследования были представлены на конференциях, таких как «Студенчество в научном поиске» (20 апреля 2018 г.) и «Молодежь в мире науки» (24 ноября 2017 г.).
Работа состоит из введения, теоретической части, в которой два параграфа, практической части, в которой четыре параграфа и заключения. Список использованной литературы включает в себя 23 наименования.
Глава Ι. Основные сведения о принципе Дирихле
История создания принципа Дирихле
тема очень в наши дни. Так как роль олимпиад растёт, а знание принципа Дирихле очень помогает при решении олимпиадных задач. Так же он используется в разных областях математики и в повседневной жизни.
Таким образом, мы познакомились с историей создания данного принципа. Изучением принципа Дирихле занимались такие учёные как Давид Гильберт, Вейерштрасс, Гаусс и Риман. А также, выяснили какую связь устанавливает Дирихле в своём принципе.
1.2 Формулировки принципа Дирихле
При решении многих задач используется логический метод рассуждения — «от противного». Принцип Дирихле как раз является одним из таких примеров. Существует несколько формулировок этого принципа. Основное определение, сформулированное самим Дирихле, звучит так: «если в n клетках сидит n + 1 зайцев или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца».
Доказательство. Это утверждение можно доказать от противного. Допустим, что в каждой «клетке» не более одного «зайца», тогда общее число «зайцев» будет n. Противоречие. А значит найдётся «клетка», в которой хотя бы два «зайца».
Также нужно узнать способ, которым надо усаживать «зайцев» в «клетки».
Было сформулировано другое определение принципа Дирихле: «если n + 1 предмет поместить в n мест, то обязательно хотя бы в одном месте окажутся хотя бы два предмета».
Разных формулировок принципа Дирихле много. И в зависимости от типа задачи нужно найти подходящую формулировку для решения.
Существует так называемый обобщённый принцип Дирихле. Но это лишь свойство выделяемое из этого принципа. Он тоже достаточно очевиден и его используют в тех случаях, когда требуется выявить несколько (три и более) объектов, обладающих некоторым свойством. Звучит он так: «если в n клеток посадить k * n + 1 зайцев, то найдется хотя бы одна клетка, в которой находятся не менее чем k + 1 заяц». В данном случае k и n являются натуральные числа.
Доказательство. Предположим, что не найдётся такой клетки. Значит, в каждой клетке находится не более чем k зайцев. Тогда в n клетках не более чем k * n зайцев. Но по условию у нас было k * n + 1 зайцев. Получилось противоречие, а значит наше предположение неверно. Из этого следует, что найдется хотя бы одна клетка, в которой находятся не менее чем k + 1 заяц.
Таким образом, мы познакомились с формулировками принципа Дирихле и их доказательствами. Узнали, что в роли «зайцев» и «клеток» могут выступать любые предметы. И в зависимости от типа задачи нужно найти подходящую формулировку для решения.
Изучив теоретическую основу по данной теме, можно рассмотреть примеры задач, в которых используется принцип Дирихле.
Глава ΙΙ. Применение принципа Дирихле к решению задач
Мы рассмотрели и систематизировали задачи с использованием принципа Дирихле на 4 группы. Задачи в комбинаторике, в арифметике, в теории чисел и в геометрии.
2.1 Решение арифметических задач
1. В классе 30 учеников. Ваня сделал в контрольной работе 13 ошибок, а остальные допустили меньшее количество ошибок. Докажите, что по крайней мере 3 ученика сделали равное количество ошибок.
2. В лесу растет миллион ёлок. Известно, что на каждой из них не более 600000 иголок. Докажите, что найдутся две ёлки с одинаковым числом иголок.
Доказательство. В данной задаче миллион «зайцев», то есть ёлок и всего лишь 600001 «клетка» (иголка) с номерами от 0 до 600000. Каждый «заяц» оказывается в «клетке» с номером, равным количеству иголок на этой ёлке. Так как «зайцев» больше, чем «клеток», то в какой-то «клетке» окажется по крайней мере два «зайца». Если бы в каждой сидело не более одного, то всего «зайцев» было бы не более 600001 штук. Зайцев оказалось больше чем клеток и из этого следует, что, хотя бы 2 ёлки с одинаковым количеством иголок.
3. В школе 450 учеников. Докажите, что, хотя бы двое из них родились в один день года.
4. В классе 40 учеников. Докажите, что найдётся такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 ученика этого класса.
Доказательство. Рассуждаем от противного. Если бы такого месяца не нашлось, то в каждом из 12 месяцев день рождения отмечали бы не более трёх учеников. Значит, всего учеников было бы не более 12*3=36. Но по условию у нас 40 учеников, а значит найдётся такой месяц в году, котором отмечают свой день рождения не меньше чем 4 ученика этого класса.
5. В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.
6. В городе N живет 3 миллиона человек. Докажите, что у каких-то двух из них одинаковое число волос на голове, если известно, что у любого человека на голове миллион волос.
7. Сто человек сидят за круглым столом, причем более половины из них – мужчины. Докажите, что какие-то два мужчины сидят друг напротив друга.
Доказательство. Разделим всех людей на 50 пар так, чтобы люди из одной пары сидели друг напротив друга. В данной задаче «клетки» это пары, а «зайцы» — это мужчины. По принципу Дирихле следует, что в одной из этих пар оба человека – мужчины, так как по условию их больше половины.
В данном параграфе мы рассмотрели выше представленные задачи и вывели следующую особенность: для решения задач данного типа нужно выполнить арифметические действия.
2.2 Решение задач из теории чисел
1. Докажите, что из любых трёх целых чисел можно выбрать два, сумма которых чётна.
Доказательство. Все числа можно разбить на два класса: чётные и нечётные. Невозможно распределить три числа по двум классам так, чтобы ни в какой класс не попало более одного числа. Значит, среди любых трёх целых чисел найдутся два числа одинаковой чётности. А сумма чётных чисел чётна.
2. Доказать, что среди 101 целого числа всегда можно выбрать два таких, что их разность делится на 100.
3. Натуральные числа от 1 до 9 разбиты на три группы. Докажите, что произведение чисел в одной из групп не меньше 72.
Доказательство. Так как произведение всех данных чисел равно 9! = 362880, а 72³ = 373248. Из этого следует что произведение чисел одной из групп не меньше 72.
4. Докажите, что среди любых шести целых чисел найдутся два, разность которых кратна 5.
Доказательство. При делении целого числа на 5 возможны пять различных остатков: 0, 1, 2, 3 или 4. Так как чисел по условию 6, значит, по принципу Дирихле среди них обязательно найдутся два с одинаковыми остатками. Если мы рассмотрим их разность, то она будет давать при делении на 5 остаток 0, а значит будет делиться на 5.
6. Докажите, что из любых 7-ми натуральных чисел можно выбрать три числа, сумма которых делится на 3.
Доказательство. Так как имеется лишь три различных остатка от деления на 3 — 0, 1 и 2. Значит, по принципу Дирихле среди 7 натуральных чисел можно выбрать хотя бы 3 числа, остатки которых будут совпадать. Их сумма, делится на 3.
На основе задач данного параграфа мы можем сказать, что для решения задач этого типа необходимо знать основы теории чисел.
2.3 Решение геометрических задач
1. В квадрат со стороной 1 метр бросили 51 точку. Докажите, что какие-то три из них можно накрыть квадратом со стороной 20 см.
Доказательство.Разделим квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле, в какой-то из них попадёт, по крайней мере, три точки из тех, что бросили.
2. Внутри равностороннего треугольника со стороной 1 см расположено 5 точек. Докажите, что расстояние между некоторыми двумя из них меньше 0,5см.
Доказательство. Разделим данный треугольник на 4 равносторонних треугольника, с помощью проведенных отрезков к серединам сторон (рис. 1). Тогда получим 4 равносторонних треугольника со сторонами по 0,5 см, которые и будут у нас «клетками». По принципу Дирихле так как точек 5, а треугольников 4, то в одном из них будет хотя бы 2 точки.
3. В полотенце 4 м × 4 м моль прогрызла 15 дырок. Докажите, что из него можно вырезать коврик 1 м × 1 м, не имеющем внутри себя дырок.
Доказательство. Полотенце 4 м × 4 м разделим на 16 равных квадратов 1 м × 1 м. Из условия дырок только 15, по принципу Дирихле следует, что, хотя бы в одном квадрате не будет дырки.
4. Докажите, что если прямая k лежит в плоскости треугольника АВС и не проходит через каждую из его вершин, то она не может пересекать все три стороны треугольника.
Доказательство. Прямая k делит плоскость на две полуплоскости (рис.2). Три вершины треугольника АВС принадлежат двум полуплоскостям. Из этого следует, что по принципу Дирихле хотя бы две вершины лежат в одной полуплоскости относительно прямой k ипрямая не пересекает сторону, соединяющую эти вершины.
5. Дан равносторонний треугольник со стороной 2 см, внутрь него бросили 5 бобов. Докажите, что найдутся два боба, расстояние между которыми меньше 1 см.
Доказательство. Разделим треугольник на 4 равных треугольника как показано на рисунке (рис. 3). Стороны построенных треугольников будут равны 1 см. Из условия бросают 5 бобов, значит по принципу Дирихле в один из полученных треугольников попадет хотя бы 2 боба, расстояние между которыми будет меньше стороны треугольника, то есть меньше 1 см.
Для решения задач данного типа нужно выполнить дополнительные построения.
2.4 Решение комбинаторных задач
1. В коробке лежат шарики 4-х разных цветов (белые, черные, синие, красные). Какое наименьшее количество шариков надо вынуть из коробки, чтобы среди них оказались два шарика одного цвета?
2. В бригаде 7 человек и их суммарный возраст – 332 года. Докажите, что из них можно выбрать трех человек, сумма возрастов которых не меньше 142 лет.
Доказательство. Выберем трёх старших членов бригады. Если им вместе 142 года, то хотя бы одному из них больше 47 лет. Если самому младшему из троих 47 лет, то им троим больше 142 лет. Пусть самому младшему из троих 47 лет или меньше, и им троим вместе менее 142 лет. Тогда на долю остальных 4-ых приходится более 332-142=190 лет, разделим 190 на 4-ых, получим 190 = 4 * 47 + 2. Тогда по принципу Дирихле одному из 4-ых больше 47 лет, это противоречит выбору троих самых старших в этой бригаде.
3. Докажите, что в любой момент турнира по шашкам (в котором каждый встречается с остальными участниками по одному разу) найдется два игрока, сыгравшие одинаковое число партий.
4. На контрольной работе 10 школьников решили в сумме 35 задач, причем среди них были решившие ровно одну, ровно две и ровно три задачи. Докажите, что кто-то из них решил не менее 5 задач.
Доказательство. Возьмем одного школьника, решившего ровно одну задачу, одного, решившего ровно две и одного, решившего ровно три. Эти трое решили в сумме 6 задач. Остается еще 7 школьников, решивших в сумме 29 задач. Значит, по обобщённому принципу Дирихле n = 7, k = 4, 7 * 4 + 1 = 29, из этого следует что найдётся кто-то из них, кто решил не менее 5 задач.
На примере данных задач, мы можем сказать, что их решение осуществляется путём выбора каких-либо предметов в нужном колличестве для получения ответа.
Рассмотрев типовые задачи по данной теме, нами были сформулирована последовательность действий для решения задач с применением принципа Дирихле:
1. Определить, что в данной задаче удобно принять за «клетки», а что за «зайцев».
Каждая грань куба раскрашена в чёрный или белый цвет. Докажите, что найдутся две одинаково раскрашенные грани, имеющие общее ребро.
2. При необходимости преобразовать условия задачи в удобный для понимания вид и получить «клетки» и «зайцев».
Данная задача в преобразованиях не нуждается.
3. Выбрать для решения задачи удобную формулировку принципа Дирихле.
Для решения данной задачи выбираем следующую формулировку: «если в n клетках
Продолжение таблицы 1
сидит n + 1 зайцев или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца».
4. Привести условия задачи к выбранной формулировке принципа Дирихле.
«клеток» получилось две, по принципу Дирихле из этого следует что «зайцев» будет 2 + 1 = 3. Так как у нас получилось 3 грани, а цвета всего 2, из этого следует, что какие-то две грани будут одинаково раскрашены.
5. Получаем ответ или результат доказательства.
В ходе проделанной работы были изучены различные научные материалы по данной теме, разобраны и систематизированы типовые задачи: в арифметике, геометрии, теории чисел и комбинаторике. Разобраны разные формулировками данного принципа с их доказательством.
Была обобщена схема решения задач с применением принципа Дирихле и сформулирована последовательность действий для данного класса задач. Задачи были систематизированы и разобраны в соответствии с различным уровнем сложности.
Материал работы будет полезен для самостоятельного изучения при подготовке к математическим олимпиадам.
Список используемых источников
Алимов Ш.А., Колягин Ю.М., Сидоров Ю.В. Алгебра: Учеб. для 9 кл. общеобразоват. учреждений – 16-е изд.– М.: Просвещение, 2011. – 287с.
Алфутова Н. Б, Устинов А. В. Алгебра и теория чисел. Сборник задач для математических школ. — 3-е изд., испр. доп. — М.: МЦНМО, 2009. — 336 с.
БердичевскийВ. Л. Вариационные принципы механики сплошной среды. — М.: Наука, 2005. – 448 с.,
Болодурина И.П., Отрыванкина Т.М., Арапова О.С. и др. Дискретная математика. Часть 1: Учебное пособие — Оренбург: Оренбургский гос. ун-т, 2016. — 108с.
Венков Б.А. Элементарная теория чисел. – ОНТИ НКПТ СССР, 1937. – 222 с.
Виленкин Н.Я. Математика: Учеб. для 5 кл. общеобразоват. учреждений и –24-е изд., испр. – М.: Мнемозина, 2008. –280с.
Виноградов И. М. Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — 2921 с.
Дорогая И.Д. Метод Фурье, симметрии и функция Грина задачи Дирихле — Вестник Балтийского федерального университета им. И. Канта, 2009. — 6с.
Кастрица О.А., Мазаник С.А., Наумович А.Ф. и др. Математический анализ. Ряды и несобственные интегралы: учебное пособие — 392с.
Крепкогорский В.Л. Функциональный анализ: учебное пособие — Казань: КНИТУ, 2014. — 116с.
Мордкович А.Г., Семенов П.В. Алгебра и начала анализа: Учеб. для 11 кл. В 2 ч. Ч. 1. Учебник для общеобразоват. учреждений (проф. уровень) – М.: Мнемозина, 2007. – 287с.
Нигмедзянова А.М. Решение основных краевых задач одного многомерного вырождающегося эллиптического уравнения первого рода с отрицательным параметром методом — Известия ТулГУ. Естественные науки, 2013. — 10с.
Сидоров Ю.В. Алгебра: Учеб. для 7 кл. общеобразоват. учреждений – Под редакцией Ш. А. Алимова. – 18-е изд. – М.: Просвещение, 2011. –224с.
Фарков А.В. Математические олимпиады: методика подготовки: 5-8 классы — Москва: ВАКО, 2012. — 176с.
Хаггарти Р. Дискретная математика для программистов — 2-е изд., исправленное. — Москва: Техносфера, 2012. — 400с.
Чулков П.В. Практические занятия по элементарной математике (2-й курс) — Учебное пособие. – М.: МПГУ, 2012. — 102с.