Сборник задач "Принцип Дирихле"

Сборник

                 задач

       по математике

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

                         Составитель: Забожанская Елена Петровна,

                    Учитель математики МАОУ «СОШ № 44» им. Г.Я.Грицая

                   Миасс, 2022 г.

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

Доказательство. Предположим противоположное. Каждая буква встречается не более одного раза. Так как всего букв 33, то на, кубиках должно быть не более 33 граней, а их по 6 на каждом кубике, то есть 36. Получили противоречие, значит наше предположение не верно, следовательно, верно прямое утверждение, а именно: найдется буква встречающееся дважды.

Задача 2.  Маугли положил 3 различных типа фруктов в мешок, всего в мешке 30 штук этих фруктов. Чтобы наверняка вынуть из мешка апельсин, (не заглядывая в мешок), Маугли должен вынуть из него 19 фруктов.

Чтобы наверняка вынуть из мешка кокос, Маугли должен вынуть 24 фрукта.

Сколько фруктов должен вынуть из мешка Маугли (не заглядывая в него), чтобы быть уверенным, что он вынет по крайне мере один фрукт каждого вида?

Решение: Если, чтобы наверняка вынуть из мешка апельсин, надо вытащить 19 фруктов (и 19-ый -апельсин), то в мешке (30-18=12)12 апельсинов. По такому же правилу можно вычислить, что в мешке 7 кокосов. (30-23=7). А других фруктов 30-12-7=11. Чтобы вынуть по одному фрукту каждого вида, надо вытащить 12+11+1=24 фрукта. И даже если не очень повезет, и мы вынем сначала 12 апельсинов, потом 11 "других" фруктов, то все равно будет хотя бы 1 кокос!

Ответ: 24

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

Решение. Обозначим 35 учеников за «зайцев», а буквы за «клетки». В русском алфавите 33 буквы.

Фамилии не могут начинаться на Ъ и Ь. Так как 35 больше 31, то, по принципу Дирихле, найдете 2 ученика, у которых фамилии начинаются с одной буквы.

Задача 4. В коллекции имеется 25 монет по 1, 2, 5,10рублей. Имеется ли среди них 7 монет одинакового достоинства?

Решение:                                       

Имеем 4 «клетки» (монет разного достоинства), 25:4=6(ост.1), 25=4*6+1. В каждую «клетку» мы можем «посадить» 6 «зайцев» (монет одного достоинства) и еще останется одна монета. Значит, в какую-то «клетку» мы посадим еще одного «зайца» (монету). Таким образом, среди 25 монет, по крайней мере, имеется 7 монет одинакового достоинства.

Ответ: 7

Задача 5. В школе 20 классов. В ближайшем доме живет 23 ученика этой школы. Можно ли утверждать, что среди них обязательно найдутся хотя бы 2 одноклассника?

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

Задача 6. В ковре размером 3х3 метра моль проела 8 дырок. Докажите, что из него можно вырезать коврик размером 1х1 метр, не содержащий внутри себя дырок.

Решение: 

Из ковра размером 3х3 метра можно получить 9 ковриков размером 1х1 метр, так как ковриков- «клеток» 9, а дырок-«кроликов» 8, то найдется хотя бы одна пустая «клетка», то есть найдется коврик без дырок.

Задача 7.

На площадке 20 собак восьми разных пород. Докажите, что среди них есть не менее трех собак одной породы.

Решение: Имеем 8 «клеток» (разные породы собак), 20:8=2(ост. 4), 20=8*2+4. В каждую «клетку» мы можем «посадить» 2 «зайцев» (собак) и еще останется 3 собаки. Значит, в какую-то «клетку» мы посадим еще одного «зайца» (собаку). Таким образом , среди 20собак, по крайней мере, имеется 3 собаки одной породы.

Задача 8. У Васи было 49 апельсинов и он раздал их шести друзьям. Требуется доказать, что кто-то из друзей получил не меньше 9 апельсинов.

Решение: Будем рассуждать от противного. Пусть такого человека, который получил не менее 9 апельсинов нет. Значит, он получил 8 или меньше апельсинов (не более 8). Значит, каждый человек получил не более 8, и все мвесте они получили не более 6*8=48 апельсинов. А по условию апельсинов было 49. Мы опять пришли к противоречию. Значит, по меньшей мере есть хотя бы один из друзей, который получил не меньше 9 апельсинов.

Задача 9.  В классе, где учится 28 учеников, прошел диктант. Вася сделал 13 ошибок, остальные меньше. Докажите, что есть трое, сделавшие поровну ошибок.

Решение: Отведем в сторону Васю, у нас останется 27 человек, про которых известно, что каждый из них сделал меньше 13 ошибок. Какие здесь есть варианты? Можно сделать 12 ошибок, 11, 10, 9 и так далее до 1 (это уже 12 вариантов), но надо не забыть, что есть еще 1 вариант, когда ошибок вообще нет. Значит разных вариантов для остальных учеников 13.  Допустим, что  таких троих нет, тогда на каждый вариант приходится не больше 2 человек. Значит, всего не больше 13*2 = 26  человек, а у нас без Васи 27 человек. Противоречие. Следовательно,  есть трое, сделавшие поровну ошибок.

Задача 10. Докажите, что среди 82 карандашей всегда можно выбрать 10 карандашей так, что либо все они имеют разные цвета, либо все одного цвета.

Решение: Опять будем доказывать от противного. Пусть не выполняется ни одно из этих условий.  Тогда у нас нет 10 карандашей разных цветов, то есть их не больше 9, и нет 10 карандашей одного цвета, значит, каждого цвета не больше 9 карандашей. Получается, что всего карандашей 9*9 = 81, а по условию карандашей 82. Пришли к противоречию, а следовательно, либо имеется 10 карандашей одного цвета, либо 10 карандашей разных цветов.

