Решение олимпиадных задач по математике онлайн. Принцип Дирихле.

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

К таким открытиям можно отнести широко известный «принцип Дирихле», который часто используется при решении задач «на доказательство». Формулируется этот принцип очень просто и доступно, я бы сказала, даже в шуточной форме.

Итак, он гласит:

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

Также часто при решении задач используют так называемый

обобщенный принцип Дирихле.

Пусть в n клетках сидит не менее k · n + 1 кроликов, тогда в какой-то из клеток сидит по крайней мере k + 1 кролик.

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

Задача 1.

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

Решение.

Здесь в качестве кроликов необходимо принять учеников, а в качестве клеток – число решенных примеров на контрольной. В клетку с номеров «0» определим все учеников, кто не решил ни одного примера. В клетку с номером «1» – всех учеников, кто решил 1 пример, в клетку с номером «2» – всех учеников, кто решил 2 примера и так далее до клетки номер 13. В ней окажется Саша Виноградов. Теперь предположим противное, то есть что никакие три ученика не решили одинаковое количество примеров. На языке «кроликов и клеток» это будет звучать так: в каждую из клеток, начиная с 0-ой и заканчивая 12-й, попадет меньше трех учеников. Тогда в каждой клетке не больше двух человек, а в 13-ти клетках не больше 26 человек. Даже если мы добавим Сашу Виноградова, то 30 человек не набирается. Мы получили противоречие с нашим предположением.

Тогда заключаем, что найдутся 3 ученика, решивших одинаковое количество примеров на контрольной по математике.

Задача 2.

На доске записаны 52 произвольных натуральных числа. Докажите, что среди этих чисел можно выбрать два таких, что либо их сумма, либо разность заканчивается на 00.

Решение.

Для начала «построим» клетки.

Клетка №0 – для чисел, заканчивающихся на 00.

Клетка №1 – для чисел, заканчивающихся на 01 или 99.

Клетка №2 – для чисел, заканчивающихся на 02 или 98.

…

Клетка №49 – для чисел, заканчивающихся на 49 или 51.

Клетка №50 – для чисел, заканчивающихся на 50.

Нетрудно видеть, что какие-то два из 52 чисел попадут  в одну клетку, а значит, или их сумма, или их разность заканчивается на 00.

Задача 3.

Докажите, что среди n + 1 натуральных чисел, меньших 2n, найдутся два числа, таких, что одно из них делится на второе.

Решение.

Выберем из данных n + 1 натуральных чисел все четные числа. Далее разделим каждое из выбранных чисел на максимальную степень двойки, чтобы в результате получить нечетное число. Таким образом, с учетом оставшихся чисел, получим n + 1 нечетное число. Заметим, что каждое из полученных нечетных чисел по-прежнему меньше 2n. Нетрудно заметить, что существует всего n нечетных чисел, меньших 2n. Если провести аналогию, то видно, что клеток у нас – n, а кроликов – n + 1. Значит, среди полученных чисел найдется по крайней мере 2 одинаковых, то есть по крайней мере в одной клетке сидит два кролика.

Это и означает, что существует по крайней мере два числа, таких, что одно из них делится на второе.

Задача 4.

В куб со стороной 1 метр помещена 2001 муха. Докажите, что хотя бы трех из них можно поймать сферой радиуса 1/11.

Решение.

Распилим наш куб на 1000 маленьких кубиков со стороной 1/10 метра. Далее воспользуемся принципом Дирихле. В качестве кроликов возьмем мух, а в качестве клеток – 1000 маленьких кубиков. Тогда, очевидно, что в каком-то кубике сидит 3 мухи. Вычислим радиус сферы описанной вокруг такого кубика

. Он будет равен половине диагонали куба.

Рассмотрим треугольник ABC. Здесь сторона AB и есть нужная нам диагональ. AC = 1/10, как сторона маленького кубика.

BC =√2/10 как диагональ квадрата со стороной 1/10. Тогда по теореме Пифагора для треугольника ABC получим:

