Статья по математике Принцип Дирихле

Занятие математического кружка в VII классе «Принцип Дирихле».
Многие вещи нам непонятны не потому,
что наши понятия слабы; но потому, что сии
вещи не входят в круг наших понятий.
К. Прутков
Аннотация. В статье представлена разработка занятия математического кружка по теме «Принцип Дирихле» в 7 классе, рассчитанная на 2 часа. В данной статье рассматриваются различные формулировки принципа Дирихле, а также приводятся конкретные примеры применения данного принципа при решении задач разного типа.
Ключевые слова: концепция математического образования, дополнительное математическое образование (ДМО), математический кружок, принцип Дирихле, математические доказательства
Согласно Концепции математического образования значительную роль играет воспитательная составляющая деятельности школы. В круг ее основных задач входит привлечение учащихся в различные мероприятия, направленные на всестороннее развитие творческих и индивидуальных способностей каждого обучающегося, а также на максимальное удовлетворение их потребностей. В настоящее время, как известно, творческий процесс заслуживает самого пристального внимания, поскольку общество нуждается в массовом совершенствовании уже известного, в отказе от устойчивых и привычных, но пришедших в противоречие с имеющимися потребностями и возможностями форм. А это в свою очередь означает возрастание роли внеурочной деятельности. Опытная работа П. М. Горева и его собственная практика обучения школьников математике в ДМО показала, что одной из важных форм организации работы в ДМО являются занятия математического кружка [3].
Вопросы, рассматриваемые на занятиях кружка, выходят за пределы объема обязательных знаний, но вместе с тем они плотно примыкают и тесно взаимосвязаны с основными вопросами программного материала. В этой статье предлагается разработка внеклассного занятия по математике в VII классе «Принцип Дирихле».
Цель занятия: Познакомить учащихся с новым математическим методом решения задач, не рассматриваемом в курсе изучения математики, показать на конкретных примерах применение принципа Дирихле при решении задач.
Вступительная беседа. Из всех областей знаний, известных человечеству, математика является наиболее точной и правильной. И главное ее отличие от других наук – наличие неопровержимых доказательств, являющихся эталоном бесспорности. Порог убедительности математических доказательств значительно выше, чем у других наук.
Давайте, вспомним, что же такое доказательство? (Ответы учеников). Доказательство – это такое рассуждение, которое убеждает нас настолько, что мы готовы убеждать других, используя тоже рассуждение [9]. Математические доказательства бывают прямые и косвенные. Используя прямое доказательство, нам нужно доказать существование объекта с заданными свойствами. Рассмотрим пример прямого доказательства: чтобы доказать, что неравенство имеет решение, нам нужно найти множество всех значений переменной, при которых оно верно. Но также существуют и косвенные доказательства – это, когда обоснование того, что объект существует, происходит без прямого указания на сам объект. Примером косвенного доказательства является логический метод рассуждения - «от противного». Мы рассмотрим одну из форм этого метода – принцип Дирихле.
Принцип назван в честь немецкого математика Питера  Густава  Дирихле (1805-1895), который успешно применял его к доказательству арифметических утверждений.
В связи со сложившейся традицией принцип Дирихле объясняют на примере «зайцев и клеток». Если мы хотим применить данный принцип при решении конкретной задачи, то в этом случае необходимо разобраться, что мы будем принимать – за «клетки», а что – за «зайцев» [1]. Это обычно является самым трудным на этапе доказательства. В английском и некоторых других языках утверждение известно как “принцип голубей и ящиков” (англ. Pigeonhole principle), когда объектами являются голуби, а контейнерами — ящики.
46996351499235В шутливой форме этот принцип гласит: «Нельзя посадить семерых зайцев в три клетки, чтобы в каждой клетке находилось не более двух зайцев» [8].
Наиболее распространенная формулировка принципа Дирихле состоит в следующем: «Если в n клеток посадить n+1 зайцев, то найдется хотя бы одна клетка, в которой находятся не менее чем 2 зайца».
Обобщенный принцип Дирихле: «Если в n клеток посадить kn+1 зайцев, то найдется хотя бы одна клетка, в которой находятся не менее чем k+1 заяц».
Рассмотрим примеры различных задач, решаемых с помощью этого принципа.
Задачи для обсуждения на уроке.
Применение принципа Дирихле при решении логических задач.
Но, спросите вы, разве о зайцах идет речь в задачах?
Задача 1.
В городе 15 школ. В них обучается 6015 школьников. В концертном зале городского Дворца культуры 400 мест. Докажите, что найдется школа, ученики которой не поместятся в этом зале.
Решение.
Предположим, что в каждой школе не более 400 учеников. Значит, в 15 школах будет 15*400= 6000 учеников. Но, по условию, в школах обучается 6015 человек. Значит, найдется школа, в которой больше 400 учеников. Поэтому ученики этой школы не поместятся в зале, в котором 400 мест.
Задача 2.
В хвойном лесу растет миллион елей. На каждой ели - не более 600000 иголок. Доказать, что существуют хотя бы две ели с одинаковым числом иголок.
Решение.
Перед нами миллион «зайцев» - елей и, увы, всего лишь 600001 клетка с номерами от 0 до 600000. Каждый «заяц» - ель, сажается нами в клетку с номером, равным количеству иголок на этой ели. Так как «зайцев» гораздо больше, чем клеток, то в какой-то клетке сидит по крайней мере два «зайца» - если бы в каждой сидело не более одного, то всего «зайцев» - елей было бы не более 600001. Но ведь, если два «зайца» - ели, сидят в одной клетке, то количество иголок у них одинаково [2].
Обратите внимание на то, что формулировки этих задач носят тот же налет расплывчатости вывода, что и сам принцип Дирихле. Часто именно такие вопросы решаются с помощью этого принципа.
Применение принципа Дирихле при решении задач на размещения.
Задача 3.
Можно ли вывезти из завода 50 деталей, массы которых соответственно равны 370, 372, 372, …, 468 кг на семи трехтонках?
 Решение.
 Если бы это удалось осуществить, то на какую-нибудь трехтонку нагрузили бы 8 камней, поскольку 7 ∙ 7 + 1 = 50, потому по принципу Дирихле даже при равномерном распределении по 7 деталей на каждую трехтонку получим в избытке 1 деталь. Но даже 8 легких деталей составляют в сумме S = 370 + 372 + 374 + ... + 384 = 3016 кг> 3т. Нельзя.
          Отметим, что общая масса всех деталей, как не трудно подсчитать, составляет 20950 кг, а на семь трехтонок можно нагрузить одновременно 21т. Поэтому складывается впечатление, что ответ на вопрос задачи должен быть положительным. Однако это было бы возможно, если бы мы раздробили детали.
