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

Автор: Шиянова Любовь Борисовна

Организация: ГБОУ СОШ № 58

Населенный пункт: г. Севастополь

На внеурочных занятиях по математике мы с ребятами рассматриваем различные способы и методы решения нестандартных задач. При решении задач на доказательство часто используется метод рассуждения «от противного», одна из его форм – принцип Дирихле. (Пётр Густав Лежек Дирихле (1805-1859 гг.) - известный немецкий математик).

Принцип Дирихле не рассматривается в учебниках математики, между тем, это достаточно простое утверждение способно помочь в решении многих математических задач.

Самая простейшая формулировка этого принципа: «Если в n клетках сидит m кроликов, и m > n, то в какой-то из клеток сидит не менее двух кроликов». Доказательство этого принципа чрезвычайно просто. Действительно, пусть это утверждение неверно, тогда в каждой клетке сидит не более одного кролика, и, следовательно, в n клетках — не более n кроликов, а их должно быть m > n . Получили противоречие.

Более общая формулировка принципа Дирихле, такова: если (kn + 1) кроликов поместить в n клеток, то в одной из клеток находятся не менее (k + 1) кроликов; или в эквивалентной форме – нельзя посадить (kn + 1) кроликов в n клеток так, чтобы в каждой клетке находилось не более k кроликов.

Принцип Дирихле помогает легко решить задачи из теории чисел, комбинаторики, геометрии.

Главное правильно распределить, что выступает в роли кроликов, и что в роли клеток, при этом следить за тем, чтобы кроликов всегда было больше, чем клеток; а затем научиться пользоваться фактом наличия в одной клетке двух кроликов и делать необходимые выводы.

Примеры задач

Задача 1. В мешке лежат шарики двух цветов: чёрного и белого. Какое наименьшее число шариков нужно достать из мешка не глядя, чтобы среди них оказались ровно два шарика одного цвета?

Решение: «Кроликами» в этой задаче являются шарики, а «клетками» — цвета. Достаём из мешка 3 шарика. Понятно, что из них 2 шарика будут одного цвета. (Ответ:3)

Задача 2. Доказать, что среди шести любых целых чисел найдутся два, разность которых делится на 5.

Решение:

При делении на 5 возможных 5 разных остатков: 0; 1; 2; 3; 4. Так как чисел 6, то найдутся 2 числа с одинаковыми остатками; их разность разделится на 5. Здесь числа – это «кролики», остатки – это «клетки».

Задача 3. Верно ли, что среди любых семи натуральных чисел найдутся три, сумма которых делится на 3?

Решение:

При делении на 3 есть три остатка: 0, 1, 2. Так как 7 = 3 ∙ 2 + 1, то найдутся три числа, дающие один остаток. Ответ: верно.

Задача 4. В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.

Решение:

Здесь «кроликами» являются ящики, а «клетками» — сорта яблок. Рассадим 25 кроликов по трём клеткам. Поскольку 25= 3⋅ 8 +1 , то, применив обобщённый принцип Дирихле для n = 3, k = 8, получим, что имеется не менее чем 8+1 = 9 ящиков с яблоками одного и того же сорта.

Задача 5. Каждую точку плоскости раскрашивают в один из двух цветов. Докажите, что существует отрезок длиной 1см, концы которого имеют одинаковый цвет.

Решение:

Построим равносторонний треугольник со стороной 1см. Поскольку треугольник имеет три вершины, а цветов только два, то хотя бы две вершины будут одного цвета. Эти вершины и есть концы искомого отрезка.

Задача 6. На планете Земля океан занимает больше половины площади поверхности. Докажите, что в Мировом океане можно указать две диаметрально противоположные точки.

Решение:

Отразим океан симметрично относительно центра Земли. Поскольку сумма площадей океана и его образа превышает площадь земной поверхности, то существует точка, принадлежащая океану и его образу. Возьмём эту точку вместе с противоположной к ней.

Ответ: да, существуют 2 диаметрально противоположные точки.

Задача 7. Внутри равностороннего треугольника со стороной 4 см бросили 5 горошин. Доказать, что найдутся две горошины, расстояние между которыми меньше 2см.

Решение.

Разделим треугольник на 4 равносторонних треугольника со стороной 2см.

Поскольку бросают 5 горошин, то в один из полученных треугольников попадет хотя бы 2 горошины, расстояние между которыми будет меньше стороны треугольника, то есть меньше 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. Кот Базилио пообещал Буратино открыть великую тайну, если он составит чудесный квадрат 6 х 6 из чисел + 1, -1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различными. Помогите Буратино!

Решение:

Допустим, что квадрат составлен. Тогда суммы чисел могут меняться в пределах от - 6 до + 6. Всего 13 значений. Строк в квадрате - 6, столбцов - 6, диагоналей - 2. Получаем 14 различных сумм (суммы – это «кролики», а значения – «клетки»). Значит найдется не менее двух сумм, имеющих одинаковые значения.

Ответ: составить такой квадрат невозможно.

Задача 10 .Вокруг круглого стола стоят на равном расстоянии друг от друга k флажков разных стран, а за столом сидят k представителей от каждой страны, причём каждый из них расположился рядом с чужим флажком. Докажите, что можно так повернуть стол, что хотя бы двое из представителей окажутся возле своих флажков.

Решение.

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

Итак, с помощью принципа Дирихле легко решаются, кажущиеся на первый взгляд сложными, задачи. Знание этого пригодится для успешного решения олимпиадных задач, сдачи экзаменов и решении практических задач в жизни.

1. file0.docx (23,4 КБ)