МОУ Тучковская средняя школа 3 Научный руководитель: Гагаркина И.И. Руководитель проекта: Матвеева А.В. Участники проекта: Шиков Владислав, Потехин Дмитрий

Тема доклада : Принцип Дирихле Принцип Дирихле

Биография Дирихле Петер Август Лежён ( ) немецкий математик, иностранный член- корреспондент Петербургской Академии наук (1837), член многих других академий. Основные заслуги П. Дирихле в области математики: установил, что в арифметической прогрессии аn = а1 + dn, где n = 1,2... с целыми взаимно простыми а1 и d содержится бесконечно много простых чисел; установил, что в арифметической прогрессии аn = а1 + dn, где n = 1,2... с целыми взаимно простыми а1 и d содержится бесконечно много простых чисел; исследовал понятие условной сходимости ряда, установил признак сходимости ряда; исследовал понятие условной сходимости ряда, установил признак сходимости ряда; ввёл функциональные ряды особого вида; ввёл функциональные ряды особого вида; ввёл (вместе с Н. И. Лобачевским) определение функции через соответствие и т. д. ввёл (вместе с Н. И. Лобачевским) определение функции через соответствие и т. д.

Цель: - Познакомить учащихся с новыми математическим методом решения задач, которые не рассматриваются в школьном курсе - Научить решать олимпиадные задачи с помощью принципа Дирихле; - Показать его применение для решения разнообразных задач

Задачи проекта: - Научить решать задачи, связанные с числовыми множествами; - Научить решать задачи, связанные с делимостью чисел; - Научить решать некоторые геометрические; - Показать методику решения простейших задачи по теории вероятностей.

Формулировки принципа Дирихле Принцип Дирихле - утверждение, устанавливающее связь между объектами («кроликами») и контейнерами («клетками») при выполнении определённых условий. кроликамиклеткамикроликамиклетками 1. Если в n клетках сидит m зайцев, причём m > n, то хотя бы в одной клетке си­дят, по крайней мере два зайца 2. Пусть в n клетках сидят m зайцев, причём n > т. Тогда найдётся хотя бы одна пустая клетка

3. Если m зайцев сидят в n клетках, то найдётся клетка, в которой сидят не меньше, чем m/n зайцев, и найдётся клетка, в которой сидят не больше, чем m/n зайцев 4. Если n зайцев съели n килограммов травы, то какой-то заяц съел не менее m/n килограммов травы и какой-то заяц съел не больше m/n килограммов 5. Если в n клетках сидят m зайцев и m больше или равно, то в какой-то из клеток сидят по крайней мере k+1 заяц

Задачи на обобщенный принцип Дирихле: 1) 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть школьники, решившие ровно 1 задачу, школьники, решившие ровно 2 задачи, школьники, решившие ровно 3 задачи. Докажите, что есть школьники, решившие не менее 5 задач. 1) 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть школьники, решившие ровно 1 задачу, школьники, решившие ровно 2 задачи, школьники, решившие ровно 3 задачи. Докажите, что есть школьники, решившие не менее 5 задач.

Решение: Есть хотя бы по одному человеку, решившему ровно 1, ровно 2 и ровно 3 задачи. Значит найдутся 7 школьников, решивших оставшиеся = 29 задач. Так как 29 = 4 х 7 + 1, то найдется школьник, решивший не менее 5 задач. ( 29 кроликов и 7 клеток )

2) В школе 400 учеников. Можно ли утверждать, что среди учащихся этой школы обязательно найдутся хотя бы 2 ученика, отмечающие день рождения в один день? 2) В школе 400 учеников. Можно ли утверждать, что среди учащихся этой школы обязательно найдутся хотя бы 2 ученика, отмечающие день рождения в один день?

Решение: Да. 400 > 1 х

Задачи, решаемые методом «От противного»: 1) 21 мальчик вместе собрали 200 орехов. Докажите, что какие – то 2 мальчика собрали одинаковое число орехов.

Решение: Существуют две возможности: есть мальчики, собравшие одинаковое число орехов, или их нет. Предположим. Что все мальчики собрали разное количество орехов. Возьмем от нуля до 20 минимально возможные различные числа и просуммируем их …+ 20 = 210, уже больше чем по условию. Получили противоречие с условием. Значит принятое предположение неверно. Следовательно, найдутся 2 мальчика, собравших одинаковое число орехов. Существуют две возможности: есть мальчики, собравшие одинаковое число орехов, или их нет. Предположим. Что все мальчики собрали разное количество орехов. Возьмем от нуля до 20 минимально возможные различные числа и просуммируем их …+ 20 = 210, уже больше чем по условию. Получили противоречие с условием. Значит принятое предположение неверно. Следовательно, найдутся 2 мальчика, собравших одинаковое число орехов.

