ПРИНЦИП ДИРИХЛЕ

Министерство образования,науки,молодежи и спорта.

МБОУ Черноморская средняя школа №1

Имени Николая Кудри

Черноморского районного совета АРК

ПРИНЦИП  ДИРИХЛЕ

Творческая работа

Учащейся 10-М класса

МБОУ ЧСШ №1

Титовой Русланы 

Научный руководитель

Ткаченко И.А

Учитель математики,

Учитель высшей категории

”Старший учитель“

Содержание:

Введение..................................................3

Глава 1:Биография Петра Дирихле.................................................5

Глава 2:Формулировка принципа Дирихле...................................................6

Глава 3:Доказательство принципа Дирихле.................................................12

Глава 4:Принцип Дирихле в теории чисел......................................................14

Глава 5:Принцип Дирихле для длин и площадей...............................................17

Глава 6:Непрерывный приницип Дирихле.................................................20

Глава 7 : Практика. Решение задач на принцип Дирихле..................................23

Заключение...........................................30

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

Введение

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

 Объектом моей исследовательской работы  является способ решения логических задач. Логическая задача – это особый вид задачи, который развивает логику, образное и творческое мышление, поэтому часто такие задачи являются олимпиадными.

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

Актуальность :

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

Цель:

изучить принцип и понять в каких случаях прицип  Дирихле встречается в математических задачах. Доказать необходимость приминения этого принципа.

Задачи:

Изучить  принцип Дирихле., где человеку не обойтись без этого принципа;

2.Отобрать и систематизировать задачи, решаемые с помощью принципа Дирихле

3.Сформулировать Принцип Дирихле.;

4.Доказать формулировку принципа Дирихле.

5.Разобрать принцип Дирихле в теории чисел;

6.Разобрать принцип Дирихле для длин и площадей;

7.Показать на практике решения задач принцип Дирихле

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

Мной использовались следующие методы исследования :

Теория

Исследование

Поиск

Сравнение

Новизна:

Данная тема очень актуальна в наше время.Роль олимпиад с каждым годом становится все более значимой. И не случайно многие вузы стали проводить свои олимпиады для будущих абитуриентов, преследуя цель - привлечь школьников в данный вуз. Победители, занявшие призовые места, имеют преимущества при зачислении абитуриентов в вуз. Решая олимпиадные задания,для решения некоторой группы задач используется определённый способ, называемый принципом Дирихле, я решила изучить его подробнее.

Глава 1: Петр Дирихле

Пути развития современной математики в значительной мере были предопределены трудами немецкою ученого XIX века Петером Густавом Лежен Дирихле. Петер Дирихле родился 13 февраля 1805 года в Дюрине, Рейнской провинции. В 1822 году он переехал в Париж, где поселился в доме генерала Фау. В семье Фау Дирихле был домашним учителем в течение пяти лет. Здесь ему представился удобный случай познакомиться со многими знаменитыми учеными, философами и математиками. В то же время он изучал труды Гаусса и посещал его лекции. В 1826 году Дирихле возвратился в Германию, где получил должность приват-доцента в Бреславльском университете (ныне Вроцлавском), а потом переехал в Берлин. Здесь он был сначала приват-доцентом (1829 год), а затем ординарном профессором (1831 год) в университете. Одновременно он стал преподавателем военного училища. В 1855 году Дирихле был приглашен в Геттинский университет в качестве продолжателя Гаусса. В 1837 году Дирихле был избран иностранным членом-корресподнентом Петербургской Академии Наук.

Оригинальное творчество Дирихле касается, в основном теории чисел, теории рядов, интегрального исчисления и некоторых проблем математической физики. Ученый установил формулы для числа бинарных квадратных форм с заданным определителем и доказал теорему о бесконечности количества простых чисел в арифметической прогрессии из целых чисел, член и разность которой - взаимно просты. Дирихле создал общую теорию алгебраических единиц в алгебраическом числовом поле. Дирихле утверждал, что в математике большое значение имеют так называемые доказательства существования. Самый простой способ доказать существование объекта с заданными свойствами - это указать его и, разумеется убедиться, что он действительно обладает нужными свойствами. Например, чтобы доказать, что уравнение имеет решение, достаточно привести какое-то его решение. Доказательство существование такого рода называется прямым или конструктивным...

