Реферат: Принцип Дирихле

Доказательство Каждое из p - 1 чисел a, 2a, . . ., (p-1)a ("зайцев") даёт при делении на p ненулевой остаток (ведь a не делится на p):

Если число различных встречающихся здесь остатков ("клеток") меньше p - 1, то среди них найдутся по крайней мере два одинаковых ("в клетке по крайней мере два зайца"). Но это невозможно, так как при rn = rm число (n-m)a = (kn-km)p делится на p, что противоречиво, ибо |n-m| < p и a взаимно просто с p. Значит, все остатки r1, . . . , rp - 1 между собой различны и образуют перестановку чисел 1, 2, . . . , p - 1. Перемножая все предыдущие равенства, получаем

где N - некоторое целое число. Следовательно, (p-1)!·(ap-1-1) делится на p, а тогда и ap - 1 - 1 делится на p. Теорема доказана.

Следствие. Если p - простое число, то при любом целом a разность ap - a делится на p.

Помимо малой теоремы Ферма применение принципа Дирихле к остаткам при делении встречается во многих других задачах элементарной теории чисел. Возможна следующая переформулировка принципа Дирихле:

"Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток".

При делении с остатком на p может встретиться конечное число различных остатков: 0, 1, 2, . . . , p-1. Они то и играют здесь роль "клеток", а сами целые числа являются "зайцами". Так как чисел ("зайцев") больше, чем остатков ("клеток"), то хотя бы два числа "сидят в одной клетке", т.е. имеют одинаковые остатки при делении на p. Рассмотрим классические примеры.

Пример 10. Дано 11 различных целых чисел. Доказать, что из них можно выбрать два числа, разность которых делится на 10.

Решение По крайней мере два числа из 11 дают одинаковый остаток при делении на 10 (принцип Дирихле). Пусть это будут A = 10a + r и B = 10b + r. Тогда их разность делится на 10: A - B = 10(a - b).

Пример 11. Доказать, что если имеется 100 целых чисел x1, x2, . . . , x100, то из них можно выбрать несколько чисел (может быть, одно), сумма которых делится на 100.

Решение Рассмотрим 100 следующих сумм:

Если хотя бы одна из этих сумм делится на 100, то наша цель достигнута. Допустим, что ни одно из чисел S1, S2, . . . , S100 не делится на 100. Значит, два из них при делении на 100 дают равные остатки (т. к. сумм у нас 100, а различных остатков может быть лишь 99). Пусть это Sn и Sm (n < m). Тогда разность

делится на 100, и поэтому сумма xn + 1+. . .+ xm является искомой.

Пример 12. Первоклассник Петя знает только цифру 1. Доказать, что он может написать число, делящееся на 1997.

Решение

Рассмотрим последовательность a1 = 1, a2 = 11, . . . , an = = 11. . .1, . . . чисел, десятичная запись которых состоит из одних единиц. Поскольку существует лишь конечное число остатков от деления на 1997, а последовательность содержит бесконечно много членов, то, согласно принципу Дирихле, среди них найдутся два, дающих одинаковые остатки: ak и al (k > l). Их разность ak - al = 10l·ak - l делится на 1997. Так как 10l и 1997 - взаимно просты, то ak - l делится на 1997. Это число Петя сможет записать.

КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ. Если числа a1, a2, . . . , an попарно взаимно просты, то для любых остатков r1, r2, . . ., rn таких, что 0 Ј ri < ai при всех i = 1, 2, . . ., n, найдётся число N, которое при делении на ai даёт остаток ri при всех i = 1, 2, . . ., n.

Доказательство Применим индукцию по n. При n = 1 утверждение теоремы очевидно. Пусть теорема справедлива при n = k - 1, т.е. существует число M, дающее остаток ri при делении на ai при i = 1, 2, . . ., k - 1. Обозначим d = a1a2. . . ak - 1 и рассмотрим числа M, M + d, M + 2d, . . . , M + (ak - 1)d. Покажем, что хотя бы одно из этих чисел даёт остаток rk при делении на ak. Допустим это не так. Поскольку количество чисел равно ak, а возможных остатков при делении этих чисел на ak может быть не более чем ak - 1 (ведь ни одно число не даёт остаток rk), то среди них найдутся два числа, имеющих равные остатки (принцип Дирихле). Пусть это числа M + sd и M + td (0 Ј s Ј ak - 1 и 0 Ј t Ј ak - 1). Тогда их разность (M + sd) - (M + td) = (s - t)d делится на ak, что невозможно, т.к. 0 < |s - t| < ak и d = a1a2...ak - 1 взаимно просто с ak, ибо числа a1, a2, . . ., ak попарно взаимно просты (по условию). Противоречие.

Таким образом, среди рассматриваемых чисел найдётся число N, которое при делении на ak даёт остаток rk. В то же время при делении на a1, a2, . . ., ak-1 число N даёт остатки r1, r2, . . ., rk-1 соответственно. Теорема доказана.