(1/10)² + ВС² = AB².

Отсюда AB = √3/10.

А радиус сферы, описанной около кубика, r = √3/20.

Но 1/11 > √3/20, а, значит, сфера радиуса 1/11 будет содержать кубик с тремя мухами, то есть хотя бы три мухи можно поймать сферой радиуса 1/11.

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

Остались вопросы? Не знаете, как решить задачу по математике?
Чтобы получить помощь репетитора – зарегистрируйтесь.

Первый урок – бесплатно!

Зарегистрироваться

© blog.tutoronline.ru, при полном или частичном копировании материала ссылка на первоисточник обязательна.

blog.tutoronline.ru

Задачи на принцип Дирихле. Задачи на доказательство от противного.

Тема занятия: Задачи на принцип Дирихле.  Задачи на доказательство от  противного.   Задачи:               Познакомить обучающихся с методом доказательства «от противного», методом  оценки и научить пользоваться некоторыми свойствами неравенств;               Сформировать понимание отличия интуитивных соображений от доказательства;               Развивать умение различать в задаче условие и заключение;               Познакомить с задачами, где при расплывчатых формулировках удается получить  некоторую достоверную информацию;     1. Организационный момент. Сообщение темы и целей урока. Рабочий настрой на урок.   2. Вводная часть. При решении многих задач используется логический метод рассуждения — «от  противного». В чем заключается этот метод мы с вами немного говорили: делается  противоположное предположение тому, что нужно доказать. На данном занятии мы  рассмотрим одну из форм метода рассуждения «от противного» — принцип Дирихле. Принцип Дирихлее — утверждение, названное в честь автора немецкого математика,  который жил в 19 веке. Данное утверждение устанавливает связь между объектами при  выполнении определённых условий. Данный метод автор успешно применял его к  доказательству арифметических утверждений. Принцип Дирихле применяется в разных  разделах математики: в арифметике, в комбинаторике, в геометрии. И мы на данном  занятии познакомимся с некоторыми изюминками решения задач на принцип Дирихле.   3. Разбор темы занятия.   Рассмотрим общую формулировку принципа Дирихле. Этот принцип утверждает, что если  множество из k элементов разбито на п непересекающихся частей, не имеющих  общих элементов, где k>n то, по крайней мере, в одной части будет более одного  элемента. По традиции принцип Дирихле объясняют на примере «кроликов и клеток». Самая  популярная формулировка принципа Дирихле звучит так: «Если в n клетках сидит n+1 или больше кроликов, то найдётся клетка, в которой сидят по крайней мере два кролика».   Более общая формулировка принципа: «Если k кроликов сидят в n клетках (k>n), то  найдётся клетка, в которой не менее k/n кроликов»            Доказательство принципа Дирихле очень простое, но заслуживает внимания,  поскольку похожие рассуждения «от противного» часто встречаются.