Глава 2: Формулировка принципа Дирихле

Самая популярная формулировка принципа Дирихле звучит так:

ФОРМУЛИРОВКА 1. ”Если в n клетках сидит n+1 или больше зайцев,то найдётся клетка, в которой сидят по крайней мере два зайца” .

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

ФОРМУЛИРОВКА 2. “ При любом отображении множества Р, содержащего  n+1 элементов, в множество Q, содержащее n элементов, найдутся два элемента множества Р, имеющие один и тот же образ” .

Несмотря на совершенную очевидность этот принципа, его применение является весьма эффективным методом решения задач, дающим во многих случаях наиболее простое и изящное решение. Однако во всех этих задачах часто нелегко догадаться, что считать “зайцем", что - ”клеткой", и как использовать наличие двух “зайцев”, попавших в одну ”клетку". С помощью принципа Дирихле обычно доказывается существование некоторого объекта, не указывая, вообще говоря, алгоритм ею нахождения или построения. Эго
даёт так называемое неконструктивное доказательство - мы не можем сказать, в какой именно клетке сидят два зайца, а знаем только, что такая клетка есть.

Приводимые ниже теоремы и задачи показывают, что природа ”зайцев” и ” клеток” в различных задачах может сильно отличаться друг от друга.

Пример 1. Доказать, что если прямая 1, расположенная в плоскости
треугольника АВС, не проходит ни через одну из его вершин, то она не может пересечь все три стороны треугольника.

Решение :

Полуплоскости, на которые прямая 1 разбивает плоскость треугольника АВС, обозначим через  q1 и q2 ; эти полуплоскости будем считать открытыми (то есть не содержащими точек прямой 1). Вершины рассматриваемою треугольника (точки А, В, С) будут “зайцами”, а полуплоскости  q1 и q2 - ”клеткам”. Каждый ”заяц” попадает в какую-нибудь ”клетку” (ведь прямая 1 не проходит ни через одну из точек А, В, С). Так как ”зайцев" три, а ”клеток” только две, то найдутся два ”зайца", попавшиев одну “клетку”, иначе говоря, найдутся такие две вершины треугольника АВС, которые принадлежат одной полуплоскости.

Пусть, скажем, точки А и В находятся в одной полуплоскости, то есть лежат по одну сторону от прямой 1. Тогда отрезок АВ не пересекается с 1. Итак, в треугольнике АВС нашлась сторона, которая не пересекается с прямой 1.

Пример 2. Внутри равностороннею треугольника со стороной 1 расположено 5 точек. Доказать, что расстояние между некоторыми двумя из них меньше 0,5.

Решение: 

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

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

Решение:

Существует n-1 способов вращения стола, после каждого из них взаимное расположение флагов и послов изменится. Каждому послу сопоставим вращение, после которою он окажется рядом со своим флагом. Согласно принципу Дирихле при каком-то вращении два (может, и больше) посла окажутся рядом со своим флагом. В решении задачи роль играют, естественно, послы, а роль ”клеток" - положения стола при различных вращениях. Посол попадает в ”клетку", если при соответствующем этой ”клетке” вращении стола он оказывается рядом с флатом своей страны. Таким образом, ”клеток” у нас n- 1, а ”зайцев” - n.

Замечание: Условие о том, что вначале ни один из послов не находится рядом со своим флагом, существенно. На самом деле первоначальное положение также является ”клеткой”, но эта “клетка” по условию заведомо окажется пустой. Так что можно считать, что всего “клеток" имеется  n- 1.

Пример 4. 

Доказать,что для любого действительною числа а > 0 и любого натурального N найдутся такие целые m i 0 и k > 0, что  lka-ml J1/N.

Решение:

