Материал по математике "Математические задачи. Принцип Дирихле"

Принцип Дирихле.

1. В ковре размером 4×4 метра моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1×1 метр, не содержащий внутри себя дырок (Дырки можно считать точечными).

Решение. Разрежем ковер на 16 ковриков размерами 1×1 метр. Так как ковриков – «клеток» - 16, а дырок – «зайцев» - 15, то найдется хотя бы одна «клетка», в которой не будет «зайцев», т. е. найдется коврик без дырок внутри.

2. В классе 27 учеников. Найдется ли месяц, в котором отмечают свои дни рождения не меньше, чем три ученика этого класса?

Решение. В году 12 месяцев. Обозначим их как «клетки», а учеников как «зайцев». Так как 27˃12×2+1, то по обобщенному принципу Дирихле найдется «клетка», в которой сидят не менее 3 «зайцев» т. е. найдется месяц, в котором дни рождения празднуют не менее 3 учеников.

3. За круглым столом сидят 16 учеников, причем больше половины из них девушки. Докажите, что какие – то 2 девушки сидят напротив друг друга.

Решение. Образуем 8 пар, в каждую пару включим учеников, сидящих друг против друга. Примем за «клетки» - пары, а за зайцев – «девушек». Так как девушек больше половины, то есть восьми, то найдется «клетка» (пара), в которой будут находиться 2 девушки.

4. Докажите, что никакая прямая не может пересекать все три стороны треугольника.

Решение: Прямая делит плоскость на две полуплоскости, которые мы назовем "клетками". Три вершины треугольника назовем "кроликами". По принципу Дирихле "найдется клетка, в которой сидит по крайней мере два кролика", то есть найдутся две вершины, лежащие в одной полуплоскости относительно данной прямой. Сторона, соединяющая эти вершины, не пересекает данную прямую.

5. Грани куба окрашены в 2 цвета. Докажите, что найдутся две соседние одноцветные грани.

Решение: Рассмотрим три грани куба, имеющие общую вершину. Назовем их "кроликами", а данные цвета — "клетками". По принципу Дирихле, найдутся две грани, окрашенные в один цвет. Они и будут соседними.

6. Имеется 25 конфет 3 сортов. Верно ли, что не менее 9 из них будут какого-то одного сорта?

Решение: Пусть "клетками" у нас будут сорта конфет, а "кроликами" -сами конфеты. По принципу Дирихле найдется "клетка", в которой не менее 25 / 3 "кроликов". Так как 8 < 25 / 3 < 9, то найдется 9 конфет одного сорта.

Утверждение можно доказать, проводя сразу рассуждения от противного. Пусть конфет каждого сорта не более 9, то есть не превышает восьми. Тогда всего конфет не превышает 3 × 8 = 24, а по условию их 25. Противоречие.

7. В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Доказать, что какие-то три ученика сделали одинаковое количество ошибок.

Решение: По условию задачи наибольшее число ошибок, сделанных в работе 13. Значит, ученики могли сделать 0, 1, 2, ..., 13 ошибок. Эти варианты будут "клетками", а ученики станут "кроликами". Тогда по (обобщенному) принципу Дирихле (14 клеток и 30 зайцев) найдутся три ученика, попавших в одну "клетку", то есть сделавших одинаковое число ошибок.

8. В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка - точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.

Решение: Весь ковер можно накрыть такими 25-ю заплатами. По принципу Дирихле какая-то из этих заплат накроет не менее трех дырок.

9. В магазине привезли 26 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?

Решение 26 ящиков – «кроликов» рассадим по трем «клетка» - сортам. Так как 26 = 3×8+2, то применим обобщенный принцип для m = 3, k = 8 и получим, что в какой-то «клетке» - сорте не менее 3 ящиков.

10. На шахматной доске размером 8×8 Вася расставил 14 фигур. Докажите, что найдется квадрат размером 2×2, в котором не будет фигур. (Фигуры размещаются внутри клеток размером 1×1. )

Решение. Разобьем квадрат 8×8 следующим образом на клетки...

Тогда получаем 16 «клеток» и 14 «зайцев» - фигур. Так как 16 ˃14, то найдется как минимум одна клетка. Которая будет пустой.

Весь материал - в документе.

Принцип Дирихле.

1. В ковре размером 4×4 метра моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1×1 метр, не содержащий внутри себя дырок (Дырки можно считать точечными).

Решение.Разрежем ковер на 16 ковриков размерами 1×1 метр. Так как ковриков – «клеток» - 16, а дырок – «зайцев» - 15, то найдется хотя бы одна «клетка», в которой не будет «зайцев», т.е. найдется коврик без дырок внутри.

1. В классе 27 учеников. Найдется ли месяц, в котором отмечают свои дни рождения не меньше, чем три ученика этого класса?

Решение. В году 12 месяцев. Обозначим их как «клетки», а учеников как «зайцев». Так как 27˃12×2+1, то по обобщенному принципу Дирихле найдется «клетка», в которой сидят не менее 3 «зайцев» т.е. найдется месяц, в котором дни рождения празднуют не менее 3 учеников.

1. За круглым столом сидят 16 учеников, причем больше половины из них девушки. Докажите, что какие – то 2 девушки сидят напротив друг друга.

Решение. Образуем 8 пар, в каждую пару включим учеников, сидящих друг против друга. Примем за «клетки» - пары, а за зайцев – «девушек». Так как девушек больше половины, то есть восьми, то найдется «клетка» (пара), в которой будут находиться 2 девушки.

1. Докажите, что никакая прямая не может пересекать все три стороны треугольника.

Решение: Прямая делит плоскость на две полуплоскости, которые мы назовем "клетками". Три вершины треугольника назовем "кроликами". По принципу Дирихле "найдется клетка, в которой сидит по крайней мере два кролика", то есть найдутся две вершины, лежащие в одной полуплоскости относительно данной прямой. Сторона, соединяющая эти вершины, не пересекает данную прямую.

1. Грани куба окрашены в 2 цвета. Докажите, что найдутся две соседние одноцветные грани.

Решение: Рассмотрим три грани куба, имеющие общую вершину. Назовем их "кроликами", а данные цвета — "клетками". По принципу Дирихле, найдутся две грани, окрашенные в один цвет. Они и будут соседними.

1. Имеется 25 конфет 3 сортов. Верно ли, что не менее 9 из них будут какого-то одного сорта?

Решение: Пусть "клетками" у нас будут сорта конфет, а "кроликами" -сами конфеты. По принципу Дирихле найдется "клетка", в которой не менее 25 / 3 "кроликов". Так как 8 

Утверждение можно доказать, проводя сразу рассуждения от противного. Пусть конфет каждого сорта не более 9, то есть не превышает восьми. Тогда всего конфет не превышает 3   8 = 24, а по условию их 25. Противоречие.

1. В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Доказать, что какие-то три ученика сделали одинаковое количество ошибок.

Решение: По условию задачи наибольшее число ошибок, сделанных в работе 13. Значит, ученики могли сделать 0, 1, 2, ..., 13 ошибок. Эти варианты будут "клетками", а ученики станут "кроликами". Тогда по (обобщенному) принципу Дирихле (14 клеток и 30 зайцев) найдутся три ученика, попавших в одну "клетку", то есть сделавших одинаковое число ошибок.

1. В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка - точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.

Решение: Весь ковер можно накрыть такими 25-ю заплатами. По принципу Дирихле какая-то из этих заплат накроет не менее трех дырок.

1. В магазине привезли 26 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?

Решение 26 ящиков – «кроликов» рассадим по трем «клетка» - сортам. Так как 26 = 3×8+2, то применим обобщенный принцип для m = 3, k = 8 и получим, что в какой-то «клетке» - сорте не менее 3 ящиков.

1. На шахматной доске размером 8×8 Вася расставил 14 фигур. Докажите, что найдется квадрат размером 2×2, в котором не будет фигур. (Фигуры размещаются внутри клеток размером 1×1.)

Решение. Разобьем квадрат 8×8 следующим образом на клетки:

Тогда получаем 16 «клеток» и 14 «зайцев» - фигур. Так как 16 ˃14, то найдется как минимум одна клетка. Которая будет пустой.