Задача 11. В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.

Решение:

 25 ящиков - "кроликов" рассадим по 3 "клеткам"-сортам. Так как  25 = 3 ∙ 8 + 1, то применим утверждение (Если в n клеток посадить kn+1 зайцев, то найдется хотя бы одна клетка, в которой находятся не менее чем k+1 заяц для п= 3, k= 8) и получим, что в какой-то "клетке" - сорте не менее 9 ящиков.

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

Решение: Поставим куда-нибудь на доску белую фигуру. Она одно место уже займет. Если фигура стоит в центре доски, то она "унесет" с собой еще 8 мест, откуда ее может бить конь. То есть каждая белая фигура "уносит" с собой не более 9 клеток. Фигура может стоять и в углу, тогда она только 2 клетки с собой "свяжет", но в любом случае она свяжет не более 8 и таких клеток на каждую фигуру приходится не более 9. А фигур семь. Каждая уносит 9 клеток, 7х9 = 63, а всего на доске 64 поля. Значит семь фигур заняли не более 63 клеток, и одна клетка по меньшей мере останется для черного коня.

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

Решение: В году может быть максимум 366 дней, то по принципу Дирихле учеников может быть максимум n+1, то есть 366+1=367 учеников.

Задача 14. Сто человек сидят за круглым столом, причем более половины из них – мужчины. Докажите, что найдутся два мужчины, сидящие друг напротив друга.

Решение: Число пар, сидящих друг напротив друга равно 50. Так как мужчин как минимум n+1, то есть 50+1, то по принципу Дирихле найдется хотя бы одна пара мужчин, сидящих друг напротив друга.

Задача 15. Пять мальчиков собрали вместе 14 грибов, причем каждый нашел хотя бы один гриб. Докажите, что хотя бы два мальчика нашли одинаковое число грибов.

Решение: В худшем случае у пяти мальчиков могло быть различное число грибов, а всего 1+2 + 3 + 4 + 5 = 15. Но грибов было 14, следовательно, кто-то один, кроме первого, нашел на один гриб меньше. Тогда найдутся 2 мальчика, которые нашли одинаковое число грибов.

Задача 16. В школе 20 классов. В ближайшем доме живет 23 ученика этой школы. Можно ли утверждать, что среди них обязательно найдутся хотя бы 2 одноклассника?

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

Задача 17. В классе 37 человек. Докажите, что среди них найдутся 4 человека, родившиеся в один и тот же месяц.

Решение: В худшем случае в каждом из 12 месяцев родилось по 3 человека - всего 36 человек. 37-й родился с какой-то из этих троек в один месяц.

Задача 18. В новом микрорайоне было построено 30 новых домов. 21 из них были трехэтажные , 22 выкрашены в персиковый цвет, у 18 домов крыша красного цвета. Докажите, что на улице обязательно найдется двухэтажный дом персикового цвета с красной крышей.                     

Решение: Возьмем 21 карточку и на каждой из них напишем двухэтажный дом. Еще на 22 карточках напишем – персиковый цвет, и на 18 – красная крыша. Всего у нас окажется 21 + 22 + 18 = 61карточка. Пронумеруем дома от 1 до 30 и будем раскладывать карточки. Так как 61 = 30∙2 + 1, значит по крайне мере на одном доме будет три карточки. Следовательно, на улице обязательно найдется двухэтажный дом персикового цвета с красной крышей.

Задача 19. На поляне размером 8м×10м в произвольном порядке посадили 19 деревьев  .           

Докажите, что в любом случае найдется квадрат со стороной 2м, на котором не растёт ни одно дерево, для того, чтобы установить качели.

Решение: Данную поляну можно разделить на 20 равных квадратов со стороной 2м.

Так как посажено только 19 деревьев, то обязательно найдется квадрат, внутри которого нет ни одного дерева.

Задача 20. В ковре 2м×5м мышь прогрызла 21 дырку. Докажите, что найдутся хотя бы 3 дырки, которые можно залатать одной квадратной заплаткой со стороной 1м.

Решение: Ковер можно разделить на 10 квадратов со стороной 1м.Так как 21 = 10∙2+1, то найдется квадрат со стороной 1м, в котором мышь прогрызла минимум три дырки. Его можно залатать одной заплаткой.

Задача 21. Олимпиаду писали 70 школьников. Аркаша набрал 33 балла, остальные меньше. Докажите, что по крайней мере три школьника набрали одинаковое количество баллов                                  

Решение: Предположим, что не нашлось таких трёх школьников. Тогда одинаковое количество баллов (от 0 до 32) набрали не более двух школьников. Тогда школьников, не считая Аркаши, не более 33·2 = 66, а их 69. Противоречие, а значит такие три школьника найдутся.

Задача 22. Семь волков съели 50 кроликов. Докажите, что один из волков съел не менее 8 кроликов.

Доказательство. Предположим противоположное – что такого волка не найдется. Т.е. каждый волк съел менее 8 кроликов. Так как волков 7, то они вместе съели не более 49 кроликов, а по условию волки съели 50 кроликов. Получили противоречие, значит, наше предположение не верно, следовательно, верно прямое утверждение. Один из волков съел не менее 8 кроликов.

Задача 23. В партии из 300 сапог 150 левых и 150 правых, кроме того, по 100 штук каждого из трех размеров. Докажите, что есть по крайней мере 50 годных пар обуви.

Решение: В каждом размере либо левых и правых поровну, либо каких-то больше. Если левых и правых поровну, то их по 50 – вот мы и нашли 50 годных пар. Пусть в каждом размере или левых или правых больше. Можно считать, что в двух размерах больше левых, а в еще одном больше правых. (Во всех трех размерах левых быть больше не может, так как всего левых и правых сапог поровну).