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

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

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

Приведенные рассуждения достаточно стандартны и основываются на применении свойств неравенств и методе доказательства «от противного». Рекомендуется при решении простых задач этого типа проводить рассуждения, не упоминая о принципе Дирихле, так как в школьной программе нет такой темы и при решении задач ссылки на этот принцип неоправданны. Принцип Дирихле состоит в следующем: "Если в 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 человек . Получили противоречие. Значит, найдутся четыре участника похода, родившихся в один год.

Практическое задание. Начертите прямоугольный треугольник с катетами 3 см и 4 см. Измерьте гипотенузу. Ее длина должна получиться 5 см. Проверьте, что выполняется равенство 32+42=52. Начертите треугольник с катетами 5 см и 12 см. Измерьте гипотенузу. Ее длина должна быть равна 13 см. Проверьте, что выполняется равенство 52+122=132. У треугольника с катетами 6 см и 8 см гипотенуза равна 10 см (проверьте!). При этом 62+82=102.

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

Домашнее задание

3.1. По дороге в школу третьеклассник Коля преодолел 27 луж. Дорога в школу заняла у него 15 минут. Докажите, что найдутся две лужи с паузой менее чем в 35 секунд. 3.2. В Волгодонске живет более 125000 человек. На голове у каждого не более 10000 волос. Докажите, что найдутся 12 человек с одинаковым количеством волос на голове. 3.3. В буфете продают лимонад в бутылках стоимостью 30 руб. Пустую бутылку можно вернуть, получив за нее 20 руб. Какое наибольшее количество лимонада можно выпить на 100 руб.? 3.4. Я задумал число, прибавил к нему 1, умножил сумму на 2, произведение разделил на 3 и от результата отнял 4. Получилось 5. Какое число я задумал? 3.5. Первый член последовательности - 439, каждый следующий равен сумме цифр предыдущего, умноженной на 13. Чему равен 99 член последовательности?

Занятие 14. Принцип Дирихле. Решение задач.

Задача 1.

Доказать, что среди чисел, состоящих из цифр 3, найдется число, делящееся на 17.

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

Рассмотрим 17 чисел с разным количеством цифр:3, 33, 333, 3333, ... Предположим, что ни одно из них не делится на 17. При этом могут получаться 16 различных остатков: 1, 2, 3, ..., 16. Значит, среди наших чисел есть два числа с одинаковым остатком при делении на 17. Разность этих чисел делится на 17 и это число вида 333...000...(сначала несколько троек, потом нули). Заметим, что 10 взаимно просто с 17, значит если с конца этого числа убрать нули, то получившееся число тоже будет делиться на 17. Но оно состоит из цифр 3. Значит, мы нашли искомое число.

Рекомендуется разобрать задачи домашнего задания.

Ответы и указания. 3.1. Если бы между всеми лужами были паузы не менее чем в 35 секунд, то Коля затратил бы на них не менее 35*26=910 секунд, это больше чем 15 минут, что противоречит условию. (26 промежутков, если первая и последние лужи находятся на концах пути.) 3.2. Пусть в Волгодонске найдется не более 11 человек с каждым из 10001 вариантов количества волос. Но тогда население Волгодонска не превышало бы 110011 человек, что неверно. Значит, найдутся такие 12 человек. 3.3. Ответ:8. В самом конце останется 1 пустая бутылка за 20 руб., на возвращенные деньги лимонада уже не купишь. Сам лимонад стоит 10 руб. за бутылку. Значит, можно выпить (100-20):10 бутылок лимонада. 3.4. Ответ: 12,5. 3.5. Выпишем члены получившейся последовательности. 439,208,130,52,91,130,…Начиная с числа 130 числа повторяются через 3. (99-2):3=32(ост. 1), значит на 99 месте число 130.

Практическое задание. Разрежьте правильный 6-угольник на 9 одинаковых частей.

Домашнее задание 3.6. Докажите, что среди любых пятнадцати натуральных чисел есть два числа, разность которых делится на 14. 3.7. Диктант написали 29 человек. Гена сделал в диктанте 11 ошибок, и никто не сделал большее количество ошибок. Докажите, что найдутся три человека с одинаковым количеством ошибок. 3.8. Сколько нулей в конце записи числа, равного произведению чисел от 10 до 30? 3.9. Если цифры двузначного числа переставить местами, то число увеличится на 36. Найди все такие числа. 3.10. Можно ли расставить 18 табуреток в прямоугольной комнате так, чтобы у каждой стены стояло по 5 стульев?

Занятие 15. Решение задач.

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

Решение задачи №4.
Разделим окно на 12 квадратов размером 10 см на 10 см. Если в каждом квадрате не более двух мух, то всего на окне не более 2 •12=24 мух, а по условию мух 25, значит в каком-то квадрате сидит хотя бы 3 мухи. Мухобойка закроет этот квадрат. Значит, такой мухобойкой можно прихлопнуть сразу трех мух.
Задача 2.
На шахматной доске 8x8 отмечены центры всех полей. Можно ли 13 прямыми разбить доску на части так, чтобы в каждой части было не более одной отмеченной точки?
Решение задачи №5.
Рассмотрим внешний ряд клеток доски (по периметру). Центры полей образуют квадрат 7x7, между ними 28 промежутков. Мы должны разбить доску так, чтобы все отмеченные точки попали в разные части. Значит, прямые должны пересекать все промежутки между клетками. Но прямая может пересечь квадрат не более чем в двух точках, значит нужно не менее 14 прямых. Итак, нельзя 13 прямыми разбить доску на части так, чтобы в каждой части было не более одной отмеченной точки.