V Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Применения принципа Дирихле в решении некоторых видов логических задач в рамках школьного курса математики
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
I. Введение
Объектом исследования являются способы и методы решения логических задач. Логическая задача – это особый вид задач, который развивает логику, образное и творческое мышление, поэтому часто такие задачи являются олимпиадными. Решение таких задач увлекательное занятие, поскольку для решения большинства из них требуется не только знание определённого программного материала, но и логическое мышление.
Разнообразие логических задач велико, велико и количество их решений. При решении многих задач часто используется метод рассуждения «от противного» и одна из его форм – принцип Дирихле. Способ решения задач с помощью данного принципа и является предметом исследования данной работы.
Гипотеза: принцип Дирихле позволяет решать некоторые логические задачи, которые сложно решать другими способами.
Цель работы: исследование эффективности применения принципа Дирихле в решении некоторых видов логических задач.
Были определены задачи исследования:
раскрыть суть принципа Дирихле;
отобрать и систематизировать задачи, решаемые с помощью принципа Дирихле;
научиться составлять задач, решаемые данным методом.
В ходе научного исследования использовались следующие методы:
изучение литературных источников;
теоретические;
поисковые;
сравнение;
анализ.
Данная работа весьма актуальна, так как принцип Дирихле не рассматривается в учебниках математики, а полученные знания пригодятся для успешного решения олимпиадных задач, сдачи экзаменов и решении практических задач в жизни.
II. Знакомство с принципом Дирихле 1. Смысл принципа Дирихле
В математике существует множество принципов. Некоторые из них достаточно просты и понятны даже новичку, а некоторые требуют определенных объяснений и доказательств. Однако все они весьма эффективны, и их легко можно применять на практике. Одним из них является принцип Дирихле (известный также как принцип голубей/кроликов). Это достаточно простое утверждение, способное помочь в решении многих математических задач.
Данный принцип был сформулирован почётным немецким математиком Иоганном Дирихле ещё в 1834 году. Сегодня его применяют в комбинаторике, а также в математической физике. В переводе с оригинального немецкого он звучит как «принцип ящиков».
Свои исследования учёный проводил с кроликами и контейнерами. Он продемонстрировал, что если поместить, допустим, 5 кроликов в 7 контейнеров, то, по крайней мере, в одном контейнере будет находиться 5/7 от одного животного. Однако кролика нельзя разделить на части, следовательно, хотя бы одна клетка будет пустовать (Приложение, рисунок 1).
Точно так же и в обратную сторону, если кроликов 7, а ящиков 5, то хотя бы в одном из них – 2 кролика (Приложение, рисунок 2).
Отталкиваясь от этого утверждения, математику удалось сформулировать принцип, который обеспечивает успешное решение задач по математике уже многие год.
2. Современная формулировка принципа Дирихле
На сегодняшний день существует несколько разных формулировок данного принципа.
Научная формулировка, объясняющая принцип Дирихле, гласит: если в n ячеек находится n + 1 зайцев, то, по крайней мере, в 1 ячейке будет располагаться больше одного зайца.
Это простое утверждение можно обобщить: если (2n + 1) кролик помещен в n клетках, то, по крайней мере, в одной клетке находятся не менее трех кроликов.
Более общая форма принципа Дирихле, включающая все предыдущие, такова: если (kn + 1) кролик помещен в n клетках, то в одной из клеток находятся не менее (k + 1) кролика; или в эквивалентной форме – нельзя посадить (kn + 1) кролика в n клеток так, чтобы в каждой клетке находилось не более k кроликов.
В действительности такой простой и понятный принцип значительно облегчает решение задач по математике и доказательства многих трудоемких теорем. Просто необходимо учитывать, что зайцев и ячейки можно легко заменить на математические предметы и объекты (цифры, точки, отрезки, фигуры и т. д.).
III. Применение принципа Дирихле для решения различных задач 1. Классификация задач, решаемых с помощью принципа Дирихле
Прежде чем применять принцип Дирихле в решении логических задач, необходимо понять, какие задачи к ним относятся.
К логическим задачам относят такие, при решении которых главное, определяющее – это отыскание связи между фактами, сопоставление их, построение цепочки рассуждений для достижения цели.
Хотя современные логические задачи по математике предъявляют к ученикам творческие требования и предполагают нестандартные подходы, решение через принцип Дирихле не всегда такое простое и понятное. Иногда очень трудно определить, какую величину считать животным, а какую – клеткой. При этом все равно нельзя определить, в какой именно клетке будет находиться объект. То есть можно просто доказать существование такой ячейки, но нельзя конкретизировать её.
Таким образом, можно определить следующий вид задач, к которым применим принцип Дирихле:
задачи, которые в буквальном смысле не являются математическими с точки зрения школьного курса математики (т.е. требующими получения конкретного измеримого ответа);
в то же время требуют для своего решения формулирования суждений (высказываний), построения умозаключений и их цепочек;
ответом является установление факта, или его опровержение.
На основании данного определения выберем такие задачи в разных разделах математической подготовки учащихся.
2. Принцип Дирихле и арифметика
Задача 1. В школе учится 962 ученика. Доказать, что по крайне мере у двух учеников совпадают инициалы.
Решение.
Заметим, что из двух букв можно создать 2∙2=4 различных пары инициалов. (если это, например, буквы А и Б, то имеем А.А., А.Б., Б.А., Б.Б.)
В русском алфавите 33 буквы. Т.к. инициалы не могут начинаться с ь и ъ, то существует только 31 буква, которая может входить в состав инициалов. Поэтому можно создать 31∙31=961 различных пар инициалов.
Возьмём 961 «ящик» и на каждом из них нанесём пару инициалов. Напишем для каждого ученика его инициалы на карточке и каждую карточку положим в тот «ящик», на котором написаны именно эти инициалы. Поскольку раскладываем 962 карточки в 961 «ящик», то, соответственно принципу Дирихле, по крайне мере в одном «ящике» будет не меньше одной карточки. Следовательно, по крайне мере у двух учеников совпадают инициалы.
Задача 2. В классе 29 учеников. Во время диктанта один ученик допустил 13 ошибок, а все остальные ученики – меньше. Доказать, что в классе найдутся по крайне мере 3 ученика допустивших одинаковое количество ошибок.
Решение.
Создадим «ящики». На каждом «ящике» напишем число, соответствующее количеству ошибок, допущенных в диктанте. Таких «ящиков» будет 14. На каждом из них записано одно из чисел от 0(нет ошибок) до 13.
Запишем на карточках фамилии учеников (таких карточек будет 29) и будем опускать карточки в «ящики» номер которого соответствует количеству ошибок.
В «ящик» №14 положим только одну карточку. Остальные 28 карточек надо разложить в 13 ящиков.
Поскольку 28 = 13∙2 + 2, значит по крайне мере в одном из «ящиков» будет лежать не меньше 3 карточек, то есть что в классе найдутся по крайне мере 3 ученика допустивших одинаковое количество ошибок.
3. Принцип Дирихле и делимость чисел
Задача 1. Доказать, что среди шести любых целых чисел найдутся два, разность которых делится на 5.
Решение.
При делении на 5 возможных 5 разных остатков:
0; 1; 2; 3; 4. Так как чисел 6, то найдутся 2 числа с одинаковыми остатками; их разность разделится на 5.
Задача 2. Доказать, что из любых трёх целых чисел можно найти два, сумма которых делится на 2.
Решение.
Среди трёх целых чисел обязательно найдутся два числа одинаковой чётности (так как чисел 3, а классов – чётных и нечётных чисел – лишь два). Сумма их делится на 2 .
Задача 3. Верно ли, что среди любых семи натуральных чисел найдутся три, сумма которых делится на 3?
Решение.
При делении на 3 есть три остатка: 0, 1, 2.
Так как 7 = 3 ∙ 2 + 1, то найдутся три числа, дающие один остаток.
4. Принцип Дирихле и геометрия
Задача 1. Прямая k проходит через плоскость треугольника ABC, однако не пересекает ни одну его вершину. Необходимо доказать, что она не может пересекать три его стороны.
Решение.
Представим, как прямая k разбивает треугольник на две плоскости, назовём их s1 и s2. Будем считать, что s1 и s2 открытые, то есть не содержащие прямую k. Ну а сейчас – самое время применить принцип Дирихле. Задачи с решениями могут продемонстрировать, что под кроликами и ячейками в современных условиях подразумеваются разнообразные объекты. Так, вместо зайцев мы подставим вершины треугольника, а вместо ячеек – полуплоскости. Поскольку проведенная прямая k не пересекает ни одну из вершин, то каждая из них находится в той или иной плоскости. Но поскольку вершины в треугольнике три, а плоскости у нас всего две (s1 и s2), то одна из них будет содержать две вершины. Предположим, что это вершины A и B, и находятся они в полуплоскости s2 (то есть лежат по одну сторону от k). В таком случае отрезок АВ не пересекает прямую k. То есть в треугольнике есть сторона, которую прямая k не пересекает.
Задача 2. Внутри равностороннего треугольника со стороной 2 см бросили 5 горошин. Доказать, что найдутся две горошины, расстояние между которыми меньше 1см.
Решение.
Разделим треугольник на 4 равных треугольника как показано на рисунке (Приложение, рисунок 3). Стороны новых треугольников будут равны 1см.
Поскольку бросают 5 горошин, то в один из полученных треугольников попадет хотя бы 2 горошины, расстояние между которыми будет меньше стороны треугольника, то есть меньше 1см.
5. Принцип Дирихле и комбинаторные задачи
Задача 1. Допустим, вокруг округлённого стола стоят на равном расстоянии друг от друга m флажков разных стран, а за столом сидят m представителей от каждой страны, причём каждый из них расположился рядом с чужим флажком. Нужно доказать, что при определённом вращении стола хотя бы двое из представителей окажутся возле своих флажков.
Решение.
Получается, что существует m–1 способов развернуть стол так, чтобы изменилось взаиморасположение представителей и флажков (если исключить начальное размещение стола), но при этом остается m представителей. Применим к решению утверждение Дирихле и обозначим, что представители выступают кроликами, а определенные положения стола при вращении – ячейками. При этом нужно провести аналогию между расположением представителя рядом с соответствующем флажком и заполненными ячейками. То есть положительный результат (1 представитель размешается возле своего флажка) равносилен результату «кролик оказывается в клетке». Мы понимаем, что у нас на одну ячейку меньше, чем нужно (m–1), а значит, в одной из них окажется как минимум 2 кролика. При этом не исключены ситуации, что какая-то клетка будет пустой (ни один представитель не совпал с флажком), а в какой-то клетке окажется два, три или даже больше кроликов (два, три и больше представителей совпадут с флажками). Таким образом, при одном определенном вращении как минимум два представителя очутятся возле своих флажков (как минимум два кролика попадут в одну ячейку). Приступая к решению такой задачи, важно понимать, что начальное положение – это тоже ячейка, но по условию задачи она заведомо пустует, поэтому мы уменьшаем общее количество на 1 (m–1).
IV. Авторские задачи
Изучив классические задачи, которые решаются с помощью принципа Дирихле, я решила попробовать самостоятельно составить несколько подобных задач.
Задача 1. В нашем классе 29 человек. Доказать, что по крайне мере у трех из них день рожденья в одном месяце.
Решение.
Вместо «ящиков» возьмём календарь и будем в него записывать имена одноклассников, которые в этом месяце отмечают день рожденья. Так как месяцев только 12, а учеников 29, то справедливо равенство 29 = 12∙2 + 5, значит найдётся хотя бы три человека у которых день рожденья в одном месяце.
Задача 2. Для команды лыжников было сшито 20 новых костюмов. 15 из них были мужскими, 14 синего цвета, у 12 костюмов шапочки белого цвета. Докажите, что среди всех костюмов найдется мужской костюм синего цвета с белой шапочкой.
Решение.
Возьмём 15 карточек и на каждой из них напишем мужской костюм. Еще на 16 карточках напишем – синий цвет, и на 12 – белая шапочка. Всего у нас окажется 15 + 14 + 12 = 41 карточка.
Пронумеруем костюмы от 1 до 20 и будем раскладывать карточки.
Так как 41 = 20∙2 + 1, значит по крайне мере на одном костюме будет три карточки. Следовательно, среди всех костюмов найдется мужской костюм синего цвета с белой шапочкой.
Задача 3. В городе Реутов 99 989 жителей, на голове у каждого не больше 90 000 волос. Докажите, что имеются, по крайней мере, 2 человек с одинаковым числом волос на голове.
Решение.
Действительно, выдадим каждому человеку ярлык, на котором написано число волос на его голове (таких ярлыков не больше 90 000). Разобьем теперь все население города на группы, в каждую из которых входят люди с одинаковым числом волос на голове. Если теперь предположить, что в каждой группе меньше 2 человек, то это будет означать, что всего в городе не больше 90 тыс. человек, что противоречит условию задачи. Отметим, что при решении этой задачи мы фактически доказали принцип Дирихле, где в качестве «клеток» служат группы людей с одинаковым числом волос, а в качестве «кроликов» – жители города.
Задача 4. Для поездки на экскурсию заказали автобус с 22 местами, сблокированными по 2. На экскурсию едет 12 учеников 6 “Б” класса и 10 учеников 6 “Г” класса. Могут ли в одном блоке оказаться ученики одного класса?
Решение.
Определим, сколько блоков сидений в автобусе 22:2=11.
Возьмём 12 карточек с надписью 6 “Б” и 10 карточек с надписью “Г” и разложим по местам автобуса. Т.к. блоков 11, то в одном из них обязательно окажется две карточки одного класса.
Задача 5. Докажите, что среди любых последовательных 7 натуральных чисел найдутся хотя бы 3, сумма которых делится на 3.
Решение.
При делении на 3 возможны остатки 0, 1, 2.
Запишем карточки с выбранными натуральными числами и разложим их в стопки в соответствии с остатками от деления на 3.
Соответственно, в одной из стопок будет 3 числа, сумма которых будет делиться на 3.
V. Выводы
1. В результате проведённых исследований удалось классифицировать и выявить в школьном курсе математики логические задачи, решаемые с помощью принципа Дирихле.
2. На основании проведённого анализа показана применимость принципа Дирихле к решению учениками некоторых типов логических задач.
3. По итогам проведённой работы гипотеза исследования подтвердилась, цель исследования считаем достигнутой.
VI. Заключение
В рамках исследования были изучены различные источники, описывающие историю создания и математическую сущность принципа Дирихле. Полученные знания позволили уяснить сущность предлагаемой структуры деятельности по доказательству математических фактов, разобраться в основном определении и определении принципа Дирихле в теории чисел.
В результате проведённого анализа структуры деятельности при применении принципа Дирихле удалось выявить требования к виду задач, позволяющие систематизировать задачи в разрезе разделов математической подготовки учащихся.
На основе проведённой систематизации были проанализированы и отобраны некоторые задачи по разделам:
арифметика;
делимость чисел;
геометрия;
комбинаторика.
На основе накопленных знаний и полученного опыта были составлены задачи, решение которых возможны с помощью принципа Дирихле.
По итогам проведённой работы гипотеза исследования подтвердилась, цель исследования считаем достигнутой.
VII. Список используемых источников
1. Болтянский В. Г. Шесть зайцев в пяти клетках//Квант, – 1997. - №2, – С.17 – 37
2. Канин Е. С. Логические задачи // Математика для школьников. – 2011. – № 3. – С. 17–30.
3. Ненашев М. И. Введение в логику. – Киров, 1997. – 240 с.
4. Ончукова Л. В. Введение в логику. Логические операции: учебное пособие для 5 класса. – Киров, 2004. – 124 с.
5. Ядренко М.И. Принцип Дирихле. Харьков «Основа», – 2005.
VIII. Приложение
Рисунок 1. Смысл принципа Дирихле. Прямое утверждение.
Рисунок 2. Смысл принципа Дирихле. Обратное утверждение.
Рисунок 3. Принцип Дирихле и геометрия. Задача 2.