Творческая работа Принцип Дирихле

ЧИСТЕНСКИЙ УВК «ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА

I - III СТУПЕНЕЙ - ГИМНАЗИЯ»

НАПРАВЛЕНИЕ МАТЕМАТИКА

«ПРИНЦИП ДИРИХЛЕ»

Работу выполнила

ученица 7а класса

Кудрявская Кристина

Научный руководитель

специалист высшей категории

Федоренко Ирина Витальевна

Чистенькое, 2014

СОДЕРЖАНИЕ

ВВЕДЕНИЕ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1. ПРИНЦИП ДИРИХЛЕ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.1 ПРИМЕНЕНИЕ ПРИНЦИПА ДИРИХЛЕ ПРИ РЕШЕНИИ ЛОГИЧЕСКИХ ЗАДАЧ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 ПРИМЕНЕНИЕ ПРИНЦИПА ДИРИХЛЕ ПРИ РЕШЕНИИ ЗАДАЧ ГЕОМЕТРИЧЕСКОГО СОДЕРЖАНИЯ . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

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

ВЫВОДЫ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

СПИСОК ЛИТЕРАТУРЫ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

ВВЕДЕНИЕ

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

Цель работы:

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

Задачи:

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

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

- Научиться составлять и решать задачи по данной теме.

1. ПРИНЦИП ДИРИХЛЕ

Любой, даже незнакомый с математикой человек, понимает, что рассадить (n + 1)-го зайца в n клеток так, чтобы в каждой клетке было не больше одного зайца, нельзя. Иначе говоря, если в n клетках находится n + 1 заяц, то по крайне мере в одной клетке сидит не меньше двух зайцев.

Если n + 1 предмет разложено в n ящиков, то найдутся два предмета, которые лежат в одном ящике.

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

Более общее формулирование принципа Дирихле:

Если nk + 1 предмет разложено в n ящиков, то по крайне мере в одном из ящиков находится не меньше, чем k + 1 предмет.

Для доказательства пронумеруем ящики числами 1, 2, ..., n. Пусть x_i число предметов, которые находятся в ящике с номером i.

По условию x₁ + x₂ +… + x_n= nk + 1.

Допустим, что x₁ ≤ k, x₂ ≤ k, … , x_n ≤ k. Тогда x₁ + x₂ +… + x_n ≤ nk, что противоречит условию. Т.е. наше допущение неправильно, значит существует хотя бы одно i такое, что x_i ≥ k + 1.

1.1 ПРИМЕНЕНИЕ ПРИНЦИПА ДИРИХЛЕ ПРИ РЕШЕНИИ ЛОГИЧЕСКИХ ЗАДАЧ

Рассмотрим различные нематематические применения принципа Дирихле.

Задача 1.1

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

Решение.

Заметим, что из двух букв можно создать 2∙2=4 различных пары инициалов. (если это, например, буквы А и Б, то имеем А.А., А.Б., Б.А., Б.Б.)

В русском алфавите 33 буквы. Т.к. инициалы не могут начинаться с ь и ъ, то существует только 31 буква, которая может входить в состав инициалов. Поэтому можно создать 31∙31=961 различных пар инициалов.

Возьмем 961 «ящик» и на каждом из них нанесем пару инициалов. Напишем для каждого ученика его инициалы на карточке и каждую карточку положим в тот «ящик», на котором написаны именно эти инициалы. Поскольку раскладываем 962 карточки в 961 «ящик», то, соответственно принципу Дирихле, по крайне мере в одном «ящике» будет не меньше одной карточки. Следовательно, по крайне мере у двух учеников совпадают инициалы. Что и требовалось доказать.

Задача 1.2

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

Решение.

Каждый из 12 шахматистов может сыграть 11 партий.

Рассмотрим два случая.

1) в данный момент есть шахматист, который не сыграл еще ни одной партии;

2) в данный момент нет шахматиста, который не сыграл еще ни одной партии.

Пронумеруем шахматистов и запишем на карточках для каждого шахматиста число партий, которое он сыграл на данный момент. Получим 12 карточек.

В первом случае на каждой карточке будет записано одно из чисел от 0 до 10 (шахматиста, который сыграл все 11 партий нет, т.к. известно, что есть шахматист, который не сыграл еще ни одной партии). Среди 12 карточек, на которых записано одно из11 чисел, есть по крайне мере две одинаковых. Таким образом, в первом случае утверждение задачи справедливо.

Во втором случае на каждой карточке будет одно из чисел от 1 до 11, и снова по принципу Дирихле утверждение задачи справедливо.

Задача 1.3

В классе 29 учеников. Во время диктанта один ученик допустил 13 ошибок, а все остальные ученики - меньше. Доказать, что в классе найдутся по крайне мере 3 ученика допустивших одинаковое количество ошибок.

Решение.

Создадим «ящики». На каждом «ящике» напишем число, соответствующее количеству ошибок, допущенных в диктанте. Таких «ящиков» будет 14. На каждом из них записано одно из чисел от 0(нет ошибок) до 13.

Запишем на карточках фамилии учеников (таких карточек будет 29) и будем опускать карточки в «ящики» номер которого соответствует количеству ошибок.

В «ящик» №14 положим только одну карточку. Остальные 28 карточек надо разложить в 13 ящиков.