Разобьём отрезок [0, 1] точками 1/N, 2/N, ... , [(N-1)/( N)] на N отрезков. Полученные отрезки будем  считать ”клетками”, а числа 1,2....., N+1 примем в качестве ”зайцев".

Если k- один из ”зайцев”, то число kа можно записать в виде kа=m + х, где m- целое, 0Ј х < 1 (т. е. в виде суммы целой и дробной части). Число х попадает в одну из ”клеток"; в эту ”клетку” мы и посадим ”зайца” К. Так как ”зайцев” больше, чем ”клеток", то найдутся два ”зайца", сидящих в одной ”клетке”. Иначе говоря, среди чисел 1, 2, ... , N+1 найдутся такие два числа k1 < k2, что k1а=m1+X1 ,ОЈ .

K2a = m2 +х2 , ОЈ

 причём x1 и х2 находятся в одной ”клетке”, и поэтому lX2-X2l Ј 1/N. Таким образом,

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

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

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

Решение :

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

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

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

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

Решение :

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

Пример 7.

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

Решение:

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

Пример 8.

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

Решение:

 Разобьём данный квадрат на 25 одинаковых квадратиков ("клеток") со стороной 1/5. В один из них попадёт не менее трёх точек ("зайцев”).

Окружность, описанная около квадратика со стороной 1/5, имеет радиус

= 1/7, поэтому этот квадратик можно

= [1/5 [Ц2]/2] =[1/(Ц50< [1/( [Ц49])] =1/7,поэтому этот квадратик можно  накрыть кругом радиуса 1/7.

Глава З:Доказательство принципа Дирихле

Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются.

Допустим, что в каждом ящике сидят меньше чем n/k кроликов. Тогда во всех ящиках вместе кроликов меньше, чем (n/k)*k=n. Противоречие.

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

Принцип Дирихле бывает непрерывным: Если n кроликов съели m кг травы, то какой-то кролик съел не меньше m/n кг и какой-то съел не больше m/n кг (а если кто-то съел больше среднего, то кто-то съел меньше среднего). И Заметим, что в последней формулировке кролики играют роль ящиков для травы, а трава,• роль кроликов, сидящих в ящиках.

Пример 1. В школе 400 учеников. Докажите, что хотя бы двое из них

родились в один день года.

Решение. Всего в году бывает 366 дней. Назовем дни ящиками, а учеников кроликами. Тогда в некотором ящике сидят не меньше Я кроликов, т.е. больше одного. Следовательно, не меньше двух.

Можно рассуждать от противного. Допустим, что каждый день отмечают день рождения не больше одного ученика, тогда всего учеников не больше 366. Противоречие.

Пример 2. Кот Базилио пообещал Буратино открыть великую тайну, если он составит квадрат 6 х 6 из чисел +1, 1, 0 так, чтобы все суммы по строкам, по столбцам и по большим диагоналям были различны. Помогите Буратино.

Решение. Допустим, что квадрат составлен. Тогда суммы чисел могут меняться в пределах от 6 до +6. Всего 13 значений. Строк в квадрате 6, столбцов 6, диагоналей 2. Получаем 14 различных сумм. Противоречие, значит составить такой квадрат невозможно.

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

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

Пример 4. На собеседование пришли 65 школьников. Им предложили З контрольных работы. За каждую контрольную ставилась одна из оценок: 2, З, 4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на всех контрольных?

Решение. Рассмотрим множество наборов из трех оценок за соответствующие контрольные. Количество таких наборов равно 4— или 64 (4 возможности за каждую из трех контрольных). Поскольку число учащихся больше 64, по принципу Дирихле каким-то двум учащимся отвечает один набор оценок.

Глава 4: Принцип Дирихле в теории чисел

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

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

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

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

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

Решение:

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

Пример 2. Доказать, что если имеется 100 целых чисел Ч, х), ..

• X100, ТО из них можно выбрать чисел (может быть, одно), сумма которых делится на

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

S1=

S2=x1+

S3=x1+x2+

….…………..

S100=x1+x2+x3+…+x100.

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

.

КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ.

 Если числа a1,a2,…..,аn попарно взаимно просты. то для любых остатков r1 ,r2…..,rn  таких ,что oJri всех i = 1, 2, .....n, найдётся число N, которое при делении на ai даёт остаток ri при всех i = 1, 2, . п.

Глава 5: Принцип Дирихле для длин и

площадей

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

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

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

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

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

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

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

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

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

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

Решение Пусть S1, S2, ……S100-

площади фигур, дополняющих их до квадрата.Понятно, что Sk + SYk

= S. По условию S1+S2+….+S100 > 99S, поэтому SY1+ SY2+.. .+ SY100 = (S- S1)+ (S- S2)+.. .+ (S-S100) = 100S-(S1+ S2+.. .+S100) < 100S-99S = S.

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

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

Решение :

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

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

Решение

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

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

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

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

Глава 6:Непрерывный принцип Дирихле

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

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

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

”Если среднее арифметическое нескольких чисел больше а, тогда хотя бы одно из этих чисел больше а”; или в терминах ”зайцев”

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

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

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

Понятно, что если рассматривать только углы между соседними лучами, то всего получится N углов. В сумме они составляют полный угол, равный 360 . Следовательно, по непрерывному принципу Дирихле градусная мера однот из этих углов не менее 360 (иначе их сумма будет меньше 3600).

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

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

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

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

Решение

 Пусть А- наименьшее из выписанных на доске чисел, а В- наибольшее. Покажем, что В-А i7. Запишем числа в порядке возрастания (заметим, что никакие два числа неравны):

X1

Здесь x1=A,x64=B

Тогда

B-A=x64-x1=(x64-x63)+(x63-x62)+…+(x3-x2)+(x2-x1)i

(1/9) + (1/9) + ... + (1/9) = 63-(1/9) = 7.

Допустим теперь, что утверждение задачи неверно, т.е. в любой паре соседних клеток числа отличаются меньше чем на 1/2. Рассмотрим две клетки, в которых записаны числа А и В. Понятно, что, переходя из клетки в клетку, можно попасть из клетки А в клетку В, сделав не более 14 переходов.

Глава 7: Практика. Решение задач на

принцип Дирихле

Задача 1. В корзине лежат 30 грибов - рыжиков и груздей.

Известно, что среди любых 12 грибов имеется хотя бы один рыжик, а среди любых 20 грибов - хотя бы один груздь. Сколько рыжиков и сколько груздей в корзине.

Решение:

19 рыжиков и 11 груздей. Если бы в корзине нашлись 12 груздей, то ни один из них не был бы рыжиком, следовательно, количество груздей не превосходит 11. Если бы груздей было меньше 11, то их было бы не больше 10. В этом случае можно было бы найти 20 не груздей, следовательно, труздей - 11. Рыжиков - 19.

Задача 2. В мешке лежат шарики двух разных цветов: черного и белого. Какое наименьшее число шариков нужно вынуть из мешка вслепую так, чтобы среди них заведомо оказались два шарика одного цвета?

Решение: 

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

Ясно, что ” зайцами ” здесь являются шарики, а ” клетками“ - цвета: черный и белый.

Задача З. В магазин привезли 25 ящиков с тремя сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков одного  сорта.

Решение:

В решении этой задачи нам поможет обобщенный принцип

Дирихле: ” Если в n клетках сидят не менее kn+1 зайцев, то в какой-то из клеток сидит, по крайней мере, К + заяц. 25 ящиков — ”зайцев” - рассадим по З ”клеткам” - сортам. Так как 25 = З * 8 + 1, то, применив обобщенный принцип Дирихле для n= З, k = 8, получим, что в какой-то ” клетке” — сорте не менее 9 ящиков.

Задача 4. В квадрате со стороной 1 м бросили 51 точку. Докажите, что какие-то З точки из них можно накрыть квадратом со стороной 20 см.

Решение: Разобьем квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле в какой-то из них попадет по крайней мере З точки из 51 брошенной. Замеппш, что в основе принципа лежит идея сложения неравенств. одно замечательное свойство из неё гласит: ” Если сумма п чисел равна S, то среди них есть как число не большее S:n и число не меньшее S:n

Задача 5. В бригаде 7 человек и их суммарный возраст 332 года. Докажите, что из них можно выбрать трех человек, сумма возрастов которых не меньше 142.

Решение:

 Рассмотрим всевозможные тройки рабочих бригад. Сумма суммарных возрастов, как легко подсчитать, равна 15*332, а таких троек 35. Значит, есть тройка, суммарный возраст в которой не меньше, чем что больше 142.

Задача 6:

 В непрозрачном мешке лежат 5 белых и 2 черных шара. а) Какое наименьшее число шаров надо вытащить из мешка, чтобы среди них обязательно оказался хотя бы один белый шар?

Решение:

 “Худшим”, здесь является случай, когда мы будем

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

б) Сколько шаров надо вытащить, чтобы среди них обязательно оказался хотя бы один белый и хотя бы один черный шар?

