104
3. Принцип Дирихле
При решении различных мате математических задач применяется
специальный метод, получивший название «принцип Дирихле».
Существует несколько формулировок этого принципа. Самая популярная
следующая: «Если в n
клетках сидит m зайцев, причем n меньше m, то
хотя бы в одной клетке сидит по крайней мере два зайца». Доказывается
этот принцип Дирихле легко, методом доказательства от противного.
Поэтому некоторые из задач, решаемые с помощью принципа Дирихле,
также можно решить, используя метод доказательства от противного, но
не все.
При решении задач выбор зайцев и клеток часто неочевиден. Далеко не
всегда по формулировке задачи можно определить, что следует применить
принцип Дирихле.
Главное достоинство данного метода решения состоит в том, что он дает
неконструктивное решение.
Рассмотрим примеры различных задач, решаемых с помощью принципа
Дирихле.
1.
В классе 15 учеников. Докажите, что найдутся как минимум 2
ученика, отмечать дни рождения в одном месяце. ( Решение. Пусть 15
учеников будут «зайцы». Тогда «клетками» будут месяцы года, их 12. Т.к.
15 больше 12, то по принципу Дирихле найдется, как минимум, одна
клетка, в которой будут сидеть по крайней мере 2 «зайца». Т.е. найдется
месяц, в котором будут отмечать дни рождения не менее 2 учеников
класса. Это и требовалось доказать. Также задача легко решается с
использованием метода доказательства от противного.
2.
В классе 35 учеников. Можно ли утверждать, что среди них найдутся
хотя бы 2 ученика, фамилии которых начинаются с одной буквы? (
Решение. Пусть 35 учеников будут «зайцы», а буквы – это «клетки». В
русском алфавите 33 буквы.
Фамилии не могут начинаться на ь и ъ знаки. Т.к. 35 больше 31, то
найдутся 2 ученика, у которых фамилии начинаются с одной буквы.
3.
Дано 12 целых чисел. Докажите, что из них можно выбрать 2,
разность которых делится на 11. ( Решение. Примем числа за «зайцев». Т.к.
их 12, то «клеток» должно быть меньше. Пусть «клетки» - это остатки от
деления целого числа на 11.Всего «клеток» будет 11: 0,1,2,3,4,5,6,7,8,9,10.
Тогда по принципу Дирихле, найдется «клетка», в которой будут сидеть не
менее чем 2 «зайца», т.е. найдутся 2 целых числа с одним остатком. А
разность двух чисел с одинаковым остатком от деления на 11 будет
делиться на 11. Действительно, пусть a=11m+q, b=11n+q, тогда a-b=
11m+q-(11n+q)=11(m-n). ( делится на 11).
4.
Дано 9 целых чисел. Докажите, что из них можно выбрать 2, разность
которых делится на 8. (Решается задача подобно задаче № 3. Только
здесь будет 8 остатков:0,1,2,3,4,5,6,7 – «клетки», а числа – их 9 – «зайцы».
5.
В лесу растет миллион елок. Известно, что на каждой из них не более
600 000 иголок. Докажите, что в лесу найдутся две елки с одинаковым
количеством иголок.
( Решение. Пусть елки – «зайцы», а число иголок на елках: 0,1,2,3,…,
600 000-
«клетки». «Клеток» будет 600 001, а «зайцев» - 1000 000. Здесь «зайцев»
гораздо больше, чем «клеток». Тогда в какой – то «клетке» будет
находиться не менее 2 «зайцев». Но, если в одной клетке сидят два
106
Решение. Рассмотрим тройки кусков, обозначенные на рис. Одинаковыми
цифрами. Суммарный вес кусков хотя бы одной тройки не меньше 300 г., в
противном случае вес торта меньше 300х3=900 г
11. Натуральные числа 22, 23, 24 обладают тем свойством,
что в разложении каждого из них на простые множители
каждый множитель входит в нечетной степени:
22=2
1
∙11
1
,
23=23
1 ,
24=2
3
∙3
1.
Какое наибольшее количество последовательных натуральных чисел может обладать таким
свойством?
Решение. Пример. 29, 30, 31, 32, 33, 34, 35. Покажем, что восьми подряд идущих чисел с
указанным свойством быть не может. Действительно, одно из этих чисел делится на 8. Среди
восьми наших чисел обязательно будет либо число (n-4), либо число (n+4). Оно делится на 4,
но не делится на8, что противоречит условию, т.к. делитель 2 входит в это число в четной
степени.
12. Внутри правильного треугольника со стороной 5 расположены 76 точек . Докажите, что
можно так выбрать круг радиуса1/
3
, что внутри него окажется не менее 4 из этих точек.
Решение. Разобьем треугольник на 25 правильных треугольников со стороной 1 так, как показано
на рис. Тогда, хотя бы в одном из треугольников окажется не менее четырех данных точек, т.к.
3х25< 76. Но такой треугольник можно вписать в круг радиуса 1/
3
Do'stlaringiz bilan baham: