Принцип Дирихле
    Андреев А.A., Савин А.Н., Саушкин М.Н. Введение
    При решении многих задач используется логический метод рассуждения - "от противного". В данной брошюре рассмотрена одна из его форм - принцип Дирихле. Этот принцип утверждает, что если множество из N элементов разбито на пнепересекающихся частей, не имеющих общих элементов, где N>n то, по крайней мере, в одной части будет более одного элемента. Принцип назван в честь немецкого математика Дирихле (1805-1859), который успешно применял его к доказательству арифметических утверждений.
    По традиции принцип Дирихле объясняют на примере "зайцев и клеток". Если мы хотим применить принцип Дирихле при решении конкретной задачи, то нам предстоит разобраться, что в ней - "клетки", а что - "зайцы". Это обычно является самым трудным этапом в доказательстве. Цель этого статьи - познакомить школьника с некоторыми изюминками решения задач на принцип Дирихле.
    Статья предназначена главным образом для старшеклассников, однако школьники младших классов также несомненно найдут в ней много полезного. Формулировка принципа Дирихле
    Самая популярная формулировка принципа Дирихле звучит так:
    ФОРМУЛИРОВКА 1. "Если в n клетках сидит n+1 или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца".
    Заметим, что в роли зайцев могут выступать различные предметы и математические объекты - числа, отрезки, места в таблице и т. д.
    Принцип Дирихле можно сформулировать на языке множеств и отображений.
    ФОРМУЛИРОВКА 2. "При любом отображении множества P, содержащего n+1 элементов, в множество Q, содержащее n элементов, найдутся два элемента множества P, имеющие один и тот же образ".
    Несмотря на совершенную очевидность этого принципа, его применение является весьма эффективным методом решения задач, дающим во многих случаях наиболее простое и изящное решение. Однако во всех этих задачах часто нелегко догадаться, что считать "зайцем", что - "клеткой", и как использовать наличие двух "зайцев", попавших в одну "клетку". С помощью принципа Дирихле обычно доказывается существование некоторого объекта, не указывая, вообще говоря, алгоритм его нахождения или построения. Это даёт так называемое неконструктивное доказательство - мы не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть.
    Приводимые ниже теоремы и задачи показывают, что природа "зайцев" и "клеток" в различных задачах может сильно отличаться друг от друга.
    Пример 1. Доказать, что если прямая l, расположенная в плоскости треугольника ABC, не проходит ни через одну из его вершин, то она не может пересечь все три стороны треугольника.
    Решение
     Полуплоскости, на которые прямая l разбивает плоскость треугольника ABC, обозначим через q1 и q2; эти полуплоскости будем считать открытыми (то есть не содержащими точек прямой l). Вершины рассматриваемого треугольника (точки A, B, C) будут "зайцами", а полуплоскости q1 и q2 - "клетками". Каждый "заяц" попадает в какую-нибудь "клетку" (ведь прямая l не проходит ни через одну из точек A, B, C). Так как "зайцев" три, а "клеток" только две, то найдутся два "зайца", попавшиев одну "клетку"; иначе говоря, найдутся такие две вершины треугольника ABC, которые принадлежат одной полуплоскости. ............