Решение: ” Худшим ” здесь является случай, когда мы сначала будем вытаскивать одни белые шары и только потом попадается один черный шар. Поэтому потребуется вытащить 5 + 1 = 6 шаров.

в) Какое наименьшее число шаров надо вытащить, чтобы среди них наверняка оказались З белых и 1 черный шар?

Решение: В ” худшем ” случае мы сначала вытащим все белые шары, и затем лишь пойдут черные. Тогда придется вытащить 5 + 1 =6 шаров.

г) Сколько шаров надо вытащить, чтобы среди них оказались два шара одного цвета?

Решение: “ Худший ” случай - когда сначала идут шары разных цветов. Эго возможно, если мы вытащим 2 шара. А если мы вытащим третий, то уже будем иметь два шара одного цвета.

Задача 7. Сколько надо взять двузначных чисел, чтобы по крайней мере одно из них делилось: а) на 2, б) на 7?

Решение:

а) В ” худшем ” случае, вытаскивая из мешка числа от 10 до 99, мы сначала будем иметь только нечетные числа - их 45, и поэтому 46- е число обязательно будет четным.

б) Среди 90 чисел от 10 до 99 имеется всего 13 чисел, делящихся на 7, т.е. в ”худшем ” случае мы сначала вытащим 90 - 13 = 77 чисел, не делящихся на 7, но 78-е число уже точно будет делиться на 7.