Поскольку 28 = 13∙2 + 2, значит по крайне мере в одном из «ящиков» будет лежать не меньше 3 карточек, то есть что в классе найдутся по крайне мере 3 ученика допустивших одинаковое количество ошибок. Что и требовалось доказать.

1.2 ПРИМЕНЕНИЕ ПРИНЦИПА ДИРИХЛЕ ПРИ РЕШЕНИИ ЗАДАЧ

ГЕОМЕТРИЧЕСКОГО СОДЕРЖАНИЯ

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

Задача 2.1

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

Решение.

Прямая l разбивает плоскость на две полуплоскости.

Три вершины А, В, С треугольника АВС принадлежат двум полуплоскостям. Следовательно, по принципу Дирихле по крайне мере две вершины лежат в одной полуплоскости относительно прямой l и прямая не пересекает сторону, соединяющую эти вершины.

Задача 2.2

В ковре 4м×4м моль прогрызла 15 дырок. Доказать, что из него можно вырезать коврик1м×1м. не содержащий внутри себя дырок.

Решение.

Ковер 4м×4м можно разделить на 16 равных квадратов 1м×1м. Поскольку дырок только 15, то хотя бы в одном квадрате не будет дырки.

Задача 2.3

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

Решение.

Разделим треугольник на 4 равных треугольника как показано на рисунке. Стороны новых треугольников будут равны 1см.

Поскольку бросают 5 горошин, то в один из полученных треугольников попадет хотя бы 2 горошины, расстояние между которыми будет меньше стороны треугольника, то есть меньше 1см.

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

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

Задача 1

В нашем классе 14 человек. Доказать, что по крайне мере у двух из них день рожденья в одном месяце.

Решение.

Вместо «ящиков» возьмем календарь и будем в него записывать имена одноклассников, которые в этом месяце отмечают день рожденья. Так как месяцев только 12, а учеников 14, то найдется хотя бы два человека у которых день рожденья в одном месяце.

Задача 2

В новом микрорайоне было построено 30 новых домов. 21 из них были двухэтажные, 22 выкрашены в персиковый цвет, у 18 домов крыша красного цвета. Докажите, что на улице обязательно найдется двухэтажный дом персикового цвета с красной крышей.

Решение.

Возьмем 21 карточку и на каждой из них напишем двухэтажный дом. Еще на 22 карточках напишем - персиковый цвет, и на 18 - красная крыша. Всего у нас окажется 21 + 22 + 18 = 61карточка.

Пронумеруем дома от 1 до 30 и будем раскладывать карточки.

Так как 61 = 30∙2 + 1, значит по крайне мере на одном доме будет три карточки. Следовательно, на улице обязательно найдется двухэтажный дом персикового цвета с красной крышей.

Задача 3.

В школе среди трёх седьмых и трёх восьмых классов проводились соревнования по игре «Снайпер». Каждые два класса должны были сыграть между собой одну игру. Доказать, что в любой момент соревнований есть два класса, которые сыграли одинаковое количество игр.

Решение.

Команда каждого класса должна 5 игр.

Рассмотрим два случая.

1) в данный момент есть команда, которая еще не участвовала в соревнованиях;

2) в данный момент каждая команда сыграла хотя бы одну игру.

Возьмем 6 карточек (по количеству команд) и напишем на каждой из них число сыгранных игр.

В первом случае это будут числа от 0 до 4 (всего 5 чисел); во втором случае это будут числа от 1 до 5 (тоже всего 5 чисел).

Так как карточек 6, а чисел 5. То хотя бы на двух карточках будут написаны одинаковые числа. Значит в любой момент соревнований есть два класса, которые сыграли одинаковое количество игр.

Задача 4.

На поляне размером 8м×10м в произвольном порядке посадили 19 деревьев.

Докажите, что в любом случае найдется квадрат со стороной 2м, на котором не растёт ни одно дерево, для того, чтобы установить качели.

Решение.

Данную поляну можно разделить на 20 равных квадратов со стороной 2м.

Так как посажено только 19 деревьев, то обязательно найдется квадрат, внутри которого нет ни одного дерева.

Задача 5.

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

Доказательство.

Ковер можно «Разделить» на 10 квадратов со стороной 1м.

Так как 21 = 10∙2+1, то найдется квадрат со стороной 1м, в котором мышь прогрызла минимум три дырки. Его можно залатать одной заплаткой.

ВЫВОДЫ

Изучив литературу по теме принцип Дирихле, проанализировав виды и типы задач, которые решаются с использованием данного принципа. Я пришла к выводу, что оказывается, не так сложно решать различные задачи на доказательство, которые встречались во время олимпиад по математике. Пожалуй, самым сложным при решении задач является умение определить какая величина в задаче выполняет роль «ящика», а какая «зайца».

Данная тема так увлекла меня, что я решила попробовать самостоятельно составить задачи, аналогичные рассмотренным. По-моему у меня все получилось.

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

СПИСОК ЛИТЕРАТУРЫ

1. Болтянский В. Г. Шесть зайцев в пяти клетках//Квант, - 1997. - №2, - С.17 - 37

2. Вороний О.М. Готуємось до олімпіад з математики. Харків «Основа». -2009

3. Горбачев Н.В. Сборник олимпиадных задач по математике Москва МЦНМО, - 2004

3. Леман А.А. Сборник задач московских математических олимпиад. Москва «Просвещение», - 1965

4. Ядренко М.И. Принцип Дирихле. Харьков «Основа», - 2005