Несмотря на совершенную очевидность этого принципа, его применение является весьма эффективным методом решения задач, дающим во многих случаях наиболее простое и изящное решение. С помощью принципа Дирихле обычно доказывается существование некоторого объекта, не указывая, вообще говоря, алгоритм его нахождения и построения. Приводимые ниже задачи показывают, что природа «зайцев» и «клеток» в различных задачах может сильно отличаться друг от друга.
Применение принципа Дирихле при решении геометрических задач.
Рассмотрим геометрические задачи, которые опираются на дискретный принцип Дирихле.
Задача 4.
Внутри равностороннего треугольника со стороной 2см бросили 5 горошин. Доказать, что найдутся две горошины, расстояние между которыми меньше 1см.
-3962408166735Решение.
Разделим треугольник на 4 равных треугольника как показано на рисунке (рис.1). Стороны новых треугольников будут равны 1см.
Поскольку бросают 5 горошин, то в один из полученных треугольников попадет хотя бы 2 горошины, расстояние между которыми будет меньше стороны треугольника, то есть меньше 1см.
Задача 5.
Доказать, что если прямая l, расположенная в плоскости треугольника АВС, не проходит ни через одну из его вершин, то она не может пересечь все три стороны треугольника [1].
Решение.
46615352680335Полуплоскости, на которые прямая l разбивает плоскость треугольника АВС, обозначим за g1 и g2, эти полуплоскости будем считать открытыми (то есть не содержащими точек прямой l). Вершины рассматриваемого треугольника (точки А, В, С) будут «зайцами», а полуплоскости g1 и g2 будут «клетками». Каждый «заяц» попадает в какую- нибудь «клетку» (ведь прямая l не проходит ни через одну из точек А, В, С). Так как «зайцев» три, а «клеток» только две, то найдутся два зайца, попавшие в одну «клетку»; иначе говоря, найдутся такие две вершины треугольника АВС, которые лежат в одной полуплоскости (рис.2). Пусть, скажем, точки А и В находятся в одной полуплоскости, то есть лежат по одну сторону от прямой l. Тогда отрезок АВ не пересекается с l. Итак, в треугольнике АВС нашлась сторона, которая не пересекается с прямой l.
Современные примеры решения задач демонстрируют, что животными и клетками могут выступать совершенное различные математические предметы.
Применение принципа Дирихле при решении задач на раскраски.
Задача 6.
Плоскость раскрашена в два цвета. Докажите, что найдутся две точки одного цвета на расстоянии 1 метр друг от друга [5].
Решение.
Рассмотрим вершины равностороннего треугольника со стороной 1 м. Если две точки разного цвета, то третья обязательно либо первого, либо второго, значит, мы нашли две точки одного цвета.
Задача 7.
Каждая грань куба раскрашена в чёрный или белый цвет. Доказать, что найдутся одинаково раскрашенные грани, имеющие общее ребро [6].
Решение.
Рассмотрим любую вершину куба. В ней пересекаются три грани. Примем за "клетки" цвета, а за зайцев грани, пересекающиеся в одной вершине (их три). Поэтому согласно принципу Дирихле найдутся два "зайца" в одной "клетке", а это и означает, что найдутся две грани имеющие общее ребро (так как они имеют общую точку) и окрашенные одинаково.
Применение принципа Дирихле в теории чисел.
Рассмотрим примеры, когда при решении задач на делимость чисел используют принцип Дирихле.
Задача 8.
Докажите, что среди чисел, состоящих из цифр 3, найдется число, делящееся на 17 [5].
Решение.
Рассмотрим 17 чисел с разным количеством цифр: 3, 33, 333, 3333, … Предположим, что ни одно из них не делится на 17. При этом могут получаться 16 различных остатков: 1, 2, 3, … 16. Значит, среди наших чисел есть два числа с одинаковым остатком при делении на 17. Разность этих чисел делится на 17, и это число вида 333 … 000… (сначала несколько троек, потом нули). Заметим, что 10 взаимно просто с 17, значит, если с конца убрать нули, то получившееся число тоже будет делиться на 17. Но оно состоит из цифр 3. Значит, мы нашли искомое число.
Достаточно много задач разной сложности можно решить через принцип Дирихле. Задачи с решениями разнообразных математических и логических вопросов достаточно часто опираются на этот принцип.
Задачи для самостоятельного решения (в классе или дома).
В мешке лежат шарики двух цветов: чёрного и белого. Какое наименьшее число шариков нужно достать из мешка не глядя, чтобы среди них оказались ровно два шарика одного цвета? [7]
В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.
На собеседование пришли 65 школьников. Им предложили 3 контрольные работы. За каждую контрольную ставилась одна из оценок: 2, 3, 4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на всех контрольных? [4]
Несколько дуг окружности покрасили в синий цвет. Сумма длин окрашенных дуг меньше длины окружности. Докажите, что существует диаметр, оба конца которого не окрашены [7].
Докажите, что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками [7].
Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6× 6 из чисел +1, −1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино [4].
Докажите, что среди любых пятнадцати натуральных чисел есть два числа, разность которых делится на 14 [5].
Вывод:
Принцип Дирихле является весьма эффективным методом решения задач. Но для его применения на первых этапах изучения темы надо при решении каждой конкретной задачи научиться определять, какой объект считать зайцем, а какой — клеткой, при этом следить за тем, чтобы зайцев всегда было больше, чем клеток; а затем научиться пользоваться фактом наличия в одной клетке двух зайцев, и делать необходимые выводы.Ссылки на источники.
Андреев А. А., Горелов Г. Н., Люлев А. И., Савин А. Н. Принцип Дирихле. Учебное издание.Серия А: Математика. Вып. 1. — Самара: Пифагор, 1997. — 21 с., ил.
Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. – Киров: АСА, 1994.
Горев П. М. Система внеклассной работы по математике в средней школе № 21 города Кирова / П. М. Горев // Российские регионы: проблемы, суждения, поиск путей развития: тезисы IV межрегиональной научно-практической конференции. – Киров: ВСЭИ, 2001. – С. 174.
Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи / Под ред. В. О.Бугаенко.|4-е изд., стереотип.|М.: МЦНМО,2008.| 96 c.
Коннова Е.Г. Математика. Поступаем в вуз по результатам олимпиад. 5 – 8 класс. Часть 1. /издание 4-е/ Под редакцией Ф.Ф.Лысенко. – Ростов-на-Дону: Легион; Легион –М, 2010. – 112 с. – (Готовимся к олимпиаде).
Летчиков А.В. Принцип Дирихле. Задачи с указаниями и решениями: Учебное пособие. Ижевск: Изд – во Удм. ун-та, 1992. 108с.
Севрюков П. Ф. Школа решения олимпиадных задач по математике. — М. : Илекса; Ставрополь: Сервисшкола, 2012. — 176 с.
Спивак А.В. Математический праздник. – М.: Бюро Квантум, 2004. – 288 с. – ( Библиотечка «Квант». Вып. 88)Успенский В. А. Простейшие примеры математических доказательств.— М.: Изд-во МЦНМО, 2009.—56 с.