Принцип Дирихле
Категория реферата: Рефераты по математике
Теги реферата: бесплатные доклады, где диплом
Добавил(а) на сайт: El'chenko.
Предыдущая страница реферата | 1 2 3 4 5 6 7 | Следующая страница реферата
Решение По крайней мере два числа из 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
Доказательство Применим индукцию по 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|
Таким образом, среди рассматриваемых чисел найдётся число 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".
В качестве упражнения докажите все эти утверждения методом от противного и попробуйте сформулировать аналогичные им (например, для тел и объёмов).
Рекомендуем скачать другие рефераты по теме: государство курсовая работа, культура скачать реферат.
Предыдущая страница реферата | 1 2 3 4 5 6 7 | Следующая страница реферата