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

Решение Введём на клетчатой бумаге систему координат с началом координат в одном из узлов, осями, направленными вдоль линий сетки, и единичным отрезком, равным стороне клетки. Тогда все отмеченные точки будут иметь целочисленные координаты. Покажем, что найдутся две точки из пяти, у которых одна и та же чётность координат x и координат y. "Зайцами" у нас будут точки, а "клетками" - пары (Ч, Ч), (Ч, Н), (Н, Ч), (Н, Н). Если, например, у точки (x, y) координата x чётна, а координата y нечётна, то мы её поместим в "клетку" (Ч, Н). Итак, 5 "зайцев" и 4 "клетки". Пусть (x₁ , y₁ ) и (x₂ , y₂ ) - две точки, попавшие в одну "клетку". Середина отрезка, соединяющего эти две точки, имеет координаты ([(x₁ +x₂ )/ 2], [(y₁ +y₂ )/ 2]), которые являются целыми числами в силу одинаковой чётности x₁ и x₂ , y₁ и y₂ . Таким образом, середина этого отрезка лежит в узле сетки, т.е. данный отрезок является искомым.

Пример 6. На длинной прямолинейной дороге с равными интервалами вырыты небольшие поперечные канавки (См. рисунок). Расстояние между центрами каждых двух соседних канавок равно Ц2 метров. Доказать, что какими бы узенькими эти канавки ни были сделаны, человек, шагающий по дороге и имеющий длину шага 1 метр, рано или поздно попадёт в одну из канавок.

Решение Представим, что мы можем "намотать" дорогу на барабан, длина окружности которого равна Ц2 метров. Тогда все канавки на этом барабане совместятся, а каждый шаг человека будет изображаться на окружности дугой длины 1 метр. Будем последовательно отмечать на окружности след человека после первого, второго, третьего и так далее шагов. Нам надо доказать, что хотя бы один из этих следов попадёт внутрь заданной на окружности дуги, изображающей канавку, какой бы малой ни была длина h этой дуги. Нетрудно понять, что если нам удастся найти такие k и m, для которых следы k-го и (k+m)-го шагов удалены друг от друга (на окружности) меньше чем на h, то требуемое утверждение докажется легко. Ведь ещё после m шагов новый след (то есть (k+2m)-й) опять сдвинется на расстояние меньшее h, затем мы рассмотрим следующие m шагов и так далее. Ясно теперь, что, сделав несколько раз по m шагов, мы неминуемо обнаружим след, попавший в канавку (потому что, перемещаясь на одно и то же расстояние, меньшее h, нельзя "перешагнуть" канавку ширины h). Итак, нужно найти два следа, находящиеся на окружности на расстоянии, меньшем h. Вот здесь-то и помогают "зайцы". Действительно, разделим окружность на дуги, каждая из которых имеет длину меньше h; эти дуги мы и назовём "клетками". Пусть их имеется p штук. Если мы возьмём число следов большее, чем p (заметим, что никакие два следа не совпадут в силу иррациональности числа Ц2), то по принципу Дирихле хотя бы в одну из клеток попадёт более одного следа ("зайца"). Расстояние между двумя следами, попавшими в одну "клетку", меньше h; этим наше утверждение и доказано.

В ряде задач применяют следующее обобщение принципа Дирихле.

ФОРМУЛИРОВКА 3. "Если nk+1 зайцев размещены в n клетках, то найдутся k+1 зайцев, которые посажены в одну клетку (n, k - натуральные числа)".

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

Пример 7. В прямоугольнике 5×6 закрашено 19 клеток. Докажите, что в нём можно выбрать квадрат 2×2, в котором закрашено не менее трёх клеток.

Решение

Разделим прямоугольник на 6 частей по 5 клеток (Cм. рисунок). Согласно принципу Дирихле в одной из этих частей будет закрашено не менее 4 клеток. Тогда в квадрате 2×2, содержащемся в этой части, закрашено либо 3, либо 4 клетки. Это и будет искомый квадрат.

Пример 8. В классе 25 человек. Известно, что среди любых трёх из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.

Решение Выберем любых двух учеников класса, которые не дружат между собой. (Если таких нет, то все ученики класса дружат между собой, значит, у каждого имеется 24 друга, и задача решена.) Из оставшихся 23 учеников каждый дружит с одним из этих двух, иначе мы имели бы тройку учеников, среди которых не было бы друзей. Тогда у одного из выбранных двух учеников не менее 12 друзей. (23 "зайца" рассажены в двух "клетках".)

Пример 9. В единичный квадрат бросили 51 точку. Доказать, что какие-то три из них можно накрыть кругом радиуса 1/7.

Решение Разобьём данный квадрат на 25 одинаковых квадратиков ("клеток") со стороной 1/5. В один из них попадёт не менее трёх точек ("зайцев"). Окружность, описанная около квадратика со стороной 1/5, имеет радиус ¹ /₅ ·[(Ц2)/ 2] = [1/( [Ц50])] < [1/( [Ц49])] = ¹ /₇ , поэтому этот квадратик можно накрыть кругом радиуса 1/7.

Принцип Дирихле в теории чисел

Следующую теорему часто используют в школьном курсе алгебры, но доказательство не рассматривают. Его очень просто получить с помощью принципа Дирихле.

ТЕОРЕМА 1. Пусть p, q - натуральные числа, p < q. Если обыкновенную дробь p/q обратить в десятичную, то получится либо конечная, либо бесконечная периодическая десятичная дробь, причём длина периода не превосходит q-1.

Доказательство Будем делить p на q "уголком" и следить за остатками. Если на каком-то шаге остаток будет нулевым, то получится конечная дробь. Если же все остатки будут отличны от нуля, то рациональное число p/q запишется в виде бесконечной десятичной дроби. Докажем, что она будет периодической. Каждый раз при нахождении очередной цифры частного будет получаться в остатке одно из чисел 1, 2, ..., q-1. Эти возможные значения остатков мы и будем считать "клетками", так что всего имеется q-1 "клеток". "Зайцами" же будут остатки, которые получаются в действительности при выполнении деления (См. рисунок). Рассмотрим первых q "зайцев". Так как их на 1 больше, чем число "клеток", то какие-то два "зайца" попадут в одну "клетку". Другими словами, не позже, чем через q - 1 шагов начнут повторяться остатки, а вслед за этим - и цифры в частном. Действительно, если на некотором шаге повторился остаток, то, приписав как обычно к нему 0, мы получим то же число, что было прежде, а, значит, снесём в частное ту же самую цифру, что и раньше; поэтому наши действия начнут повторяться. Таким образом, получится периодическая десятичная дробь с периодом длиной не более q - 1.

С давних пор математиков интересовал вопрос о существовании функций f(k), значениями которых при всех натуральных k являлись бы только простые числа. Известны функции, которые принимают подряд много простых значений. Например, Эйлер указал интересный многочлен x² - x + 41, который при всех целых x от -39 до 40 включительно принимает только простые значения (т.е. при x = 0, ±1, ±2, . . . , ±39, 40). Однако при x = 41 и x = 42 значения этого многочлена будут уже составными числами. В общем случае многочлен с целыми коэффициентами не может при всех натуральных значениях аргумента принимать только простые значения.

ТЕОРЕМА 2. Любой многочлен с целыми коэффициентами (отличный от константы) при некотором натуральном значении аргумента принимает значение, представляющее собой составное число.

Доказательство Пусть f(x) = a₀ xⁿ + a₁ x^{n - 1} +. . . +a_n , где все a_i - целые числа. Предположим, что при некотором k значение многочлена f(x) - простое число, т.е. f(k) = p, где p - простое. Многочлен степени n принимает одно и то же значение не более чем в n точках. (Действительно, если f(x) = y₀ более чем в n точках x₁ , x₂ , . . ., x_{n + 1} , то многочлен g(x) = f(x)-y₀ имеет корни x₁ , x₂ , . . ., x_{n + 1} , а, как известно, любой многочлен не может иметь более n действительных корней.) Покажем, что найдётся такое целое t, что f(k+pt) отлично от 0 и p. Нам поможет принцип Дирихле. Будем считать значени многочлена (в натуральных точках) "клетками", а натуральные числа вида k+pt "зайцами". Натуральное число N = k+pt будем помещать в "клетку", соответствующую значению многочлена f(N). Согласно высказанному выше утверждению, в "клетке" не может поместитьс больше n "зайцев". Так как "зайцев" много, то это значит, что f(k + pt) не может принимать только значени 0 и p при различных целых t, т.е. найдётся "заяц" k+pt, который не попадёт ни в "клетку" 0, ни в "клетку" p. Итак, при некотором t имеем: f(k + pt) № 0 и f(k + pt) № p. Разлагая f(k + pt) по степеням pt (используя бином Ньютона), получим

где все c_i - некоторые целые числа. Поскольку f(k) = p, из предыдущего равенства получаем, что f(k + pt) делится на p, причём f(k + pt) № 0 и f(k + pt) № p, так что f(k + pt) - составное число. Теорема доказана.

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

Следующая теорема, сформулированная П. Ферма, является одним из самых фундаментальных фактов в теории делимости целых чисел и находит широкое применение как в теоретических исследованиях, так и в арифметических приложениях.

МАЛАЯ ТЕОРЕМА ФЕРМА. Если p - простое число, a - целое число, не делящееся на p, то a^{p - 1} при делении на p даёт остаток 1, т. е.

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

Если число различных встречающихся здесь остатков ("клеток") меньше p - 1, то среди них найдутся по крайней мере два одинаковых ("в клетке по крайней мере два зайца"). Но это невозможно, так как при r_n = r_m число (n-m)a = (k_n -k_m )p делится на p, что противоречиво, ибо |n-m| < p и a взаимно просто с p. Значит, все остатки r₁ , . . . , r_{p - 1} между собой различны и образуют перестановку чисел 1, 2, . . . , p - 1. Перемножая все предыдущие равенства, получаем

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

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

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

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