Методические указания по теме «П Р И Н Ц И П Д И Р И Х Л Е»
При решении многих задач используются сходные между собой приемы рассуждений, получившие название “ принципа Дирихле “. Задачи на принцип Дирихле воспитывают у учащихся умение устанавливать соответствие между элементами двух множеств. На решение задач по принципу Дирихле нужно посвятить несколько занятий, которые могут быть разделены занятиями на другие темы. Принцип Дирихле можно давать прямо на первых уроках, так как он достаточно рельефно характеризует специфику олимпиадных задач. Кроме того, многие задачи используют идеи принципа Дирихле в решении всей задачи или какой-то её части.
П Р И Н Ц И П Д И Р И Х Л Е.
В самой простой и несерьезной форме принцип Дирихле выглядит так: “нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев “. Другая формулировка “ принципа Дирихле“: если n + 1 предмет поместить в n мест, то обязательно хотя бы в одном месте окажутся хотя бы два предмета. Заметим, что в роли предметов могут выступать и математические объекты - числа, места в таблице, отрезки и т.д.
Задача 1. В корзине лежат 30 грибов - рыжиков и груздей. Известно, что среди любых 12 грибов имеется хотя бы один рыжик, а среди любых 20 грибов - хотя бы один груздь. Сколько рыжиков и сколько груздей в корзине.
Решение:19 рыжиков и 11 груздей. Если бы в корзине нашлись 12 груздей, то ни один из них не был бы рыжиком, следовательно, количество груздей не превосходит 11. Если бы груздей было меньше 11, то их было бы не больше 10. В этом случае можно было бы найти 20 не груздей, следовательно, груздей - 11. Рыжиков - 19.
Задача 2. В мешке лежат шарики двух разных цветов: черного и белого. Какое наименьшее число шариков нужно вынуть из мешка вслепую так, чтобы среди них заведомо оказались два шарика одного цвета?
Решение: Достанем из мешка 3 шарика. Если бы среди шариков было не более одного шарика каждого из двух цветов, то всего было бы не более двух шариков - это очевидно, и противоречит тому, что мы достали 3 шарика. С другой стороны, понятно, что двух шариков может и не хватить. Ясно, что “ зайцами ” здесь являются шарики, а “ клетками” - цвета: черный и белый.
Задача 3. В магазин привезли 25 ящиков с тремя сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков одного сорта.
Решение: В решении этой задачи нам поможет обобщенный принцип Дирихле: “ Если в n клетках сидят не менее kn + 1 зайцев, то в какой-то из клеток сидит, по крайней мере, k + 1 заяц. 25 ящиков – “зайцев” - рассадим по 3 “клеткам” - cортам. Так как 25 = 3 * 8 + 1, то, применив обобщенный принцип Дирихле для n = 3, k = 8, получим, что в какой-то “ клетке” – сорте не менее 9 ящиков.
Задача 4. В квадрате со стороной 1 м бросили 51 точку. Докажите, что какие-то 3 точки из них можно накрыть квадратом со стороной 20 см.
Решение: Разобьем квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле в какой-то из них попадет по крайней мере 3 точки из 51 брошенной.
Заметим, что в основе принципа лежит идея сложения неравенств. Одно замечательное свойство из неё гласит: ” Если сумма n чисел равна S, то среди них есть как число не большее S:n и число не меньшее S:n ”.
Задача 5. В бригаде 7 человек и их суммарный возраст 332 года. Докажите, что из них можно выбрать трех человек, сумма возрастов которых не меньше 142.
Решение: Рассмотрим всевозможные тройки рабочих бригад. Сумма их суммарных возрастов, как легко подсчитать, равна 15*332, а таких троек 35. Значит, есть тройка, суммарный возраст в которой не меньше, чем (15*332):35, что больше 142.
Задача 6. В непрозрачном мешке лежат 5 белых и 2 черных шара. а) Какое наименьшее число шаров надо вытащить из мешка, чтобы среди них обязательно оказался хотя бы один белый шар?
Решение: “Худшим”, здесь является случай, когда мы будем вытаскивать все время черные шары. В этом случае, даже вытащив подряд 2 шара, мы не вытащим белого шара. Но если мы вы тащим 3 шара, то тогда уж точно из трех шаров по крайней мере один шар будет белым.
б) Сколько шаров надо вытащить, чтобы среди них обязательно оказался хотя бы один белый и хотя бы один черный шар?
Решение: “ Худшим ” здесь является случай, когда мы сначала будем вытаскивать одни белые шары и только потом попадается один черный шар. Поэтому потребуется вытащить 5 + 1 = 6 шаров.
в) Какое наименьшее число шаров надо вытащить, чтобы среди них наверняка оказались 3 белых и 1 черный шар?
Решение: В “ худшем “ случае мы сначала вытащим все белые шары, и затем лишь пойдут черные. Тогда придется вытащить 5 + 1 =6 шаров.
г) Сколько шаров надо вытащить, чтобы среди них оказались два шара одного цвета?
Решение: “ Худший “ случай - когда сначала идут шары разных цветов. Это возможно, если мы вытащим 2 шара. А если мы вытащим третий, то уже будем иметь два шара одного цвета.
Задача 7. Cколько надо взять двузначных чисел, чтобы по крайней мере одно из них делилось: а) на 2, б) на 7?
Решение: а) В “ худшем “ случае, вытаскивая из мешка числа от 10 до 99, мы сначала будем иметь только нечетные числа - их 45, и поэтому 46-е число обязательно будет четным.
б) Среди 90 чисел от 10 до 99 имеется всего 13 чисел, делящихся на 7, т.е. в “худшем ” случае мы сначала вытащим 90 - 13 = 77 чисел, не делящихся на 7, но 78-е число уже точно будет делиться на 7.
Задача 8. Дано 12 целых чисел. Докажите, что из них можно выбрать два, разность которых делится на 11.
Решение: Решение этой задачи можно начать с вопроса о количестве различных остатков от деления числа на 11. Получив ответ, что их ровно 11, можно сделать вывод о том, что среди 12 чисел найдутся, по крайней мере, два, имеющие одинаковые остатки. Разность этих чисел и будет делится на 11. После этого надо найти “ зайцев” (12 чисел) и “ клетки ” (остатки от деления на 11).
Задача 9. Докажите, что в любой копании из пяти человек двое имеют одинаковое число знакомых.
Решение: Имеются пять вариантов числа знакомых: от 0 до 4.Остается заметить, что если у кого-то четверо знакомых, то ни у кого не может быть ноль знакомых. ("Клетки", соответствующие 0 и 4, взаимно исключают друг друга.) Поэтому можно говорить о четырех “ клетках “- вариантах числа знакомых. Поскольку в компании пять человек – “зайцев ”, по принципу Дирихле обязательно найдутся хотя бы два человека, имеющие одинаковое число знакомых.
Задача 10. 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть решившие ровно одну задачу, решившие ровно две задачи и решившие ровно три задачи. Докажите, что среди них есть школьник, решивший не менее пяти задач.
Решение: Из условия задачи можно заключить, что найдутся семь школьников, решивших 35 - (1 + 2 + 3) = 29 задач. Так как 29 = 7 * 4 + 1, то найдется школьник, решивший не менее 5 задач.
Задача 11. В школе 20 классов. В ближайшем доме живут 23 ученика этой школы. Можно ли утверждать, что среди них обязательно найдутся хотя бы два одноклассника?
Решение: Можно, так как классов (20) меньше, чем учеников (23).
Задача 12. В школе учится 370 человек. Докажете, что среди всех учащихся найдутся два человека, празднующие свой день рождения в один и тот же день.
Решение: В году 365 дней, следовательно, у 5 учеников дни рождения могут совпасть.
Задача 13. Коля подсчитал, что за завтрак, обед и ужин он съел 10 конфет. Докажите, что хотя бы один раз он съел не меньше 4 конфет.
Решение: Доказываемое утверждение следует из равенства: 10 = 3*3 + 1
Задача 14. В классе 37 человек. Докажите, что среди них найдутся 4 человека с одинаковым числом дня рождения.
Решение: В любом месяце дней не более 31, значит, для 37 учеников есть одинаковые числа, месяц роли не играет.
Задача 15. В ящике комода, который стоит в темной комнате, лежат 10 коричневых и 10 красных носков одного размера. Сколько носков нужно достать, чтобы среди них была пара одинакового цвета?
Решение: 3 носка.
Задача 16. Имеются три ключа от трех чемоданов с разными замками. Достаточно ли трех проб, чтобы открыть чемодан?
Решение: Достаточно.
Задача 17. Какое наибольшее число полей на доске 8 Х 8 можно закрасить в черный цвет так, чтобы в любом уголке вида из трех полей было бы по крайней мере одно незакрашенное?
Решение: 32 клетки.
Задача 18. Цифры 1, 2, 3, 4, 5, 6, 7, 8, 9 разбили на 3 группы. Докажите, что произведение чисел в одной из групп не меньше 72.
Решение: Если бы каждое из полученных произведений было меньше 72, то произведение всех чисел от 1 до 9 не превосходило бы 713= 357911. Но 1*2*3*4*5*6*7*8*9= = 362880 > 357911.
Задача 19. Сто человек сидят за круглым столом, причем более половины из них - мужчины. Докажите, что какие-то двое мужчин сидят друг напротив друга.
Решение: В противном случае женщин было бы не меньше, чем мужчин, что противоречит условию задачи.
Задача 20. На планете Тау - Кита суша занимает более половины площади планеты. Докажите, что тау-китяне могут прорыть тоннель, проходящий через центр планеты и соединяющий сушу с сушей.
Решение: Покрасим всю сушу в синий цвет, а все точки, диаметрально противоположные суше – в красный. Площади синей и красной частей планеты будут равными. Если все красные точки покрыты водой, получаем противоречие с условием задачи. Поэтому найдется точка, покрашенная в оба цвета. В ней и надо рыть туннель.