Принцип Дирихле для длин и площадей

Применительно к бесконечным множествам, имеющим меру, можно сформулировать утверждение, похожее на принцип Дирихле и столь же очевидное:

"Если внутри множества меры V расположено несколько множеств, сумма мер которых больше V, то найдётся общий элемент, принадлежащий по крайней мере двум из этих множеств".

Для отрезков и фигур это положение переписывается так:

"Если на отрезке длины L расположено несколько отрезков с суммой длин больше L, то хотя бы два из них имеют общую точку";

"Если внутри фигуры площади S находится несколько фигур, имеющих сумму площадей больше S, то хотя бы две из них имеют общую точку".

В ряде задач используется обобщение принципа, а также утверждение, в некотором смысле ему обратное:

"Если на отрезке длины L расположено несколько отрезков, сумма длин которых больше L·k, то по крайней мере одна точка покрыта не менее чем k+1 из этих отрезков";

"Если сумма площадей нескольких фигур меньше S, то ими нельзя покрыть фигуру площади S".

В качестве упражнения докажите все эти утверждения методом от противного и попробуйте сформулировать аналогичные им (например, для тел и объёмов).

Пример 13. В квадрате площадью S расположено 100 фигур, сумма площадей которых больше 99S. Доказать, что у всех этих фигур есть общая точка.

Решение Пусть S1, S2, . . . , S100 - площади данных фигур, а Sў1, Sў2,, . . . , Sў100 - площади фигур, дополняющих их до квадрата. Понятно, что Sk + Sўk = S. По условию S1+S2+. . .+S100 > 99S, поэтому

Sў1+ Sў2+. . .+ Sў100 = (S- S1)+ (S- S2)+. . .+ (S- S100) = 100S-(S1+ S2+. . .+ S100) < 100S-99S = S.

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

Пример 14. В круг радиуса 3 произвольным образом помещены несколько кругов, сумма радиусов которых равна 25. Доказать, что найдётся прямая, которая пересекает не менее девяти из этих кругов.

Решение Спроектируем все круги на произвольный диаметр AB большого круга (AB = 6). Сумма длин проекций, очевидно, равна сумме диаметров кругов, т.е. 50. Поскольку 50 > 8AB, то на отрезке AB есть точка, принадлежащая проекциям по крайней мере девяти кругов. Прямая, проходящая через эту точку и перпендикулярная диаметру AB, - искомая.

Пример 15. Дана фигура площади больше N. Доказать, что в ней найдутся N+1 точек, разности соответствующих координат которых - целые числа.

Решение Разобьём исходную фигуру параллельными прямыми, расположенными на расстоянии 1, на клетки. (В качестве таких прямых можно взять, например, линии целочисленной сетки.) Некоторые клетки будут покрываться фигурой полностью, другие - лишь частично. Выделим какую-нибудь одну клетку и с помощью параллельных переносов перенесём на эту клетку все кусочки фигуры, которые получились в результате её пересечения со всеми клетками. {Наглядно это можно описать так. Представьте, что фигура нарисована на клетчатой бумаге. Разрежьте бумагу по клеткам и сложите их в стопку, перенося их параллельно и не переворачивая, а затем спроектируйте стопку на выделенную клетку.}

Площади проекций частей фигуры в сумме дадут площадь самой фигуры, т.е. больше N. Поэтому на выделенной клетке (площади 1) согласно принципу Дирихле найдётся точка X, покрытая не менее N+1 кусочками фигуры. Вернёмся теперь к исходной фигуре и отметим на ней N+1 точек, проектирующихся в точку X при переносе клеток. Эти точки будут искомыми, т.к. после переноса кусочка фигуры в выделенную клетку координаты каждой точки этого кусочка изменяются на целое число.

Пример 16. В кубе с ребром a лежит ломаная, которую каждая плоскость, параллельная одной из граней, пересекает не более k раз. Доказать, что длина ломаной меньше 3ka.

Решение Введём в пространстве прямоугольную систему координат, оси которой направим вдоль рёбер куба. Пусть ломаная состоит из нескольких отрезков, длины которых мы обозначим через Lk.

Пусть xk, yk, zk - проекции отрезка Lk на оси координат. Тогда Lk = [Ц(x2k+y2k+z2k)]. Задачу будем решать методом от противного. Допустим, что длина ломаной не меньше 3ka. Тогда попробуем найти плоскость, параллельную одной из граней, которая пересечёт ломаную не менее чем в k+1 точках. Спроектируем ломаную на три грани куба, расположенные в плоскостях XOY, YOZ и XOZ, и рассмотрим одну из таких проекций, например, XOY (См. рисунок).