Заметим, что в роли кроликов могут выступать различные предметы и  математические объекты ­ числа, отрезки, места в таблице и т. д. Если мы хотим применить принцип Дирихле при решении конкретной задачи, то нам предстоит разобраться, что в ней  — «клетки», а что — «кролики». Это обычно является самым трудным этапом в  доказательстве.   4. Закрепление темы. Начнем решение задач с очевидной задачи и попробуем применить принцип Дирихле при  доказательстве. Задача 1: Шесть школьников съели семь конфет.  Докажите, что один из них съел не менее двух конфет. Вопрос: что мы примем за «клетки», а что за «кролики»? Если 7 кроликов рассадим по 6  клеткам, то в одной клетке окажется по крайней мере 2 кролика, т.е. один ученик съел как  минимум 2 конфеты. Ч.т.д.   Задача 2. Докажите, что в любой футбольной команде есть два игрока, которые родились в один и тот же день недели. Рассуждения: кролики – игроки команды, клетки – дни недели. Сколько игроков в  футбольной команде? – 11, а дней недели – 7. Если рассадить кроликов в клетки, то  окажется, что 4 кролика будут сидеть в клетке не в одиночестве.     Ч.т.д.   Задача 3. Имеется 25 конфет трех сортов. Верно ли, что не менее девяти из них будут  какого­то одного сорта?   Рассуждения: Пусть «клетками» у нас будут сорта конфет, а «кроликами» ­ сами конфеты.  По принципу Дирихле найдется «клетка», в которой не менее 25 / 3 «кроликов». Так как  8 < 25 / 3 < 9, то найдется 9 конфет одного сорта.   Задачу можно решить, проводя сразу рассуждения от противного: пусть конфет каждого сорта не более 9, то есть не превышает восьми. Тогда всего конфет  не превышает 3 ×  8 = 24, а по условию их 25.          Противоречие.   Задача 4: В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Докажите, что какие­то три ученика сделали одинаковое количество ошибок.   Рассуждения: Здесь «кролики»­ ученики, «клетки»­ число сделанных ошибок. В клетку  0 «посадим» всех, кто не сделал ни одной ошибки, в клетку 1­ тех, у кого 1 ошибка… и так  до клетки 13, куда попал один Паша. Теперь применим принцип Дирихле.  Докажем утверждение задачи от противного. Предположим, никакие три ученика не  сделали по одинаковому числу ошибок, то есть в каждую из «клеток» 0,1,…,12 попало  меньше трех школьников. Тогда в каждой из них два человека или меньше, а всего в этих 13 клетках не более 2*13=26 человек. Добавив Пашу, все равно не наберем 30 ребят.

Противоречие. Следовательно, утверждение задачи верно, по крайней мере, трое учеников сделали поровну ошибок. Задача 5. Каждый из 10 участников переговоров послал по их окончании поздравительные  открытки пятерым другим участникам. Докажите, что какие­то двое послали открытки  друг другу. Рассуждения: Всего было отправлено 50 открыток. Значит, существует участник, который  получил не менее пяти открыток (если бы каждый получил не более четырёх, то всего было бы отправлено не более 40 открыток). Таким образом, он послал открытки пятерым  участникам и получил открытки не менее чем от пяти участников. Поскольку, кроме него,  имеется лишь 9 участников, то хотя бы один другой участник входит в обе пятёрки. 5. Работа в группах. А теперь проверим, как вы самостоятельно применяя принцип Дирихле, решите задачи.   Дети разбиваются на группы по 2­3 человек. Совместно находят решения 4­х задач. Указание: рассуждение начинать обязательно с определения, что в задаче принимается за  «клетки», а что за «кролики». 1 В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка ­ точка).  Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не  менее трёх дырок.  Рассуждения: «клетки» ­ 25 заплаток; «кролики» 51 моль. Весь ковер можно накрыть  такими 25­ю заплатами. По принципу Дирихле какая­то из этих заплат накроет не менее  трех дырок.              2. В классе 40 учеников. Найдётся ли такой месяц в году, в котором отмечают свой  день рождения не меньше чем 4 ученика этого класса? Рассуждения: «клетки» ­ 12 месяцев, «кролики» ­ 40 учеников. Рассуждаем от противного.  Если бы такого месяца не нашлось, то в каждом из 12 месяцев день рождения отмечали бы  не более трёх учеников. Значит, всего учеников было бы не более 363. Но 40> 36.  Противоречие.          3.  На плоскости нарисовали 5 прямых. Докажите, что угол между какими­то двумя из них не больше 36°. (Если какие­нибудь прямые параллельны, считайте, что угол  между ними равен 0°.) Рассуждения: Отметим на плоскости произвольную точку и переместим параллельными  переносами все прямые так, чтобы они проходили через эту точку. Величины углов между  прямыми при этом не изменятся. Теперь мы получили пять прямых, проходящих через  одну точку, которые образовали 10 углов (внутренние области которых не пересекаются).  Сумма величин этих углов равна 360°. Если бы все эти величины были больше 36°, то их  сумма была бы больше 360°. Следовательно, величина хотя бы одного из этих десяти углов  не превышает 36°. В данной задаче «клетки» ­ 10 углов; «кролики» ­ 3600.   6. Подведение итогов урока.          Сегодня мы рассмотрели на уроке задачи, решение которых достаточно стандартны и  основываются на применении свойств неравенств и методе доказательства «от

