Упражнения

1. (5-6 класс) В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающие дни рождения в один месяц.
Решение. Количество месяцев 12 – выполняют роль «клеток», количество учащихся 15 – роль «кроликов». Если 15 кроликов рассадим по 12 клеткам, то в одной клетке окажется, по крайней мере 2 кролика, т.е. в одном месяце как минимум найдутся 2 ученика, отмечающие дни рождения. 
2. (5-6 класс) Дано 12 целых чисел. Докажите, что из них можно выбрать два числа, разность которых делится на 11.
Решение. Решение этой  задачи  можно начать с вопроса о количестве различных остатков от деления числа на 11. Получив  ответ, что их  ровно 11, можно сделать вывод о том,  что среди 12  чисел найдутся, по крайней мере, два, имеющие одинаковые  остатки. Разность этих  чисел  и будет делится  на 11. 
3. (5-6 класс) В ковре размером 3х3 метра Коля проделал 8 дырок. Докажите, что из него можно вырезать коврик размером 1 метр на 1 метр, не содержащий внутри себя дырок (дырки можно считать точечными).
Решение. Разобьем ковер-квадрат 3х3 метра на 9 квадратиков 1х1 метр. Количество ковриков  1х1 метр 9 – выполняют роль «кроликов», количество дырок 8 – роль «клеток». Найдется хотя бы один коврик 1х1 метр, не содержащий дырок. 
4. (5-6 класс) В классе 35 учеников. Можно ли утверждать, что среди них найдутся хотя бы два ученика, фамилии которых начинаются с одной буквы?
Решение. В русском алфавите 33 буквы, которые выполняют роль «клеток», 35 учеников выполняют роль «кроликов». Поэтому найдутся хотя бы два ученика, фамилии которых начинаются с одной буквы.
5. (5-6 класс) На дискотеку в студенческое общежитие, в котором 42 комнаты, пришло 36 гостей. Докажите, что найдется комната, в которую не пришёл ни один гость.
Решение. Если бы в каждую комнату пришел хотя бы один гость, то количество гостей было бы более 42 человек, что противоречит условию (36 гостей).
6.  (5-6 класс) Шесть школьников съели семь конфет.  Докажите, что один из них съел не менее двух конфет.
Решение. Вопрос: что мы примем за «клетки», а что за «кролики»? Если 7 кроликов рассадим по 6 клеткам, то в одной клетке окажется по крайней мере 2 кролика, т.е. один ученик съел как минимум 2 конфеты. 
7. (5-6 класс) В мешке лежат шарики двух разных цветов: черного и белого. Какое наименьшее число  шариков  нужно  вынуть  из  мешка вслепую так, чтобы среди них заведомо оказались два шарика  одного цвета?
Решение. Достанем из мешка 3 шарика. Если бы среди этих шариков было не более одного шарика каждого из двух цветов, то всего было бы не более двух шаров – это очевидно, и противоречит тому, что мы достали три шарика (снова же, обратите внимание – использован метод от противного). С другой стороны понятно, что двух шариков может и не хватить. Ясно, что «кроликами» здесь являются шарики, а «клетками» - цвета: черный и белый.
8. (7-8 класс) В классе 26 учеников, из них более половины – мальчики. Докажите, что какие-то  2 мальчика сидят за одним столом, если в классе 13 столов.
Решение. Так как мальчиков больше чем столов, то найдутся какие-то  2 мальчика, сидящие за одним столом.
9. (7-8 класс) Внутри равностороннего треугольника со стороной 1 см расположено 5 точек. Докажите, что расстояние между некоторыми двумя из них меньше 0,5 см.
См. решение задачи 15.
10. (7-8 класс) Можно ли окрасить клетки таблицы  так, чтобы во всех строках и во всех столбцах таблицы число закрашенных клеток было различно?
Решение. Число закрашенных клеток может изменяться от 0 до 7, т.е. всего имеем 8 вариантов. Строк и столбцов всего 11. По принципу Дирихле получим, что в каких-то двух линиях (строках и столбцах) будет одинаковое число закрашенных клеток.
Ответ. Нельзя.
11. (7-8 класс) В городе N более 201 улицы. На каждой улице не менее 52 и не более 252 домов. Докажите, что найдутся, по меньшей мере, две улицы с одинаковым числом домов.
Решение. От 52 до 252 имеется 201 различное значение числа домов на улице. Однако улиц больше, чем 201. Поэтому по принципу Дирихле уже среди 202 улиц найдутся по меньшей мере 2 улицы с одинаковым числом домов.
Здесь улицы – «зайцы», а число домов на улице – «клетки».
12. (7-8 класс) 10 друзей послали друг другу праздничные открытки. Каждый послал 5 открыток. Докажите, что двое послали открытки друг другу.
Решение.  Всего было отправлено 50 открыток. Значит, существует участник, который получил не менее пяти открыток (если бы каждый получил не более четырёх, то всего было бы отправлено не более 40 открыток). Таким образом, он послал открытки пятерым участникам и получил открытки не менее чем от пяти участников. Поскольку, кроме него, имеется лишь 9 участников, то хотя бы один другой участник входит в обе пятёрки. 
13. (7-8 класс) В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка - точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.  
Решение.   «Клетки» - 25 заплаток; «кролики» 51 моль. Весь ковер можно накрыть такими 25-ю заплатами. По принципу Дирихле какая-то из этих заплат накроет не менее трех дырок.
14. (7-8 класс) В классе 25 человек. Известно, что среди любых трёх из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей. 
Решение. Выберем любых двух учеников класса, которые не дружат между собой. (Если таких нет, то все ученики класса дружат между собой, значит, у каждого имеется 24 друга, и задача решена.) Из оставшихся 23 учеников каждый дружит с одним из этих двух, иначе мы имели бы тройку учеников, среди которых не было бы друзей. Тогда у одного из выбранных двух учеников не менее 12 друзей.
15. (7-8 класс) Внутри равностороннего треугольника со стороной 1 расположено пять точек. Доказать, что расстояние между некоторыми двумя из них меньше 0,5.
Решение. Средние линии правильного треугольника со стороной 1 разбивают его на 4 правильных треугольника со стороной 0,5. Поэтому в одном из них лежат, по крайней мере, две данные точки, причем эти точки не могут попасть в вершины треугольника. Расстояние между этими точками меньше 0,5.
16. (7-8 класс) Докажите, что из любых трех натуральных чисел можно найти два, сумма которых делится на 2.
Решение. Среди трёх целых чисел обязательно найдутся два числа одинаковой чётности (так как чисел 3, а классов – четных и нечетных – два). Сумма этих чисел будет делиться на 2.
17. (7-8 класс)Винни-Пух, Сова, Кролик и Пятачок вместе съели 70 бананов, причем каждый из них съел хотя бы один банан. Винни-Пух съел больше всех, Сова и Кролик вместе съели 45 бананов. Сколько бананов съел Пятачок?
Решение. Т.к. Сова и Кролик съели вместе 45 бананов, то, по следствию из принципа Дирихле, кто-то из них съел не меньше, чем  банана, т.е. не меньше 23 бананов.  Винни-Пух и Пятачок вместе съели          70-45=25 бананов. Т.к. Винни-Пух съел больше всех, то он съел больше 23 бананов, а т.к. по условию каждый съел хотя бы один банан, то Винни-Пух съел 24 банана, а Пятачок 1 банан.
Ответ. Пятачок съел один банан.
18. (7-8 класс) Докажите, что в любой компании из пяти человек двое имеют   одинаковое число знакомых.
Решение. Имеются пять вариантов числа знакомых: от 0 до 4.Остается заметить, что если у кого-то четверо знакомых, то ни у кого не может быть ноль знакомых. ("Клетки", соответствующие 0 и 4, взаимно исключают друг друга.) Поэтому можно говорить о четырех “ клетках “- вариантах числа знакомых. Поскольку в компании пять человек – “зайцев ”, по принципу  Дирихле обязательно найдутся хотя бы два человека, имеющие   одинаковое число знакомых.
19. (7-8 класс) 10 школьников на олимпиаде решили 35  задач, причем  известно, что  среди  них  есть  решившие ровно одну задачу, решившие ровно две задачи и решившие ровно три задачи. Докажите, что среди них есть школьник, решивший не менее  пяти задач.
Решение. Из  условия  задачи  можно заключить,  что найдутся семь школьников, решивших    35 – (1 + 2 + 3) = 29  задач. Так как 29 = 7 · 4 + 1, то найдется школьник, решивший не  менее  5 задач.
20. (7-8 класс) Если 30 человек рассадить в зале кинотеатра, то хотя бы в одном ряду окажется не менее двух человек. Если в зале рассадить 26 человек, то по крайней мере 3 ряда окажутся пустыми. Сколько рядов в зале?
Решение. Если рядов в зале больше 29, то можно рассадить 30 человек так, что во всех рядах будет не больше одного человека, что противоречит условию, значит, рядов в зале не больше 29. Если в зале меньше 29 рядов, то можно рассадить 26 человек так, что менее трех рядов окажутся пустыми, что также противоречит условию, значит, в зале не менее 29 рядов. Следовательно, в зале ровно 29 рядов.
21. (7-8 класс) 15 мальчиков собрали 100 орехов. Докажите, что какие-то два из них собрали одинаковое число орехов.
Решение. Пусть это не так, т.е. все мальчики собрали разное число орехов. Тогда они должны были собрать не менее, чем 0+1+2+…+14=105 орехов. Противоречие.
22. (8-9 класс) В розыгрыше кубка по футболу (в один круг) участвуют 30 команд. Доказать, что в любой момент найдутся две команды, сыгравшие одинаковое число игр.
Решение. 1 случай: хотя бы одна команда не сыграла еще ни одной игры.
Тогда количество игр у любой команды не больше 28, т.е. возможное число игр у любой команды принимает одно из 29 значений: 0,1,2,…,28. Разбив 30 команд на 29 групп по числу сыгранных игр, мы найдем группу, в которой не меньше двух команд.
2 случай: каждая команда сыграла хотя бы одну игру; количество игр принимает одно из значений:1,2,3,…,29.Опять число команд больше числа игр, поэтому найдутся две команды, сыгравшие одинаковое количество игр.
23. (8-9 класс) На планете Тау - Кита суша занимает более половины площади              планеты. Докажите, что тау-китяне  могут  прорыть  тоннель, проходящий через  центр планеты и соединяющий сушу с сушей.
Решение.       Покрасим всю сушу в синий цвет, а все точки, диаметрально противоположные суше – в красный. Площади синей и красной частей планеты будут равными. Если все красные точки покрыты водой, получаем противоречие с условием задачи. Поэтому найдется точка, покрашенная в оба цвета. В ней и надо рыть туннель.
24.  (9-11 класс) На плоскости нарисовали 5 прямых. Докажите, что угол между какими-то двумя из них не больше 36°. (Если какие-нибудь прямые параллельны, считайте, что угол между ними равен 0°).
Решение. Отметим на плоскости произвольную точку и переместим параллельными переносами все прямые так, чтобы они проходили через эту точку. Величины углов между прямыми при этом не изменятся. Теперь мы получили пять прямых, проходящих через одну точку, которые образовали 10 углов (внутренние области которых не пересекаются). Сумма величин этих углов равна 360°. Если бы все эти величины были больше 36°, то их сумма была бы больше 360°. Следовательно, величина хотя бы одного из этих десяти углов не превышает 36°. 
В данной задаче «клетки» - 10 углов; «кролики» - 3600.
25. (8-11 класс) Докажите, что среди любых 6 человек либо трое попарно знакомых, либо трое попарно незнакомых.
Решение. Рассмотрим произвольного человека А. Среди 5 других найдутся трое, знакомых с А,  или трое, незнакомых с А. Действительно, если так не будет, то людей, знакомых с , максимум двое; людей, незнакомых с , также максимум двое. Получим, что всего мы рассматриваем 1+2+2=5 человек, а по условию, людей 6. Получили противоречие с условием. Т.о. найдутся трое, знакомых с А,  или трое, незнакомых с А. Для определенности положим, что эти  трое знакомы с А. Если из этих троих какие-то двое знакомы друг с другом, то вместе с человеком А они составляют тройку попарно знакомых. Если среди этих троих нет знакомых, то они составляют  тройку незнакомых между собой людей.
Здесь «зайцы» - 5 человек, а «клетки» (их две) – это отношение этих людей к  («знакомы» и «незнакомы»).
26. (10-11 класс) Шесть кругов имеют общую внутреннюю точку. Докажите, что центр одного из них лежит внутри другого.
Решение. 

