group-telegram.com/math_essence/793
Last Update:
В основе очень многих математических утверждений лежит идея, называемая принципом Дирихле. Его формулировка кажется очевидной: «Если z зайцев сидят в k клетках, то найдётся клетка, в которой находится не менее ᶻ /ₖ зайцев».
Доказательство принципа Дирихле строится от противного. Допустим, что в каждой клетке число зайцев меньше, чем ᶻ /ₖ . Тогда в k клетках зайцев меньше, чем
k · ᶻ /ₖ = z. Противоречие!
Рассмотрим применение принципа Дирихле на примерах.
Задача 1. Грани куба окрашены в 2 цвета. Докажите, что найдутся две соседние одноцветные грани.
Решение. Рассмотрим три грани куба, имеющие общую вершину. Назовём их «зайцами», а данные цвета — «клетками». По принципу Дирихле найдутся две грани, окрашенные в один цвет. Они и будут соседними.
Задача 2. Имеется 37 конфет 4 сортов. Верно ли, что не менее 10 из них будут какого-то одного сорта?
Решение. Назовём «клетками» сорта конфет, а «зайцами» — сами конфеты. По принципу Дирихле найдется «клетка», в которой не менее 37/4 «зайцев». Так как 9 < 37/4 < 10, то найдется 10 конфет одного сорта.
Задача 3. В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка — точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.
Решение. Весь ковер можно накрыть такими 25-ю заплатами. По принципу Дирихле какая-то из этих заплат накроет не менее трёх дырок.
Задача 4. Докажите, что в любой компании найдутся два человека, имеющие одинаковое число друзей (из этой компании).
Решение. Пусть в компании n человек. Тогда количество друзей для одного человека из компании может принимать n различных значений: 0, 1, 2, ..., n – 1. Казалось бы, принцип Дирихле не работает: у нас имеется n человек и n различных возможностей на количество друзей. Однако, если есть человек, имеющий n – 1 друга, то он дружит со всеми, следовательно, нет человека, который имеет 0 друзей. Противоречие.
BY Математическая эссенция
Share with your friend now:
group-telegram.com/math_essence/793