противного». Дома вам предлагается самим придумать задачу, решение которой  предполагает применение принципа Дирихле.   8.     Постановка д\з.   Задачи для домашнего решения: 1. Если класс из 30 человек рассадить в зале кинотеатра, то в любом случае хотя бы в  одном ряду окажется не менее двух одноклассников. Если то же самое проделать с  классом из 26 человек, то по крайней мере три ряда окажутся пустыми. Сколько рядов в  зале? 2. На Земле живет более 4 миллиардов человек. Известно, что среди них не более 1% людей старше 100 лет. Докажите, что найдутся два человека, которые родились в одну и ту же  секунду. 3. Докажите, что из любых 12 натуральных чисел можно выбрать два, разность которых  делится на 11. 4. У человека на голове не более 400000 волос, в Москве более 8 млн. жителей. Докажите,  что найдутся 20 москвичей с одинаковым числом волос.   Педагог дополнительного образования: Лысенко Н.А.

znanio.ru

Материал для подготовки к ЕГЭ (ГИА) по математике (11 класс) на тему: Применение принципа Дирихле при решении задач ЕГЭ.

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

Принцип Дирихле: один из принципов, сформулированных немецким математиком Дирихле.

Этот принцип достаточно прост и очевиден, иногда им пользуются из соображения логики, даже не зная его формулировки. Но, зная этот принцип, легче догадаться в каких случаях его применять. Проще всего принцип Дирихле выражается в такой шуточной форме: «Если в n клетках больше, чем n + 1 зайцев, то хотя бы в одной клетке сидят не меньше двух зайцев».

В переводе на язык математики: «Если множество, состоящее из n k+1 элементов разбить на k подмножеств, то хотя бы в одном подмножестве найдется не менее чем n + 1 элементов». Формулировки принципа Дирихле.

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

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 заяц.

Доказательство принципа Дирихле можно провести, применив метод от противного.

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

 находить верное решение в нестандартной ситуации.

На апробации КИМ в 2015 году ЕГЭ по математике (базовый уровень) задача №20 решается просто, если использовать принцип Дирихле.

В корзине лежат 25 грибов:рыжики и грузди. Известно, что среди любых 11 грибов имеется хотя бы один рыжик, а среди 16 грибов хотя бы один груздь. Сколько рыжиков в корзине?

Решение.

Рассмотрим первую ситуацию: среди любых 11 грибов имеется хотя бы один рыжик, т.е.

из 11 грибов:  

Рассмотрим вторую ситуацию: среди 16 грибов хотя бы один груздь, т.е.

из 16 грибов:        

Ответ: 15 рыжиков.

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

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

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

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

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

Основные виды задач.

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 человека, сделавших одинаковое количество ошибок.

При решении задач был использован принцип Дирихле и различные его формулировки. Задачи были решены 2 способами: принципом Дирихле и способом доказательства от противного.

.

nsportal.ru

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

Слайд 1

Выполнил учащийся ГПОУ МССУОР № 1 6 «А» класса Шурыгин Матвей Принцип Дирихле и его применение при решении задач.

Слайд 2

Принцип назван в честь немецкого математика Дирихле (1805-1859), который успешно применял его к доказательству арифметических утверждений.

Слайд 3

Самая популярная формулировка принципа Дирихле звучит так: » Если в n клетках сидит n +1 или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца». Заметим, что в роли зайцев могут выступать различные предметы и математические объекты — числа, отрезки, места в таблице и т. д.

Слайд 4

Примеры задач: 1. Дано 12 целых чисел. Докажите, что из них можно выбрать 2, разность которых делится на 11. Решение: примем числа за «зайцев», их 12,значит клеток должно быть меньше. Пусть «клетки » — остатки от деления целого числа на 11.Всего таких» клеток» будет 11: 0,1,2, 3,4,5,6,7,8,9,10.Тогда по принципу Дирихле найдется «клетка», в которой будут сидеть не менее чем 2 «зайца», то есть найдутся 2 целых числа с одним остатком. А разность 2 чисел с одинаковым остатком от деления на 11, будет делиться на 11: =(11m + q) – (11n + q) = 11(m – n).

Слайд 5

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

Слайд 6

2. В ковре размером 4х4 метра моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1х1 метр, не содержащий внутри себя дырок. (Дырки можно считать точечными). Решение: Разрежем ковер на 16 ковриков размером 1х1 метр. Так как ковриков- «клеток» — 16, а дырок –«зайцев»- 15, то найдется хотя бы одна «клетка», в которой не будет «зайцев», то есть найдется коврик без дырок внутри. Здесь применяют вторую формулировку принципа Дирихле.

Слайд 7

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

Слайд 8

3. В классе 27 учеников. Найдется ли месяц, в котором отмечают свои дни рождения не меньше, чем три ученика этого класса. Решение : В году 12 месяцев. Обозначим их за «клетки», а учеников за «Зайцев ». Так как 27 ≥ 12•2 + 1, то по обобщенному принципу Дирихле найдется «клетка», в которой сидят не менее 3 «Зайцев», то есть найдется месяц, в котором дни рождения празднуют не менее 3 учеников

Слайд 9

4.В бригаде 7 человек и их суммарный возраст – 332.Доказать, что из них можно выбрать 3 человека, сумма возрастов которых не меньше 142 лет. Решение 1 . Выберем трех старших членов бригады. Если им вместе 142 года, то хотя бы одному из них больше 47 лет. Если самому младшему из троих больше 47 лет, то им троим больше 142 лет. Пусть самому младшему из троих 47 лет или меньше, им троим вместе менее 142 лет. Тогда на долю остальных четверых приходится более 320 – 142 = 190 лет. Разделим 190 на 4 с остатком: 190 =4•47 + 2. Тогда по принципу Дирихле одному из четверых больше 47 лет. Это противоречит выбору троих самых старших в бригаде. Решение 2 . Рассмотрим все возможные тройки рабочих бригады. Всего таких троек = = 35. Сумма их суммарных возрастов равна 332∙35∙ = 4980. Значит по принципу Дирихле есть тройка, суммарный возраст в которой не меньше, чем 4980 : 35, что больше 142. Решение 3 . Средний возраст трех самых старших не меньше среднего возраста по бригаде, который равен . Поэтому сумма их возрастов по меньшей мере года.

nsportal.ru

Исследовательская работа по теме»Принцип Дирихле»

МБОУ МАЙСКАЯ СОШ им. Е.Л.ЧИСТЯКОВА

Исследовательская работа на тему:

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

Покровка, 2014

Содержание

Введение…………………………….……………………………………………..3

§1.Краткая биография Дирихле………………………………………………….4 1. Формулировка принципа Дирихле…………………………………………… 5 2. Доказательство Принципа Дирихле…………………………………………..6. §2. Задачи на принцип Дирихле………………………………………………….6 2.1. Арифметические задачи……………………………….……………………..7 Заключение……………………………………………………………………….. 9 Литература…………………………………………….…………………………….10

Введение.

