Сборник задач по теме: «Принцип Дирихле»

СБОРНИК ЗАДАЧ

ПО ТЕМЕ:

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

 

       Если в n клетках сидит m зайцев, причём m>n , то хотя бы в одной клетке сидят, по крайней мере, два зайца

         Доказательство:

         Пусть не найдётся такой клетки, в которой сидят два зайца, тогда количество зайцев m должно быть меньше или равно количеству клеток n, что приводит нас к противоречию

         В несерьёзной форме принцип Дирихле гласит: «Нельзя посадить 7 кроликов в 3 клетки, чтобы в каждой было не больше 2 кроликов».

         Алгоритм применения принципа Дирихле для решения задач:

         1. Определить, что в задаче является «клетками» , а что - «зайцами».

         2.Применить соответствующую формулировку принципа Дирихле.

ЗАДАЧИ

         Задача 1. В розыгрыше кубка по футболу (в один круг) участвуют 30 команд. Доказать, что в любой момент найдутся две команды, сыгравшие одинаковое число игр.

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

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

         Задача 4. Доказать, что найдется число вида 200120012001…2001001…0, которое делится на 2002.

         Задача 5. В классе 30 учеников. Саша Иванов в диктанте сделал 13 ошибок, а остальные – меньше. Докажите что, по крайней мере 3 ученика сделали ошибок поровну (может быть по 0 ошибок).

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

         Задача 7. В строку выписано 5 натуральных чисел: а1, а2, а3, а4, а5. Докажите, что либо одно из них делится на 5, либо сумма нескольких рядом стоящих чисел делится на 5.

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

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

         Задача 10. В пионерском отряде 22 пионера. Можно утверждать, что среди пионеров найдутся хотя бы два, имена которых начинаются с одной и той же буквы?

         Задача 11. В школе 400 учеников, почему среди учащихся этой школы обязательно найдутся хотя бы два ученика, родившихся в один и тот же день года?

         Задача 12. В школе 735 учащихся. Почему можно утверждать, что, по крайней мере, три ученика должны отмечать день своего рождения в один и тот же день?

         Задача 13. В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.

         Задача 14. Дано 12 целых чисел. Докажите, что из них можно выбрать два, разность которых делится на 11.

         Задача 15. В городе Ленинграде живет более 5 миллионов человек. Докажите, что у каких-то двух из них одинаковое число волос на голове, если известно, что у любого человека на голове менее миллиона волос.

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

         Задача 17. В стране Курляндии m футбольных команд (по 11 футболистов в каждой). Все футболисты собрались в аэропорту для поездки в другую страну на ответственный матч. Самолет сделал 10 рейсов, перевозя каждый раз по m пассажиров. Еще один футболист прилетел к месту предстоящего матча на вертолете. Докажите, что хотя бы одна команда была целиком доставлена в другую страну.

         Задача 18.  Дано 8 различных натуральных чисел, не больших 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.

         Задача 19. Докажите, что в любой компании из 5 человек есть двое, имеющие одинаковое число знакомых в этой компании.

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

         Задача 21.

а) Какое наибольшее число полей на доске 8 ? 8 можно закрасить в черный цвет так, чтобы в любом уголке вида из трех полей было по крайней мере одно незакрашенное поле?

б) Какое наименьшее число полей на доске 8 ? 8 можно закрасить в черный цвет так, чтобы в каждом уголке вида было по крайней мере одно черное поле?

         Задача 22. 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть школьники, решившие ровно одну задачу, школьники, решившие ровно две задачи и школьники, решившие ровно три задачи. Докажите, что есть школьник, решивший не менее пяти задач.

         Задача 23. Какое наибольшее число королей можно поставить на шахматной доске так, чтобы никакие два из них не били друг друга?

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

         Задача 25. В квадрат со стороной 1 метр бросили 51 точку. Докажите, что какие-то три из них можно накрыть квадратом со стороной 20 см.

         Задача 26. Пятеро молодых рабочих получили на всех зарплату – 1500 рублей. Каждый из них хочет купить себе магнитофон ценой 320 рублей. Докажите, что кому-то из них придется подождать с покупкой до следующей зарплаты.

         Задача 27. В бригаде 7 человек и их суммарный возраст – 332 года. Докажите, что из них можно выбрать трех человек, сумма возрастов которых не меньше 142 лет.

         Задача 28. Докажите, что среди степеней двойки есть две, разность которых делится на 1987.

         Задача 29. Докажите, что из 52 целых чисел всегда найдутся два, разность квадратов которых делится на 100.

         Задача 30. Докажите, что среди чисел, записываемых только единицами, есть число, которое делится на 1987.

         Задача 31. Докажите, что существует степень тройки, оканчивающаяся на 001.

         Задача 32. Цифры 1, 2, …, 9 разбили на три группы. Докажите, что произведение чисел в одной из групп не меньше 72.

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

         Задача 34. 15 мальчиков собрали 100 орехов. Докажите, что какие-то два из них собрали одинаковое число орехов.

         Задача 35. В таблице 10 ? 10 расставлены целые числа, причем любые два числа в соседних клетках отличаются не более, чем на 5. Докажите, что среди этих чисел есть два равных.

         Задача 36. Докажите, что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых.

         Задача 37. На клетчатой плоскости дано 5 произвольных узлов сетки. Докажите, что середина одного из отрезков, соединяющих какие-то две из этих точек, также является узлом сетки.

         Задача 38. На складе имеется по 200 сапог 41, 42 и 43 размеров, причем среди этих 600 сапог 300 левых и 300 правых. Докажите, что из них можно составить не менее 100 годных пар обуви.

         Задача 39. В алфавите языка племени Ни-Бум-Бум 22 согласных и 11 гласных, причем словом в этом языке называется произвольное буквосочетание, в котором нет двух согласных подряд и ни одна буква не использована дважды. Алфавит разбили на 6 непустых групп. Докажите, что из всех букв одной из групп можно составить слово.

         Задача 40. Докажите, что среди любых 10 целых чисел найдется несколько, сумма которых делится на 10.

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

