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

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

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

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

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

Если хотя бы одна из этих сумм делится на 100, то наша цель достигнута. Допустим, что ни одно из чисел S₁ , S₂ , . . . , S₁₀₀ не делится на 100. Значит, два из них при делении на 100 дают равные остатки (т. к. сумм у нас 100, а различных остатков может быть лишь 99). Пусть это S_n и S_m (n < m). Тогда разность

делится на 100, и поэтому сумма x_{n + 1} +. . .+ x_m является искомой.

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

Решение

Рассмотрим последовательность a₁ = 1, a₂ = 11, . . . , a_n = = 11. . .1, . . . чисел, десятичная запись которых состоит из одних единиц. Поскольку существует лишь конечное число остатков от деления на 1997, а последовательность содержит бесконечно много членов, то, согласно принципу Дирихле, среди них найдутся два, дающих одинаковые остатки: a_k и a_l (k > l). Их разность a_k - a_l = 10^l ·a_{k - l} делится на 1997. Так как 10^l и 1997 - взаимно просты, то a_{k - l} делится на 1997. Это число Петя сможет записать.

КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ. Если числа a₁ , a₂ , . . . , a_n попарно взаимно просты, то для любых остатков r₁ , r₂ , . . ., r_n таких, что 0 Ј r_i < a_i при всех i = 1, 2, . . ., n, найдётся число N, которое при делении на a_i даёт остаток r_i при всех i = 1, 2, . . ., n.

Доказательство Применим индукцию по n. При n = 1 утверждение теоремы очевидно. Пусть теорема справедлива при n = k - 1, т.е. существует число M, дающее остаток r_i при делении на a_i при i = 1, 2, . . ., k - 1. Обозначим d = a₁ a₂ . . . a_{k - 1} и рассмотрим числа M, M + d, M + 2d, . . . , M + (a_k - 1)d. Покажем, что хотя бы одно из этих чисел даёт остаток r_k при делении на a_k . Допустим это не так. Поскольку количество чисел равно a_k , а возможных остатков при делении этих чисел на a_k может быть не более чем a_k - 1 (ведь ни одно число не даёт остаток r_k ), то среди них найдутся два числа, имеющих равные остатки (принцип Дирихле). Пусть это числа M + sd и M + td (0 Ј s Ј a_k - 1 и 0 Ј t Ј a_k - 1). Тогда их разность (M + sd) - (M + td) = (s - t)d делится на a_k , что невозможно, т.к. 0 < |s - t| < a_k и d = a₁ a₂ ...a_{k - 1} взаимно просто с a_k , ибо числа a₁ , a₂ , . . ., a_k попарно взаимно просты (по условию). Противоречие.

Таким образом, среди рассматриваемых чисел найдётся число N, которое при делении на a_k даёт остаток r_k . В то же время при делении на a₁ , a₂ , . . ., a_k-1 число N даёт остатки r₁ , r₂ , . . ., r_k-1 соответственно. Теорема доказана.

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

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

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

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

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

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

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

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

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

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

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

Решение Пусть S₁ , S₂ , . . . , S₁₀₀ - площади данных фигур, а Sў₁ , Sў₂ ,, . . . , Sў₁₀₀ - площади фигур, дополняющих их до квадрата. Понятно, что S_k + Sў_k = S. По условию S₁ +S₂ +. . .+S₁₀₀ > 99S, поэтому

Sў₁ + Sў₂ +. . .+ Sў₁₀₀ = (S- S₁ )+ (S- S₂ )+. . .+ (S- S₁₀₀ ) = 100S-(S₁ + S₂ +. . .+ S₁₀₀ ) < 100S-99S = S.

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

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

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

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

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