В школьном туре олимпиады, на математических кружках часто встречаются задачи на доказательства. Основа этих задач опирается на применение принципа Дирихле, я не могу справиться с этими заданиями и решил изучить подробнее этот вопрос. Это побудило меня заняться исследовательской работой. Предметом исследования данной работы являются логические задачи. Разнообразие логических задач велико, велико и количество способов их решения. В своей работе я рассмотрел задачи, решаемые с помощью принципа Дирихле. Особенность логических задач заключается на развитие логики образное и творческое мышление, поэтому такие задачи являются олимпиадными. Решение таких задач есть гимнастика ума и увлекательное занятие, поскольку для решения большинства из них требуется не только знание определенного программного материала, но и логическое мышление. В своем первом исследовании я выделяю арифметический способ, так как он более проще и доступнее для моего первого шага начинания. Цель: научиться применять принцип Дирихле к решению олимпиадных задач. Задачи: 1. Ознакомится с биографией Дирихле. 2. Рассмотреть формулировку принципа Дирихле. 3. Наглядно доказать принцип Дирихле. 4. Научиться применять изученный принцип к решению задач. Гипотеза. Принцип Дирихле позволяет решать логические задачи олимпиадного характера, которые сложно решать другими способами. Актуальность. Принцип Дирихле не рассматривается в учебниках математики. Решая олимпиадные задания, я заметил, что для решения многих из них часто используется принцип Дирихле, поэтому я решил изучить его подробнее, каждый ученик, желающий поступить в вуз, должен уметь решать такие задания. Именно поэтому я заинтересовался теорией этого ученого, стал находить и решать задачи с применением этого способа доказательства. Так начинается работа, которую я представляю. Объект исследования — математические задачи. Предмет исследования – олимпиадные задачи.

§1. Краткая биография Дирихле Петер Густав Лежен.

Петер Густав Лежен Дирихле (13.2.1805 — 5.5.1859) — немецкий математик. Родился в Дюрене, в семье почтмейстера. Его предки были выходцами из бельгийского городка Ришле, этим обусловлено происхождение необычной для немецкого языка фамилии. В 12 лет Дирихле (правильнее будет Диришле) начал учиться в гимназии в Бонне, спустя два года — в иезуитской гимназии в Кёльне, где в числе прочих преподавателей его учил Георг Ом. В 1825 г. Дирихле вместе с А. Лежандром доказал великую теорему Ферма для частного случая n=5. В 1827 г. молодой человек по приглашению Александра фон Гумбольдта устраивается на должность приват-доцента университета Бреслау. В 1822-1827 годах был домашним учителем в Париже. Входил в кружок молодых ученых, которые группировались вокруг Ж. Фурье. В 1827 году занял место доцента в Бреславе; с 1829 года работал в Берлине, где проработал 26 лет, сначала как доцент, затем с 1831 г. как экстраординарный, а с 1839 г. как ординарный профессор Берлинского университета, после смерти К. Гаусса (1855) — Гёттингенского университета. Сделал ряд крупных открытий в теории чисел; установил формулы. Лекции Дирихле имели огромное влияние на выдающихся математиков более позднего времени, в том числе на Г. Римана, Ф. Эйзенштейна, Л. Кронекера, Ю. Дедекинда. В 1831 г. Дирихле женится на Ребекке Мендельсон-Бартольди, сестре знаменитого композитора Феликса Мендельсон-Бартольди.

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

Самая популярная формулировка принципа Дирихле звучит так:

ФОРМУЛИРОВКА 1. «Если в n клетках сидит (n+1) или больше зайцев, то найдётся клетка, в которой сидят, по крайней мере, два зайца». Заметим, что в роли зайцев могут выступать различные предметы и математические объекты — числа, отрезки, места в таблице и т. д. Принцип Дирихле можно сформулировать на языке множеств и отображений.

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

2. Доказательство Принципа Дирихле

Исследуя ряд формулировок о том, что за место «кроликов» и «клеток» можно использовать разные предметы, объекты, множества и т.д. пришел к решению наглядно показать на домашних птицах (курицы).

Доказательство №1

Есть 7 птенцов и 3 коробки, надо распределить так, чтобы в 1 коробке было не менее 3 птенцов

Решение: нашлась 1 коробка, где сидят 3 птенца.

Доказательство №2

Есть 4 поросенка и 3 коробки , необходимо доказать что после всех манипуляций найдется такая коробка, в которой окажется 2 поросенка.

§2. Задачи на принцип Дирихле

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