ОТВЕТЫ и указания к некоторым заданиям

         Задача 1. Решение. Рассмотрим два случая.

1. Хотя бы одна из 30 команд не сыграла еще ни одной игры.

2. Каждая команда сыграла хотя бы одну игру. Докажем утверждение для 1-го случая. Так как хотя бы одна из 30 команд не сыграла еще ни одной игры, то число игр у любой команды не более 28, то есть возможное число игр у каждой из команд может быть: 0, 1, 2, …, 28 (всего 29 чисел), а команд по условию 30. Тогда по принципу Дирихле, приняв в качестве «классов» числа проведенных игр (всего 29 «классов»), а в качестве «предметов» - команды (всего 30 «предметов»), получим, что хотя бы 2 команды будут соответствовать одному числу проведенных игр, а значит, хотя бы 2 команды сыграли одинаковое число игр. Докажем утверждение для 2-го случая. Так как каждая из 30 команд сыграла хотя бы одну игру, то число проведенных игр может принимать значения: 1, 2, …, 29 (всего 29), я команд 30, тогда по принципу Дирихле найдутся хотя бы 2 команды, сыгравшие одинаковое число игр.

         Задача 2. Решение. Из теории делимости известно, что разность чисел (a – b) делится на m тогда и только тогда, когда a и b при делении на m дают одинаковые остатки. Учитывая это утверждение, переформулируем задачу: Доказать, что среди шести любых чисел найдутся два числа, которые при делении на пять, дают одинаковые остатки. Докажем это утверждение: По теореме о делении с остатком, при делении числа на пять может быть один из пяти остатков: 0, 1, 2, 3, 4. При этом рассматриваются шесть любых чисел. 6>5, по принципу Дирихле получаем, что, приняв в качестве «классов» – остатки, в качестве «предметов» - числа, учитывая, что хотя бы два числа из шести имеют одинаковые остатки при делении на пять, а значит, их разность делится на пять.

            Задача 3. Решение. Каждая из девяти прямых разбивает квадрат либо на два прямоугольника, либо на две трапеции. Площадь трапеции равна , где h – высота трапеции (в нашем случае сторона квадрата), C – длина средней линии трапеции (отрезок на средней линии квадрата). Так как по условию площади получившихся трапеций или прямоугольников делятся как 2:3, то в том же отношении (п.2) прямая делит и среднюю линию квадрата. Таких точек, которые делят одну из средних линий квадрата в отношении 2:3 всего 4, прямых по условию 9, и каждая из них должна пройти через одну из этих точек. И так «классов» – 4, «предметов» –9>2*4, тогда по принципу Дирихле, найдется три прямых проходящих через одну из этих четырех точек.  

         Задача 4. Решение. Рассмотрим 2002 числа 2001, 20012001, …, . Рассмотрим остатки от деления каждого числа на 2002: ни одно из этих чисел не делится на 2002, так как это число четное, а числа п.1 нечетные, поэтому возможные остатки: 1, 2, …, 2001 (всего 2001). Так как чисел из п.1 больше чем возможных остатков, то по принципу Дирихле найдутся хотя бы два из этих чисел, которые при делении на 2002 дадут одинаковые остатки. Разносить чисел, имеющих одинаковые остатки при делении на 2002, делится на 2002 и имеет вид 20012001…2001000…0.

         Задача 5. Решение. В качестве «зайцев» будем рассматривать учеников. Под «клетками» будем подразумевать – число сделанных ошибок. В клетку 0 «посадим» всех, кто не сделал ни одной ошибки, в клетку 1 – тех, у кого одна ошибка, в клетку 2 – две… и так до клетки 13, куда попал только Саша Иванов. Теперь применим принцип Дирихле. Докажем утверждение задачи от противного. Предположим, что никакие три ученика не сделали по одинаковому числу ошибок, т.е. в каждую из «клеток» 0, 1, 2, …,12 попало меньше трех школьников. Тогда в каждой из них два человека или меньше, а всего в этих «клетках» не более 2·12=26 человек. Добавив Сашу Иванова, все равно не наберем 30 ребят. Противоречие. Следовательно, утверждение задачи верно, по крайней мере, трое учеников сделали поровну ошибок.

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

         Задача 7. Решение. Рассмотрим 5 чисел а1, а1+ а2, а1+ а2+ а3, а1,+а2+ а3+ а4, а1,+а2+ а3+ а4+ а5 Если одно из них делится на 5, то утверждение справедливо. В противном случае при делении на 5 они дают в остатке какие-то из четырех чисел: 1, 2, 3, 4. По принципу Дирихле остатки, по крайней мере, двух из выписанных 5 чисел совпадают. Тогда их разность делится на 5. Но разность эта – одно из чисел, данных в задаче, или сумма нескольких из них, стоящих рядом.

         Задача 8. Решение: Предположим, что нашлась задача, которую решили не более двух девочек или не более двух мальчиков. Будем считать задачу «красной», если её решили не более двух девочек и «чёрной» в противоположном случае (тогда её решили не более двух мальчиков). Представим шахматную доску с 21-й строкой, каждая из которых соответствует девочке, и 21-м столбцом, каждый из которых соответствует мальчику. Тогда каждая клетка соответствует паре «мальчик–девочка». Каждую клетку покрасим в цвет какой-нибудь задачи, которую решили и мальчик- строка и девочка-столбец. По принципу Дирихле в каком-нибудь столбце найдётся 11 чёрных клеток, или в какой-нибудь строке найдутся 11 красных клеток (потому что иначе получится, что всего клеток не более чем 21 • 10 + 21 • 10 < 21²). Рассмотрим, например, девочку-строку, содержащую хотя бы 11 чёрных клеток. Каждой из этих клеток соответствует задача, решённая максимум двумя мальчиками. Тогда мы можем указать не менее 6 различных задач, решённых этой девочкой. В силу первого условия никаких других задач девочка не решала, но тогда максимум 12 мальчиков имеют общие решённые задачи с этой девочкой, что противоречит второму условию. Точно также разбирается случай, если в каком-нибудь столбце найдутся 11 красных клеток.

         Задача 9. Ответ: да.

         Задача 10. Ответ: нет.

         Задача 11.  Ответ: потому, что в году 365 дней.

         Задача 12.  Ответ: если бы в каждый день года родились два ученика, то всего в школе было бы не более чем 2·366=732 учащихся

         Задача 13. Перед нами миллион «кроликов»-елок и, увы, всего лишь 600001 клетка с номерами от 0 до 600000. Каждый «кролик»-елка сажается нами в клетку с номером, равным количеству иголок на этой елке. Так как «кроликов» гораздо больше, чем клеток, то в какой-то клетке сидит по крайней мере два «кролика» – если бы в каждой сидело не более одного, то всего «кроликов»-елок было бы не более 600001 штук. Но ведь, если два «кролика»-елки сидят в одной клетке, то количество иголок у них одинаково.

         Задача 14. Остатки по модулю 11 – «клетки», числа – «кролики».

         Задача 15. Постройте миллион клеток с номерами от 0 до 999999 и рассадите там людей, поместив каждого ленинградца в клетку, номер которой равен количеству волос на его голове.

         Задача 16. 25 ящиков-«кроликов» рассадим по 3 клеткам-сортам. Так как 25 = 3 • 8 + 1, то применим «обобщенный принцип Дирихле» для N = 3, k = 8 и получим, что в какой-то клетке-сорте не менее 9 ящиков.

         Задача 17. Так как перевезено всего 10m + 1 футболистов, то, рассадив их по клеткам-командам, получаем, что в какой-то клетке сидит 11 футболистов.

         Задача 18. Различных разностей может быть 14 – от 1 до 14 – это те 14 клеток, в которые мы будем сажать кроликов. Кто же будет нашими кроликами? Ими, конечно, должны быть разности между парами данных нам натуральных чисел. Однако имеется 28 пар и их можно рассадить по 14 клеткам так, что в каждой клетке будет сидеть ровно два «кролика» (и значит, в каждой меньше трех). Здесь надо использовать дополнительное соображение: в клетке с номером 14 может сидеть не более одного кролика, ведь число 14 можно записать как разность двух натуральных чисел, не превосходящих 15, лишь одним способом: 14 = 15 – 1. Значит, в оставшихся 13 клетках сидят не менее 27 кроликов, и применение обобщенного принципа Дирихле дает нам желаемый результат.

         Задача 19. Докажите, что в любой компании из 5 человек есть двое, имеющие одинаковое число знакомых в этой компании.

         Задача 20. Пусть всего команд n. Тогда вариантов числа команд, с которыми сыграла данная команда n: от 0 до n – 1. Осталось заметить, что если одна команда сыграла со всеми n – 1-й, то никакая другая команда не могла ни с кем не сыграть.