Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата



Так как "зайцев" больше, чем "клеток", то найдутся два "зайца", сидящих в одной "клетке". Иначе говоря, среди чисел 1, 2, . . . , N+1 найдутся такие два числа k1 < k2, что

k1a = m1 +x1 , 0 Ј x1 < 1,

k2a = m2 +x2 , 0 Ј x2 < 1,

причём x1 и x2 находятся в одной "клетке", и поэтому |x2-x1| Ј 1/N.

Таким образом,

|(k2-k1)a-(m2-m1)| = |(k2a-m2)-(k1-m1)| = |x2-x1| 1 N ,

то есть числа k = k2 - k1 и m = m2 - m1 являются искомыми. Здесь k > 0, так как k2 > k1, и m і 0, так как k2a - k1a = (m2 + x2) - (m1 + x1) > 0, откуда m2 - m1 > x1 - x2 > -1 (ведь 0 Ј x1 < 1 и 0 Ј x2 < 1), и поскольку m1 и m2 - целые числа, m2 - m1 і 0.

Пример 5. На клетчатой бумаге отметили 5 точек, расположенных в узлах клеток. Доказать, что хотя бы один из отрезков, соединяющих эти точки, проходит через узел клетки.

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

Пример 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, имеет радиус 1/5·[(Ц2)/ 2] = [1/( [Ц50])] < [1/( [Ц49])] = 1/7, поэтому этот квадратик можно накрыть кругом радиуса 1/7.

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

Рекомендуем скачать другие рефераты по теме: государство курсовая работа, культура скачать реферат.

Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки