Принцип Дирихле. Задачи с решениями 6-7 класс с ответами и решениемМатематические задачи для учащихся 5-7 класса с ответами. Тема: Принцип Дирихле
При решении задач на «доказательство» часто бывает полезен так называемый «принцип Дирихле» (Пётр Густав Лежек Дирихле (1805-1859 гг.) — известный немецкий математик). В самой простой и несерьёзной форме он выглядит так: «Нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев».
Действительно, если в каждой клетке не больше двух зайцев, то всего зайцев не больше, чем 2 · 3 = 6, что противоречит условию. Решим задачи, выбирая каждый раз подходящих «зайцев» и строя соответствующие «клетки».
Задача 1.
В классе 30 человек. Саша Иванов сделал в диктанте 13 ошибок, остальные — меньше. Докажите, что по крайней мере 3 ученика сделали ошибок поровну (может быть по 0 ошибок).
Решение:
Здесь «зайцы» — ученики, «клетки» — число сделанных ошибок. В клетку «0» «посадим» тех учащихся, кто не сделал ни одной ошибки. В клетку «1» — тех, у кого 1 ошибка, в клетку «2» — две… и т. д. до клетки «13». Теперь применим «принцип Дирихле» (обратите внимание, это очень важное место). Докажем утверждение задачи от противного. Предположим, что никакие 3 ученика не сделали по одинаковому числу ошибок, то есть в каждую из «клеток» 0, 1, 2,…, 12 попало меньше трёх школьников. Тогда в каждой из них 2 человека или меньше, а всего в этих клетках не более 2 • 13 = 26 (учеников). Добавив Сашу Иванова, всё равно не наберём 30 ребят. Противоречие.
Ответ: действительно, по крайней мере три ученика сделали поровну ошибок.
Задача 2.
Пусть в классе 41 человек, а не 30, а все остальные условия — как в предыдущей задаче. Докажите, что найдутся четверо ребят, сделавших одинаковое число ошибок.
Решение:
В клетку «0» «посадим» всех учащихся, кто не сделал ни одной ошибки. В клетку «1»-тех, у кого 1 ошибка, в клетку «2»-две… и т. д. до клетки «13», где у Саши 13 ошибок. Предположим, что никакие 4 ученика не сделали по одинаковому числу ошибок, то есть в каждую из «клеток» 0, 1,2, …, 12 попало меньше четырёх школьников. Тогда в каждой из них — 3 человека или меньше, а всего в этих клетках не более 3 • 13 = 39 (человек). Добавив Сашу Иванова, всё равно не наберём 41 ребенка. Противоречие.
Ответ: действительно, по крайней мере четверо учеников сделали поровну ошибок.
Итак, в простейшем виде «принцип Дирихле» выражают так: «Если десять кроликов сидят в девяти ящиках, то в некотором ящике сидят не меньше двух кроликов».
Общая формулировка: «Если n кроликов сидят в k ящиках, то найдётся ящик, в котором сидят не меньше чем n/k кроликов, и найдется ящик, в котором сидят не больше чем n/k кроликов».
Пусть вас не смущает дробное число кроликов — если получится, что в ящике не меньше 7/3 кроликов, значит, их не меньше трёх.
Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются.
Допустим, что в каждом ящике сидят меньше, чем n/k кроликов. Тогда во всех ящиках меньше, чем (n/k) · k = n. Противоречие.
Формулировка принципа Дирихле кажется очевидной, однако трудность состоит в том, что в задачах не указаны ни кролики, ни ящики.
Зная принцип Дирихле, можно догадаться, в каких случаях его применять. Например, если каждому элементу множества А соответствует ровно один элемент множества В, то элементы множества А можно назвать «кроликами», а элементы множества В- «ящиками».
Принцип Дирихле бывает непрерывным: «Если n кроликов съели m кг травы, то какой-то кролик съел не меньше m/n кг и какой-то съел не больше m/n кг» (а если кто-то съел больше среднего, то кто-то съел меньше среднего). Заметим, что в последней формулировке кролики играют роль ящиков для травы, а трава — роль кроликов, сидящих в клетках.
Задача 3.
В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день.
Решение:
Всего в году бывает 366 дней. Назовём дни ящиками, а учеников — кроликами. Тогда в некотором ящике сидят не меньше 400/366 кроликов, то есть больше одного, и, следовательно, не меньше двух. Можно рассуждать от противного. Допустим, что каждый день отмечают дни рождения не более одного ученика, тогда учеников было бы не более 366. Противоречие.
Ответ: хотя бы два ученика могли родиться в один день.
Задача 4.
Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6 х 6 из чисел + 1, -1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различными. Помогите Буратино!
Решение:
Допустим, что квадрат составлен. Тогда суммы чисел могут меняться в пределах от — 6 до + 6. Всего 13 значений. Строк в квадрате — 6, столбцов — 6, диагоналей — 2. Получаем 14 различных сумм. Противоречие.
Ответ: составить такой квадрат невозможно.
Задача 5.
На планете Земля океан занимает больше половины площади поверхности. Докажите, что в Мировом океане можно указать две диаметрально противоположные точки.
Решение:
Отразим океан симметрично относительно центра Земли. Поскольку сумма площадей океана и его образа превышает площадь земной поверхности, то существует точка, принадлежащая океану и его образу. Возьмём эту точку вместе с противоположной к ней.
Ответ: да, существуют 2 диаметрально противоположные точки.
Задача 6.
На собеседование пришли 65 школьников. Им предложили 3 контрольных работы. За каждую контрольную работу ставилась одна из оценок: «2», «3» «4» или «5». Верно ли, что найдутся 2 школьника, получившие одинаковые оценки на всех контрольных?
Решение:
Рассмотрим множество наборов из трёх оценок за соответствующие контрольные работы. Количество таких наборов равно 43, или 64 (4 возможности за каждую из трёх контрольных работ). Поскольку число учащихся больше 64 то по принципу Дирихле каким-то двум ученикам отвечает один набор оценок.
Ответ: верно.
Задача 7.
Докажите, что в любой компании из 5 человек двое имеют одинаковое число знакомых.
Решение:
Имеется 5 вариантов числа знакомых: от 0 до 4 (5 человек, сам с собою человек не может быть знакомым). Заметим, что если у кого-то четверо знакомых, то ни у кого не может быть 0 знакомых («клетки», соответствующие 0 и 4, взаимно исключают друг друга). Поэтому можно говорить о четырёх «клетках» — вариантах числа знакомых. Человек 5, а «клеток» — 4, значит, обязательно найдутся хотя бы 2 человека, имеющие одинаковое число знакомых.
Ответ: утверждение верное.
Задача 8.
10 школьников на олимпиаде решили 35 задач, причём известно, что среди них есть решившие 1 задачу, решившие 2 задачи и решившие 3 задачи. Доказать, что среди них есть школьник, решивший не менее 5 задач.
Решение:
3 ученика решили 1 + 2 + 3 = 6 (задач). Осталось 10 — 3 = 7 (учеников), а задач осталось: 35 — 6 = 29;
29 = 7 • 4 + 1, то есть найдётся школьник, решивший не менее 5 задач.
Ответ: утверждение верное.
Задача 9.
Доказать, что среди 11 чисел всегда можно найти два таких числа, разность которых кратна 10.
Решение:
Среди любых 11 чисел всегда найдётся по крайней мере 2 таких числа, которые оканчиваются одной и той же цифрой (так как цифр всего 10), а значит, разность этих двух чисел оканчивается нулём, то есть кратна 10.
Ответ: утверждение верное.
Задача 10.
В классе 41 ученик написал по три контрольных работы. В результате учитель не поставил ни одной неудовлетворительной отметки. Каждый ученик получил все остальные отметки. Узнав об этом, один ученик заметил, что по крайней мере 7 человек получили одинаковые отметки по всем трём контрольным, а другой, подумав, сказал, что таких учеников с одинаковыми отметками, наверное, будет 8. Кто из них прав?
Решение:
Разобьём класс на группы в соответствии со всевозможными наборами отметок: «3», «4», «5»; «3», «5», «4»; «4», «3», «5»;
«4», «5», «3»; «5», «3», «4»; «5», «4», «3» — всего 6 наборов различных отметок.
Ответ: прав первый ученик.