Принцип Дирихле

I городской научно-практический марафон «Шажок в науку»

I этап

СЕКЦИЯ МАТЕМАТИКИ

Принцип Дирихле.

Выполнена учеником 6 класса

Муниципального образовательного учреждения

 «Основная общеобразовательная школа №223»

г.Заречного

Лившицом Григорием

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

учитель математики

 Жилякова Т.Н.

2009 год

Оглавление:

                                                                                                                                            Стр.                                                        

Введение.

Многие вещи нам непонятны не потому,

что наши понятия слабы; но потому, что сии

вещи не входят в круг наших понятий.

Козьма Прутков

Математика – один из главных школьных предметов. Умение решать задачи, особенно олимпиадные, всегда являлось одним из показателей математической одаренности ученика. Что же такое олимпиадные задачи? Существует такая трактовка: олимпиадные задачи – это задачи, при решении которых используются специальные методы, как правило, не рассматриваемые в школе на уроке.  Значит, решение таких задач способствует развитию не только интеллектуальных способностей учащихся, но развивает их творческие способности и познавательный интерес.  В данной работе подробно изучается принцип Дирихле, который позволяет находить верное решение в нестандартной ситуации.

Интерес к данному принципу возник при решении следующей задачи:

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

Итак, тема данной работы: Принцип Дирихле.

Объект исследования – сам принцип Дирихле и его формулировки.

Предмет исследования – задачи, решаемые с использованием принципа.

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

Поэтому данная работа является обобщением возможностей применения на практике различных формулировок принципа.

Задачи исследования:

1. Изучить различные формулировки принципа Дирихле.
2. Подобрать и решить ряд задач на применение этого принципа и его возможных формулировок.
3. Создать буклет с набором  задач по данной тематике.

1. Принцип Дирихле.

1.1. История возникновения принципа Дирихле

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

1.2.Формулировки принципа Дирихле.

В несерьезной форме принцип Дирихле гласит: «Нельзя посадить 7 кроликов в 3 клетки, чтобы в каждой было не больше 2 кроликов».

Существует несколько формулировок данного принципа.

1. «Если в n клетках сидит m зайцев, причем m >n, то хотя бы в одной клетке сидят, по крайней мере, два зайца».

Доказывается данный принцип Дирихле методом доказательства от противного:

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

2. «Пусть в n клетках сидят m зайцев, причем n > m. Тогда найдется хотя бы одна пустая клетка».

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

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

3.  «Если m зайцев сидят в n клетках, то найдется клетка, в которой не менее m/n зайцев».

Не надо бояться дробного числа зайцев – если получается, что в ящике не меньше 7/3 зайцев, значит, их больше двух.

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

Допустим, что в каждой клетке число зайцев меньше, чем m/n.. Тогда в n клетках вместе зайцев меньше, чем n • (m/n) = m. Противоречие!

4. «Если в n клетках сидят m зайцев и m > kn + 1 , то в какой-то из клеток сидят, по крайней мере, k + 1 заяц» (обобщенный принцип)

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

Пусть не найдется такой клетки, то есть  в каждой из n клеток сидят по k зайцев, тогда зайцев должно быть  k•n, а по условию зайцев как минимум на одного больше. Пришли к противоречию с условием. Значит, есть клетка, в которой сидят k + 1 заяц.

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

На первый взгляд, непонятно, почему это совершенно очевидное предложение, тем не менее, является мощным математическим методом решения задач, причем самых разнообразных. Всё дело оказывается в том, что в каждой конкретной задаче нелегко понять, что же здесь выступает в роли «зайцев», а что — в роли «клеток». И почему надо, чтобы «зайцев» было больше, чем «клеток». Выбор «зайцев» и «клеток» часто неочевиден. Далеко не всегда по формулировке задачи можно определить, что следует применить принцип Дирихле.

Таким образом, применяя данный метод, надо:

1)   определить, что удобно в задаче принять за «клетки», а что за «зайцев»;    

2)   получить «клетки». Чаще всего «клеток» меньше (больше), чем «зайцев» на одну;

3)   выбрать для решения требуемую формулировку принципа Дирихле.

2. Применение принципа Дирихле

Попробуем решить задачи с применением этого метода.

1. В классе 35 учеников. Можно ли утверждать, что среди них найдутся хотя бы два ученика, фамилии которых начинаются с одной буквы.

«ЗАЙЦЫ» - 35 учеников

«КЛЕТКИ»- Буквы русского алфавита. Исключая Ъ,Ь,Ы, таких букв 30.