Задача 8. Дано 12 целых чисел. Докажите, что из них можно

выбрать два, разность которых делится на 11.

Решение: Решение этой задачи можно начать с вопроса о количестве различных остатков от деления числа на 11. Получив ответ, что их ровно 11, можно сделать вывод о том, что среди 12 чисел найдутся, по крайней мере, два, имеющие одинаковые остатки.Разность этихчисел и будет делится на 11. После этого надо найти ” зайцев“ (12 чисел) и ” клетки ” (остатки от деления на 11).

Задача 9. Докажите, что в любой копании из пяти человек двое имеют одинаковое число знакомых.

Решение:

Имеются пять вариантов числа знакомых: от 0 до 4.0стается заметить, что если у кого-то четверо знакомых, то ни у кого не может быть ноль знакомых. ("Клетки", соответствующие 0 и 4, взаимно исключают друг друга.) Поэтому можно говорить о четырех ” клетках вариантах числа знакомых. Поскольку в компании пять человек — ”зайцев по принципу Дирихле обязательно найдутся хотя бы два человека, имеющие одинаковое число знакомых.

Задача 10. 10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть решившие ровно одну задачу, решившие ровно две задачи и решившие ровно три задачи. Докажите, что среди них есть школьник, решивший не менее пяти задач.

Решение:

 Из условия задачи можно заключить, что найдутся семь школьников, решивших 35 - (1 + 2 + З) = 29 задач. Так как 7 * 4 + 1, то найдется школьник, решивший не менее 5 задач.