2) Можно ли увезти 50 камней весом 370, 372, 374, …,486 кг на 7 трехтонках? 2) Можно ли увезти 50 камней весом 370, 372, 374, …,486 кг на 7 трехтонках?

Решение: Предположим, что нам удастся увезти камни 7 трехтонках, то хотя бы на одну придется погрузить не менее 8 камней (7 х 7 = Противоречие. (50 камней – зайцы, 7 трехтонок – кролики, 50 = 7 х 7 + 1, т.е. на 1 трехтонку надо поместить 8 камней.)

Задача связанная с делимостью чисел: 1) Верно ли, что из любых трех целых чисел можно выбрать 2, сумма которых четна? 1) Верно ли, что из любых трех целых чисел можно выбрать 2, сумма которых четна?

Решение: Решение: Три любых целых числа либо все четные, либо все нечетные, либо из них два числа «одной четности» и одно другой. В любом случае найдутся 2 числа одинаковой четности, а их сумма обязательно четна.

2) Имеется 11 различных натуральных чисел, не больших 20. Докажите, что из них можно выбрать 2 числа, одно из которых делится на другое. 2) Имеется 11 различных натуральных чисел, не больших 20. Докажите, что из них можно выбрать 2 числа, одно из которых делится на другое.

Решение: Выберем из11 все четные числа и разделим каждое из них на максимальную степень двойки (12 = 4 х 3), тогда в частном получим нечетное число. Обозначим эти частные и остальные нечетные числа за зайцев (их 11) Но всего нечетных чисел, меньших20, будет 10. Тогда клеток будет 10. Так как 11 > 10 то найдется 2 одинаковых нечетных числа. Так как сами исходные нечетные числа различные, то совпадет нечетное число с нечетным частным, т.е. найдутся 2 числа, одно из которых делится на другое. Выберем из11 все четные числа и разделим каждое из них на максимальную степень двойки (12 = 4 х 3), тогда в частном получим нечетное число. Обозначим эти частные и остальные нечетные числа за зайцев (их 11) Но всего нечетных чисел, меньших20, будет 10. Тогда клеток будет 10. Так как 11 > 10 то найдется 2 одинаковых нечетных числа. Так как сами исходные нечетные числа различные, то совпадет нечетное число с нечетным частным, т.е. найдутся 2 числа, одно из которых делится на другое.

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

Решение: Так как цветов 2, то надо рассмотреть фигуру в которой точек больше чем 2. Лучше всего для этого подойдет равносторонний треугольник со стороной 1 метр. У него 3 вершины (зайцы), цвета – клетки. Т.к. 3 > 2, то найдутся 2 вершины, окрашенные в один цвет. Так как цветов 2, то надо рассмотреть фигуру в которой точек больше чем 2. Лучше всего для этого подойдет равносторонний треугольник со стороной 1 метр. У него 3 вершины (зайцы), цвета – клетки. Т.к. 3 > 2, то найдутся 2 вершины, окрашенные в один цвет.

2) В квадрате со стороной 10 см находится 51 точка. Докажите, что найдутся 3 точки, принадлежащие кругу с радиусом см. 2) В квадрате со стороной 10 см находится 51 точка. Докажите, что найдутся 3 точки, принадлежащие кругу с радиусом см.

Решение: Разобьем квадрат на 25 квадратиков со стороной 2 см, это – клетки. А 51 точка – зайцы. Т.к. 51 > 2 · 25 +1, то найдутся 3 точки, попавшие в 1 квадрат. Радиус круга, описанного около квадрата со стороной 2см = 2 · 25 +1, то найдутся 3 точки, попавшие в 1 квадрат. Радиус круга, описанного около квадрата со стороной 2см = < Значит найдутся 3 точки, которые будут принадлежать кругу данного радиуса.

Простейшие задачи по теории вероятностей : 1) В коробке лежат 5 красных, 4 зеленых и 3 синих карандашей, неразличимых на ощупь. Какое наименьшее число карандашей нужно взять из коробки не глядя, чтобы среди них наверняка оказалось: 1) В коробке лежат 5 красных, 4 зеленых и 3 синих карандашей, неразличимых на ощупь. Какое наименьшее число карандашей нужно взять из коробки не глядя, чтобы среди них наверняка оказалось: 1) 2 карандаша одного цвета? 2) 2 карандаша разных цветов? 3) 3 карандаша одного цвета? 4) 3 карандаша разных цветов? 5) 4 карандаша одного цвета? 6) 5 карандашей одного цвета?