Задача свелась к тому, чтобы рассадить 35 зайцев в 30 клеток. Количество зайцев больше количества клеток. Используя принцип Дирихле (формулировка 1), можно сделать вывод, что найдутся хотя бы 2 ученика, фамилии которых начинаются с одной буквы.

Или от противного: Пусть каждый ученик начальной буквой своей фамилии имеют различные буквы алфавита. Так как учеников 35, то и букв в алфавите должно быть не меньше. А мы точно знаем, что их 33. поэтому такая ситуация невозможна. Значит,  будут существовать хотя бы два ученика, чьи фамилии начинаются с одной буквы.

2. На дискотеку в студенческое общежитие, в котором 42 комнаты, пришли 36 гостей. Докажите, что найдется комната, в которую не пришел ни один гость.

«ЗАЙЦЫ» - 36 гостей

«КЛЕТКИ»- 42 комнаты.

Теперь необходимо рассадить 36 «зайцев» в 42 «клетки». Так как «зайцев» меньше, чем «клеток», то, используя принцип Дирихле (формулировка 2), можно сделать вывод, что найдется хотя бы одна пустая комната. На самом деле их как минимум 42-36=6.

Или от противного: Пусть в каждую комнату пришел гость, тогда гостей в общежитии должно быть как минимум 42, что противоречит условию. Значит, найдется комната, в которую не пришел ни один гость.  

3. В классе 40  учеников. Докажите, что среди них найдутся 4 ученика, отмечающие день рождения в одном месяце.

«ЗАЙЦЫ» - 40 учеников

«КЛЕТКИ»- 12 месяцев

Нам нужно рассадить 40 «зайцев» в 12 «клеток». Используя принцип Дирихле (формулировка 3), можем сделать вывод, что найдется «клетка», в которой сидят не менее 40/12=3 1/3 «зайцев», то есть как минимум 4 «зайца». Значит, можно утверждать, что найдутся 4 ученика, отмечающие день рождения в одном месяце.

Или от противного: Пусть нет 4 учеников, отмечающих день рождения в одном месяце. Тогда их должно быть 3, получается, что в классе должно быть не больше  12*3=36 учеников, что противоречит условию задачи.

4. В магазин привезли 26 ящиков с яблоками трех сортов, причем в каждом ящике лежали яблоки одного сорта. Найдутся ли 9 ящиков одного сорта?

«ЗАЙЦЫ» - 26 ящиков

«КЛЕТКИ»- 3 сорта

Осталось рассадить 26 «зайцев» в 3 «клетки». Так как 26> 3·8+1, то, используя принцип Дирихле (формулировка 4), можем утверждать, что в какой – то из «клеток» сидят 8+1=9 «зайцев». Значит,  найдутся 9 ящиков одного сорта.

От противного: Пусть ящиков одного сорта будет не больше 9, то есть 8. Тогда должно быть всего не более 8*3=24 ящиков яблок. Что противоречит условию.

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

Количество ошибок может быть записано числами от 0 до 12, то есть 13 различных вариантов, их и примем за «КЛЕТКИ». Учеников, кроме Вовы, 29 – их примем за «ЗАЙЦЕВ». Осталось рассадить 29 «зайцев» в 13 «клеток». Так как 29> 13*2+1, то, согласно обобщенному принципу Дирихле, существует «клетка», в которой сидят по крайней мере 2+1=3 «зайца». Таким образом, можно утверждать, что в классе есть 3 человека, сделавших одинаковое количество ошибок.

3. Заключение.

При выполнении этой работы был исследован класс задач на применение принципа Дирихле и различных его формулировок. В ходе работы задачи были решены 2 способами: принципом Дирихле и способом доказательства от противного, то есть мы познакомились с двумя способами решения олимпиадных задач. А также был создан буклет с основными видами задач. (см.Приложение)

Литература:

1. Готовимся к олимпиадам по математике: учеб. метод. пособие/

А.В.Фарков. - М.: Издательство «Экзамен»,2007.

2. Математический праздник. –М.:Бюро Квантум, 2004.(Библиотечка «Квант», вып.88)

3.Популярная комбинаторика /Н.Я.Виленкин – М.:Издательство «Наука», 1975.

4. Андреев А.A., Савин А.Н., Саушкин М.Н. "Принцип Дирихле" (сайт Путеводитель В МИРЕ НАУКИ для школьников http: ermine.narod.ru).

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

Образуем 8 пар, в каждую пару включим учеников, сидящих друг против друга.

Тогда «ЗАЙЦЫ» - девушки

«КЛЕТКИ»- 8 пар

Так как девушек больше половины, то есть восьми, то найдется «клетка» (пара), в которой будут находиться 2 девушки (формулировка1 принципа Дирихле).