Задача 11. В школе 20 классов. В ближайшем доме живут 23 ученика этой школы. Можно ли утверждать, что среди них обязательно найдутся хотя бы два одноклассника?

Решение: Можно, так как классов (20) меньше, чем учеников (23).

Задача 12. В школе учится 370 человек. Докажете, что среди всех учащихся найдутся два человека, празднующие свой день рождения в один и тот же день.

Решение:

В году 365 дней, следовательно, у 5 учеников дни рождения могут совпасть.

Задача 13. Коля подсчитал, что за завтрак, обед и ужин он съел 10 конфет. Докажите, что хотя бы один раз он съел не меньше 4 конфет.

Решение:

Доказываемое утверждение следует из равенства: 10 = 3*3

Задача 14. В классе 37 человек. Докажите, что среди них найдутся 4 человека с одинаковым числом дня рождения.

Решение:

 В любом месяце дней не более 31, значит, для 37 учеников есть одинаковые числа, месяц роли не играет.

Задача 15.Имеются три ключа от трех чемоданов с разными замками. Достаточно ли трех проб, чтобы открыть чемодан?

Решение: Достаточно.

Задача 16. Цифры 1, 2, З, 4, 5, 6, 7, 8, 9 разбили на З группы.

Докажите, что произведение чисел в одной из групп не меньше 72.

Решение:

 Если бы каждое из полученных произведений было меньше 72, то произведение всех чисел от 1 до 9 не превосходило бы 713= 357911. но 1 = 362880 > 357911.

Задача 17. Сто человек сидят за круглым столом, причем более половины из них - мужчины. Докажите, что какие-то двое мужчин сидят друг напротив друга.

Решение:

В противном случае женщин было бы не меньше, чем мужчин, что противоречит условию задачи.

Задача 18. На планете Тау - Кита суша занимает более половины площади планеты. Докажите, что тау-китяне могут прорыть тоннель, проходящий через центр планеты и соединяющий сушу с сушей.

Решение:

Покрасим всю сушу в синий цвет, а все точки, диаметрально противоположные суше — в красный. Тощади синей и красной частей планеты будут равными. Если все красные точки покрыты водой, получаем противоречие с условием задачи. Поэтому найдется точка, покрашенная в оба цвета. В ней и надо рыть туннель.

Задача 19. Иван-царевич добыл ключи от нескольких комнат в

подземелье, но не знал, какой ключ от какой комнаты. Сколько комнат в подземелье, если, как подсчитал Иван-царевич, в худшем случае, ему достаточно 20 проб, чтобы выяснить, какой ключ от какой комнаты.

Решение: Первым ключом Иван-Царевич пробует открыть все двери (или меньше, если ключ к какой-то двери подойдет раньше), вторым — все, кроме одной, и т. д. предпоследним — две, последним — ни одной (дверь осталась одна). Так как 2 + З + 4 + 5 + 6 = 20, в подземелье 6 дверей.

Задача 20. Доказать, что среди шести целых чисел найдутся два числа, разность которых делится на 5.

Решение:

 Рассмотрим 5 коробок, пронумерованных 0,1,2,3,4, цифрами, представляющими собой остатки от деления на 5.

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

Заключение:

Я пришла к выводу, что оказывается, не так сложно решать различные задачи на доказательство, которые встречались во время олимпиад по математике. Пожалуй, самым сложным при решении задач является умение определить какая величина в задаче выполняет роль «ящика», а какая «зайца».

Данная тема так увлекла меня, что я решила попробовать самостоятельно составить задачи, аналогичные рассмотренным. По-моему у меня все получилось.

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

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

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

Самара ”Пифагор", 1997г

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

[З] Д. Х. Муштари. Подттовка к математическим олимпиадам: задачи, темы,

методы. Казанский ун-т, 1990.

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

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

1977,N02.

[6] А. А. Леман. Сборник задач московских математических олимпиад. Под

ред. В.Г. Болтянскот. М.: Просвещение, 1965.

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

МЗ.