Семинар ДООМ Кружок 5-8, Принцип Дирихле

Коннова Елена

Руководитель команд ДООМ 2008 МОЗГИ ID 215 и Великие математики ID_214

Предлагаю ряд статей, обьединенных в цикл "олимпиадные задачи. Кружок 5-8." Все они вошли в состав сборников, один из которых вышел издательстве Легион (Е.Г. Коннова. Математика. Серия «Готовимся к олимпиаде». Ростов н/Д: Легион, 2008.), а второй готовится к печати.

Занятие 3. Знакомство с принципом Дирихле.

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

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

Докажем обобщенный принцип Дирихле.

Доказательство от противного. Предположим, что не найдется такой клетки. Значит, в каждой клетке находится не более чем k зайцев. Тогда в n клетках не более чем kn зайцев. Но по условию у нас было kn+1 зайцев. Получилось противоречие, значит наше предположение неверно. Следовательно, найдется хотя бы одна клетка, в которой находятся не менее чем k+1 заяц. Безусловно, начинать эту тему стоит с задач, в которых нужно работать с конкретными числами. Обязательно в процессе решения нужно обращать внимание, что мы должны говорить «не более», «не менее», а не обсуждать «лучший» («худший») случай, так как доказать это часто достаточно сложно.

Задача 1. 

В городе Формалюнске 15 школ. В них обучается 6015 школьников. В концертном зале городского Дворца Культуры 400 мест. Доказать, что найдется школа, ученики которой не поместятся в этот зал.

Решение задачи №1.

Предположим, что в каждой школе не более 400 учеников. Значит, в 15 школах не более 15 •400=6 000 школьников. Но по условию в школах обучается 6015 человек. Значит, найдется школа, в которой больше 400 учеников. Поэтому ученики этой школы не поместятся в зал на 400 мест.

Задача 2.

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

Решение задачи №2.

Предположим, что все парламентеры поссорились с различным количеством своих коллег. Посчитаем, сколько может быть различных вариантов. Можно не поссориться ни с кем, поссориться с одним человеком, с двумя, с тремя и так далее до 16 (если поссорился со всеми). Всего получается 17 вариантов поссориться, но если кто-то поссорился со всеми, то не может одновременно быть парламентера, который ни с кем не поссорился. Значит, остается 16 различных вариантов для 17 человек, и найдутся два участника совета, которые поссорились с одинаковым количеством парламентеров.

Задача 3.

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

Решение задачи №3.

Предположим, что в каждом месяце родилось не более 13 учеников (год рождения не учитывается). Значит, за 12 месяцев родилось не более 12 •13=156 школьников. Но по условию в пяти классах этой школы обучается 5*32=160 человек. Получили противоречие. Значит, найдется месяц, в котором родилось больше 13 учеников, то есть хотя бы 14.

Задача 4.

В 3"А" классе учится 27 школьников, знающих (всего) 109 стихотворений. Докажите, что найдется школьник, знающий не менее пяти стихотворений.

Решение задачи №4.

Предположим, что каждый школьник знает не более 4 стихотворений. Значит, 27 школьников знают не более 4 •27=108 стихотворений. Но по условию они знают 109 стихотворений. Получили противоречие. Значит, найдется школьник, который знает хотя бы 5 стихотворений.

Задача 5.

В походе участвовало 25 человек, каждому из которых было от 24 до 30 полных лет (на данный день). Докажите, что найдутся четыре человека, родившихся в один год.

Решение задачи №5.

Различных годов рождения может быть 7. Предположим, что каждый год родилось не более трех участников похода. Значит, за 7 лет могли родиться не более 3• 7=21 участников. Но, по условию, в походе участвовало 25 человек . Получили противоречие. Значит, найдутся четыре участника похода, родившихся в один год.

Задача 6. 

По дороге в школу третьеклассник Коля преодолел 27 луж. Дорога в школу заняла у него 15 минут. Докажите, что найдутся две лужи с паузой менее чем в 35 секунд.

Решение

Если бы между всеми лужами были паузы не менее чем в 35 секунд, то Коля затратил бы на них не менее 35*26=910 секунд, это больше чем 15 минут, что противоречит условию. (26 промежутков, если первая и последние лужи находятся на концах пути.)

Задача 7.

На окно кабинета математики размером 40 см на 30 см село 25 мух. Доказать, что квадратной мухобойкой 11*11 см можно прихлопнуть сразу трех мух.

Решение задачи №7.

Разделим окно на 12 квадратов размером 10 см на 10 см. Если в каждом квадрате не более двух мух, то всего на окне не более 2 •12=24 мух, а по условию мух 25, значит в каком-то квадрате сидит хотя бы 3 мухи. Мухобойка закроет этот квадрат. Значит, такой мухобойкой можно прихлопнуть сразу трех мух.

Другие работы:

Семинар ДООМ 2008 "Формула текста"

Семинар ДООМ Кружок 5-8, Четность

Семинар ДООМ Кружок 5-8, Задачи на проценты

Семинар ДООМ Кружок 5-8, Игры (задачи на стратегию)

Семинар ДООМ Кружок 5-8, Принцип Дирихле

Семинар ДООМ Кружок 5-8, Текстовые задачи, решаемые с помощью теории графов

Семинар ДООМ 2007 "Графы"

Семинар ДООМ Задачи, решаемые с помощью деревьев

Элективный курс Графы 6-8 класс Программа курса 18 часов

Материалы для курса Графы - Материалы для оценивания усвоения содержания Элективного курса