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

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

Андреев А.A., Савин А.Н., Саушкин М.Н.

Введение

При решении многих задач используется логический метод рассуждения — "от противного". В данной брошюре рассмотрена одна из его форм — принцип Дирихле. Этот принцип утверждает, что если множество из N элементов разбито на пнепересекающихся частей, не имеющих общих элементов, где N>n то, по крайней мере, в одной части будет более одного элемента. Принцип назван в честь немецкого математика Дирихле (1805-1859), который успешно применял его к доказательству арифметических утверждений.

По традиции принцип Дирихле объясняют на примере "зайцев и клеток". Если мы хотим применить принцип Дирихле при решении конкретной задачи, то нам предстоит разобраться, что в ней — "клетки", а что — "зайцы". Это обычно является самым трудным этапом в доказательстве. Цель этого статьи — познакомить школьника с некоторыми изюминками решения задач на принцип Дирихле.

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

Формулировка принципа Дирихле

Самая популярная формулировка принципа Дирихле звучит так:

ФОРМУЛИРОВКА 1. "Если в n клетках сидит n+1 или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца".

Заметим, что в роли зайцев могут выступать различные предметы и математические объекты - числа, отрезки, места в таблице и т. д.

Принцип Дирихле можно сформулировать на языке множеств и отображений.

ФОРМУЛИРОВКА 2. "При любом отображении множества P, содержащего n+1 элементов, в множество Q, содержащее n элементов, найдутся два элемента множества P, имеющие один и тот же образ".

Несмотря на совершенную очевидность этого принципа, его применение является весьма эффективным методом решения задач, дающим во многих случаях наиболее простое и изящное решение. Однако во всех этих задачах часто нелегко догадаться, что считать "зайцем", что - "клеткой", и как использовать наличие двух "зайцев", попавших в одну "клетку". С помощью принципа Дирихле обычно доказывается существование некоторого объекта, не указывая, вообще говоря, алгоритм его нахождения или построения. Это даёт так называемое неконструктивное доказательство - мы не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть.

Приводимые ниже теоремы и задачи показывают, что природа "зайцев" и "клеток" в различных задачах может сильно отличаться друг от друга.

Пример 1. Доказать, что если прямая l, расположенная в плоскости треугольника ABC, не проходит ни через одну из его вершин, то она не может пересечь все три стороны треугольника.

Решение