Каждый k-ый отрезок спроектированной ломаной образует также 4 проекции на сторонах квадрата, сумма длин которых равна 2(xk + yk). Если сложить длины всех таких проекций для каждого отрезка, то получим S2(xk + yk). Если бы эта величина была больше 4ka (т.е. более чем в k раз превосходила периметр квадрата), то по принципу Дирихле на одной из сторон квадрата нашлась бы точка, покрытая не менее чем k+1 проекциями. Тогда прямая, проведенная через эту точку и параллельная стороне квадрата, пересечёт проекцию исходной ломаной не менее чем в k + 1 точках. Значит, если через эту прямую провести плоскость, параллельную грани, то она пересечет исходную ломаную по крайней мере в k + 1 точках.

Осталось показать, что для одной из трёх граней, на которые проектировалась ломаная, сумма длин проекций, лежащих на сторонах квадрата, будет больше 4ka, т.е. одна из величин S2(xk + yk), S2(zk + yk), S2(xk + zk) больше 4ka. Длина ломаной равна SLk = S[Ц(x2k+y2k+z2k)] и по предположению не меньше 3ka. Поэтому получаем

откуда

Если сумма трёх слагаемых больше 3·4ka, то по крайней мере одно из них больше 4ka, что и требовалось.

Непрерывный принцип Дирихле

Как правило, этот принцип применяется для нескольких чисел и их суммы. В общем виде для чисел он выглядит следующим образом:

"Если сумма n чисел больше S, то по крайней мере одно из этих чисел больше S/n".

По-другому его можно сформулировать так:

"Если среднее арифметическое нескольких чисел больше a, то хотя бы одно из этих чисел больше a";

или в терминах "зайцев":

"Если n кроликов съели m кг травы, то какой-то кролик съел не меньше m/n кг травы".

Кроме того, существует простая геометрическая интерпретация непрерывного принципа Дирихле:

"Пусть из некоторой точки на плоскости проведено N различных лучей; тогда угол между некоторыми двумя из них не менее 360°/N".

Понятно, что если рассматривать только углы между соседними лучами, то всего получится N углов (См. рисунок). В сумме они составляют полный угол, равный 360°. Следовательно,

по непрерывному принципу Дирихле градусная мера одного из этих углов не менее 360°/N (иначе их сумма будет меньше 360°).

Рассмотренный принцип называется непрерывным постольку, поскольку здесь числа (или градусные меры углов) могут принимать любое значение из некоторого промежутка, в то время как принцип Дирихле в обычном смысле оперирует с дискретным набором объектов ("зайцев") - было бы абсурдным предполагать, что в клетке может оказаться, скажем, два с половиной зайца.

Пример 17. На плоскости дано n попарно непараллельных прямых. Доказать, что найдутся две из них, угол между которыми не меньше 180°/n.

Указание. Достаточно перенести прямые параллельно самим себе так, чтобы все они проходили через одну точку. Из этой точки будет выходить 2n лучей, и теперь можно применить принцип Дирихле.

Пример 18. На полях шахматной доски 8×8 расставлены действительные числа, каждые два из которых отличаются не менее чем на 1/9. Доказать, что есть пара соседних (имеющих общую сторону) клеток, разность чисел в которых не меньше 1/2.

Решение Пусть A - наименьшее из выписанных на доске чисел, а B - наибольшее. Покажем, что B-A і7.

Запишем числа в порядке возрастания (заметим, что никакие два числа не равны):

(здесь x1 = A, x64 = B).

Тогда

Допустим теперь, что утверждение задачи неверно, т.е. в любой паре соседних клеток числа отличаются меньше чем на 1/2. Рассмотрим две клетки, в которых записаны числа A и B. Понятно, что, переходя из клетки в клетку, можно попасть из клетки A в клетку B, сделав не более 14 переходов. Самый худший случай, когда нужно сделать ровно 14 переходов, показан на рисунке (A, B - противоположные клетки). По предположению приращение на каждом переходе меньше 1/2. Поэтому B - A < 14·(1/2) = 7. Противоречие.

Список литературы

 [1] Андреев А.А., Горелов Г.Н., Люлев А.И., Савин А.И. "Принцип Дирихле", Самара "Пифагор", 1997г

[2] И. Л. Бабинская. Задачи математических олимпиад. М.: Наука, 1975.

[3] Д. X. Муштари. Подготовка к математическим олимпиадам: задачи, темы, методы. Казанский ун-т, 1990.

[4] В. В. Прасолов. Задачи по планиметрии. Ч. 2. М.: Наука, 1991.

[5] В. Г. Болтянский. Шесть зайцев в пяти клетках. // Ж-л «КВАНТ», 1977,No2.

[6] А. А. Леман. Сборник задач московских математических олимпиад. Под ред. В.Г. Болтянского. М.: Просвещение, 1965.

[7] Ю. Ф. Фоминых. Принцип Дирихле. // Ж-л «Математика в школе», 1996, No3.