Математическая эссенция

0:09

This media is not supported in your browser

VIEW IN TELEGRAM

В основе очень многих математических утверждений лежит идея, называемая принципом Дирихле. Его формулировка кажется очевидной: «Если 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 друзей. Противоречие.

www.group-telegram.com/ua/math_essence.com/793

2.4K viewsFeb 12 at 19:24

В основе очень многих математических утверждений лежит идея, называемая принципом Дирихле. Его формулировка кажется очевидной: «Если 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 Математическая эссенция