Решение: 1) 4; 2) 6; 3) 7; 4)10; 5)10; 6)12.

2) В погребе стоит 20 одинаковых банок с вареньем. В 8- ми банках – клубничное варенье, в 7 – ми банках – малиновое, в 5 – и – вишневое. Каково наибольшее число банок, которое можно в темноте вынести из погреба с уверенностью, что там осталось еще хотя бы 4 банки одного сорта варенья и три банки другого?

Решение: Скажем так: какое наименьшее число банок надо оставить в погребе, чтобы среди них оказались хотя бы 4 банки одного сорта варенья и три банки другого. Чтобы обеспечить 4 банки варенья одного сорта надо оставить 10 банок. Но среди них могли оказаться все 8 банок клубничного варенья. Не клубничного варенья оставили точно не меньше 2 – х банок. Тогда оставим еще 3 банки. Из 5 банок 2 – х сортов 3 обязательно будут одного сорта. Итак 13 – минимальное число банок, которые можно оставить в погребе. Значит 20 – 13 = 7 -- максимальное число банок, которые можно из погреба вынести.

Знакомства: 1) Выберем любым способом 5 человек. Докажите что по крайней мере двое из них имеют одинаковое число знакомых среди выбранных.

Решение: Построим 5 клеток: 0,1,2,3,4. Пусть номер клетки равняется числу знакомых у содержащихся в них людей. Возможны 2 случая: есть человек, ни с кем из остальных не знакомый, или же такого человека нет. В первом случае в клетке 4 никого нет (иначе сидящие в клетке 4 и в клетке 0 были бы знакомы между собой) и 5 человек размещены по 4 «клеткам». Во втором случае тоже 5 человек размещены по 4 клеткам ( кл. 0 пуста) Значит по крайней мере двое находятся в одной клетке, т.е. имеют одинаковое число знакомых. Построим 5 клеток: 0,1,2,3,4. Пусть номер клетки равняется числу знакомых у содержащихся в них людей. Возможны 2 случая: есть человек, ни с кем из остальных не знакомый, или же такого человека нет. В первом случае в клетке 4 никого нет (иначе сидящие в клетке 4 и в клетке 0 были бы знакомы между собой) и 5 человек размещены по 4 «клеткам». Во втором случае тоже 5 человек размещены по 4 клеткам ( кл. 0 пуста) Значит по крайней мере двое находятся в одной клетке, т.е. имеют одинаковое число знакомых.

2) 30 команд участвует в первенстве по футболу. Каждые 2 команды должны сыграть между собой один матч. Докажите, что в любой момент соревнований есть 2 команды, сыгравшие к этому моменту одинаковое число матчей. 2) 30 команд участвует в первенстве по футболу. Каждые 2 команды должны сыграть между собой один матч. Докажите, что в любой момент соревнований есть 2 команды, сыгравшие к этому моменту одинаковое число матчей.

Решение: Рассмотрим 2 случая: 1) Пусть все команды к данному моменту времени сыграли хотя бы 1 матч. Тогда число сыгранных матчей каждой командой могло быть 1,2,…28,29. Обозначим эти 29 вариантов за клетки; 30 команд – «зайцы» 30>29, значит найдется не менее 2 – х команд, сыгравших одинаковое число матчей. Рассмотрим 2 случая: 1) Пусть все команды к данному моменту времени сыграли хотя бы 1 матч. Тогда число сыгранных матчей каждой командой могло быть 1,2,…28,29. Обозначим эти 29 вариантов за клетки; 30 команд – «зайцы» 30>29, значит найдется не менее 2 – х команд, сыгравших одинаковое число матчей. 2) Пусть есть команда, не игравшая матчей. Тогда число сыгранных матчей 0,1,2,…28. Команд 30, «клеток» -- 29, найдутся как минимум 2 команды, сыгравшие одинаковое число матчей (возможно ни одного). 2) Пусть есть команда, не игравшая матчей. Тогда число сыгранных матчей 0,1,2,…28. Команд 30, «клеток» -- 29, найдутся как минимум 2 команды, сыгравшие одинаковое число матчей (возможно ни одного).

Вывод: Принцип Дирихле помогает нам при решении некоторых задач. Следовательно мы можем утверждать, что принцип Дирихле облегчает решение задач. Принцип Дирихле помогает нам при решении некоторых задач. Следовательно мы можем утверждать, что принцип Дирихле облегчает решение задач.