При́нцип Дирихле́ — утверждение, названное в честь автора немецкого математика, который жил в 19 веке. Данное утверждение устанавливает связь между объектами при выполнении определённых условий. Данный метод автор успешно применял к доказательству арифметических утверждений. Принцип Дирихле применяется в разных разделах математики: в арифметике, в комбинаторике, в геометрии. И в данной работе рассмотрим некоторые изюминки решения задач на принцип Дирихле. Безусловно, начинать эту тему стоит с задач, в которых нужно работать с конкретными числами. Обязательно в процессе решения нужно обращать внимание, что мы должны говорить «не более», «не менее», а не обсуждать «лучший» («худший») случай, так как доказать это часто достаточно сложно.

.1. Арифметические задачи

Пример 1. В классе 37 учащихся. Найдется ли такой месяц в году, в который свой день рождения отмечают не менее четырех учащихся этого класса? Решение. Т. к. в году 12 месяцев, а в классе 37 учащихся, то по принципу Дирихле обязательно найдется такой месяц в году, в котором свой день рождения отмечают не менее 4 учеников.

Пример 2. На земле живет 6000000000 человек, у каждого на голове – не более 3000000 (цифры условные) волос. Докажите, что обязательно найдутся два человека с одинаковым числом волос.

Решение. Т. к. количество людей больше количества возможных вариантов количества волос, то в соответствии с принципом Дирихле, хотя бы двое из них имеют одинаковое число волос. Пример 3. В классе 30 учеников. В диктанте Вова сделал 13 ошибок, остальные меньше. Докажите, что по крайней мере три ученика сделали ошибок поровну.

Ответ: Каждый из остальных 29 учеников сделал не более 12 ошибок. Разобьём их на 13 групп по числу сделанных ошибок (от 0 до 12). (В некоторых группах учеников может и не быть). Если бы в каждой группе оказались не более двух учеников, то во всех группах вместе было бы не более 26 учеников, а их 29. Значит, хотя бы в одной группе учеников больше двух.

Пример 4. В классе 40 учеников. Найдётся ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 ученика этого класса?

Ответ: Обязательно найдётся. Решение: Рассуждаем от противного. Если бы такого месяца не нашлось, то в каждом из 12 месяцев день рождения отмечали бы не более трёх учеников. Значит, всего учеников было бы не более 12 · 36. Но 40 > 36. Противоречие.[1]

Пример 5. Шесть школьников съели семь конфет.

а) Докажите, что один из них съел не менее двух конфет.

б) Верно ли, что кто-то съел ровно две конфеты?

Решение:

а) Указание: примените принцип Дирихле, считая, что, «клетки» — это школьники, а «кролики» — это конфеты.

б) Не обязательно: например, все семь конфет мог съесть один школьник.

Заключение

В ходе работы над исследованием задач я познакомился с литературой по этой теме, рассмотрел исторический материал, изучил принцип Дирихле, подготовил презентацию, учусь применять его при решении задач, планирую выступить перед учащимися 3 — 5 классов. Я понял, применяя данный метод, надо: 1.Определить, что удобно в задаче принять за «клетки», а что за «зайцев». 2. Получить «клетки»; чаще всего «клеток» меньше (больше), чем «зайцев» на одну (или более). 3.Выбрать для решения требуемую формулировку принципа Дирихле. Принцип Дирихле важен, интересен, полезен. Его можно применять в повседневной жизни, что развивает логическое мышление. Многие олимпиадные задачи решаются, используя это специальный метод. Он дает возможность обобщать.

Литература

1. http://logo-rai.ru/index.php/princip-dirihle

2. http://www.mccme.ru/courses/dirihle.html

3. konkurs2011/1433/1/9940_1433

4. http://portfolio.1september.ru/

5. http://www.zaba.ru/cgi-bin/tasks.cgi?tour=books.mk1.dirikhle

6. http://www.problems.ru/articles/216.php

7. http://bars-minsk.narod.ru/teachers/dirichle.html

8. http://lobanovaoe.narod.ru/posle_ur/principdirihle.htm

infourok.ru