Соединим общую точку со всеми центрами. Образовалось 6 углов; по следствию из принципа Дирихле один из них не превышает =. Рассмотрим два круга, центры которых породили этот угол. Докажем, что один из этих кругов содержит центр другого. Назовем общую точку точкой , а два выбранных центра точками  (центр круга с радиусом ) и  (центр круга с радиусом ). Рассмотрим треугольник , где . 
Среди углов этого треугольника обязательно найдется угол, не меньший, чем  (следствие из принципа Дирихле). Пусть это угол . Тогда получили: , отсюда следует, что  (соотношения между сторонами и углами треугольника). Т.к.  - внутренняя точка кругов, то . Таким образом, получаем , это и означает, что точка  лежит внутри круга с центром .
Еще возможен случай, когда точки ,  и  лежат на одной прямой, причем центры кругов лежат по одну сторону от точки  (), в данном случае  утверждение задачи очевидно.
27. (10-11 класс) Первоклассник Петя знает только цифру 1. Доказать, что он может написать число, делящееся на 1997.
Решение. Рассмотрим последовательность a1 = 1, a2 = 11, . . . , an = = 11. . .1, . . . чисел, десятичная запись которых состоит из одних единиц. Поскольку существует лишь конечное число остатков от деления на 1997, а последовательность содержит бесконечно много членов, то, согласно принципу Дирихле, среди них найдутся два, дающих одинаковые остатки: ak и al (k > l). Их разность ak - al = 10l·ak - l делится на 1997. Так как 10l и 1997 - взаимно просты, то ak - l делится на 1997. Это число Петя сможет записать.  
28. (10-11 класс) Дана фигура площади больше N. Доказать, что в ней найдутся N+1 точек, разности соответствующих координат которых - целые числа.
Решение. Разобьём исходную фигуру параллельными прямыми, расположенными на расстоянии 1, на клетки. (В качестве таких прямых можно взять, например, линии целочисленной сетки.) Некоторые клетки будут покрываться фигурой полностью, другие - лишь частично. Выделим какую-нибудь одну клетку и с помощью параллельных переносов перенесём на эту клетку все кусочки фигуры, которые получились в результате её пересечения со всеми клетками. {Наглядно это можно описать так. Представьте, что фигура нарисована на клетчатой бумаге. Разрежьте бумагу по клеткам и сложите их в стопку, перенося их параллельно и не переворачивая, а затем спроектируйте стопку на выделенную клетку.} 
Площади проекций частей фигуры в сумме дадут площадь самой фигуры, т.е. больше N. Поэтому на выделенной клетке (площади 1) согласно принципу Дирихле найдётся точка X, покрытая не менее N+1 кусочками фигуры. Вернёмся теперь к исходной фигуре и отметим на ней N+1 точек, проектирующихся в точку X при переносе клеток. Эти точки будут искомыми, т.к. после переноса кусочка фигуры в выделенную клетку координаты каждой точки этого кусочка изменяются на целое число.