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

Математика и шутка. Кажется, это не совместимое сочетание. Ведь математика – весьма серьезная, строгая наука. С ней шутки плохи – спросите любого ученика.

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

Может поэтому взрослые, солидные люди пытаются математический материал рассказать увлекательно.

В 5 классе целый ряд задач учительница назвала «Задачи про фазанов и кроликов», и весело рассказывала, что кролики могут стоять на задних лапках, поджав передние. Целый урок потом мы вместе примеряли «костюмы» кроликов то на коров, то на восемнадцатилистовые тетради, а то на двухместные лодки или трехколесные велосипеды.

В этом году в старом мамином журнале «Квант» я нашел интересную статью про кроликов.

Итальянский купец Леонардо из Пизы, по прозвищу Фибоначчи, т. е. «сын Боначчо» (Боначчо – добродушный) придумал забавную задачку про родившихся за год в клетке кроликов. Решение этой задачи навеки внесло его имя в списки творцов математической науки, я же познакомился с рядом Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

Еще узнал, что отношение двух соседствующих чисел этой последовательности обладает уникальным свойством – приближенностью к 1,168 и имеет большое значение в изобразительном искусстве, архитектуре, вездесуще присутствует в природе (семена подсолнечника, раковины моллюсков, расположение листьев на стеблях растений, пропорции человека). Забавные «кролики», не правда ли?

В детской математической энциклопедии я решил поискать моих знакомых кроликов. И представляете мою радость, когда я их нашел. «Если в n клетках сидит n+1 или более кроликов Дирихле»

Петер Густав Лежен Дирихле – великий математик XIX века родился 13 февраля 1805 года в городе Дюрене и в семнадцать лет начал карьеру домашнего учителя в Париже, но продолжал заниматься наукой и встречался с Фурье. К 1831 году Дирихле стал профессором сначала Берлинского, а затем Геттингенского университета. Он занимался теорией чисел, доказал теорему Ферма для n =5, сформулировал общее понятие функции. В высшей математике существует задача Дирихле, ряды Дирихле, функция Дирихле, принцип Дирихле. У Петера Лежена было много последователей и учеников, в их числе Г. Риман.

Принцип Дирихле по традиции объясняют на примере «кроликов и клеток», может потому, что профессор когда-то был учителем? А может, он очень уважал Фибоначчи ?

2.КЛЕТКИ И КРОЛИКИ

В математике много задач на доказательство существования. Самый простой способ доказательства – найти объект, который действительно обладает заданными свойствами. Например, чтобы доказать, что уравнение имеет решение, достаточно привести какое-то его решение. Такого рода доказательство называется ПРЯМЫМ.

Но бывают КОСВЕННЫЕ доказательства существования, когда существование объекта доказывается без прямого участия этого объекта: в этом лесу есть медведь, потому что мы видим его следы, где он находится в настоящий момент?, возможно в какой-то берлоге, это не главное, важно, что ОН ЕСТЬ!

Разберем какую-нибудь необычную задачу: Новый год был недавно.

В лесу 500 000 елок, на каждой елке не более 300 000 иголок. Необходимо показать, что как минимум у двух елок число иголок одинаково.

Что-то с первого взгляда не видно, с использованием какого знакомого алгоритма может быть решена эта задача. Как говориться: это мы не проходили

Будем исходить из того, что на всех елках различное количество иголок. Предположим, что на первой елке – 1 иголка; на второй – 2 иголки (не меньше, иначе совпадение с первой елкой), соответственно, третья елка – 3 иголки, и т. д.

300001ая елка – сколько иголок? Предел достигнут, а еще осталось 200 000 елок. Значит, количество иголок на них неизбежно должно повториться с какой-либо из рассмотренных елок.

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

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

Если множество из N элементов разбито на n непересекающихся частей, не имеющих общих звеньев, где N > n, то, по крайней мере, в одной части будет более одного элемента.

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

При любом отображении множества P, содержащего n+1 элементов, множество Q, содержащее n элементов, найдутся два элемента множества Р, имеющих один и тот же образ.

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

Если в n «клетках» сидят не менее n+ 1 «кроликов», то найдется «клетка», в которой сидит, по крайней мере, не менее двух «кроликов».

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

Заметим, что в роли кроликов могут выступать различные предметы и математические объекты – числа, отрезки, места в таблице и т. д.

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

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

Задача 1.

В мешке лежат шарики двух разных цветов (много белых и много черных) какое наименьшее количество шариков надо на ощупь вынуть из мешка, чтобы среди них заведомо оказались два одного цвета.

Обсуждение.

«Кроликами» будут взятые шарики, а «клетками» - черный и белый цвет. Клеток две, поэтому, если «кроликов» хотя бы три, то какие-то два попадут в одну клетку, т. е. будут одноцветными шариками.

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

Задача 2.

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

Обсуждение.

Полуплоскости, на которых прямая ℓ разбивает плоскость ∆ АВС, обозначаем через α и β. «Кролики» - вершины ∆ АВС, полуплоскости α и β – «клетки». Каждый «кролик» попадает в какую-либо «клетку» (т. к. ℓ не проходит ни через одну из точек А, В, С), так как «клетки» - две, а «кроликов» - три, то найдутся два «кролика», попавшие в одну «клетку». Следовательно, найдутся такие две вершины ∆ АВС, которые принадлежат одной полуплоскости. Допустим, точки А и В находятся в одной полуплоскости, т. е. лежат по одну сторону от прямой ℓ. Тогда отрезок АВ не пересечется с прямой ℓ. Итак, в ∆ АВС нашлась сторона, которая не пересекается прямой ℓ.

Задача 3.

Доказать, что из любых 12 натуральных чисел всегда можно выбрать два таких числа, разность которых делится на 11.

Обсуждение.

Пусть «кролики» - это 12 натуральных чисел, «клеток» - должно быть меньше. рассмотрим в их качестве остатки от деления на 11, всего их одиннадцать: 0, 1, 2, , 10.

По принципу Дирихле в какой-нибудь «клетке» будет сидеть не менее двух «кроликов», т. е. найдутся, по крайней мере, два числа, имеющие одинаковые остатки.

Разность этих двух чисел делится на 11. действительно, пусть а = 11m+q и b = 11n+q, тогда a – b = 11 m+q –-(11n+q)=11 (m-n).

А 11(m-n):11

Условия обобщения принципа Дирихле

1. Если в n клетках сидят не более n-1 кроликов, то есть пустая клетка.

Доказательство : (методом от противного) если пустой клетки нет ,то в каждой клетке сидит хотя бы 1 кролик. Тогда кроликов не меньше, чем клеток?! Значит, пустая клетка есть, что и требовалось доказать.

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

Обсуждение. В этой задаче дырки будут «кроликами». Разрежем ковер на 9 ковриков размером 1х1 метр. Так как ковриков- «клеток» 9 штук , а дырок-«кроликов» 8 , то найдется хотя бы одна пустая «клетка», то есть найдется коврик без дырок внутри.

2. Если в n клетках сидят ровно n кроликов, то либо в каждой клетке ровно один кролик, либо есть и пустая клетка , и клетка, в которой не менее двух кроликов.

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

3. Если в n клетках размещены не менее nk+1 кроликов, то найдутся не менее k+1 кроликов, которые посажены в одну клетку.

Доказательство. Действительно, если в каждой клетке сидит не более k кроликов , то во всех клетках сидит не более nk кроликов, а их хотя бы на 1 больше?! Что и требовалось доказать.

4. Если в n клетках размещены не более nk-1 кроликов, то в какой то из клеток сидит не более k-1 кроликов.

Пример. На олимпиаде 10 школьников решили в сумме 35 задач, причем среди них были решившие ровно одну задачу, ровно две и ровно три. Доказать, что кто-то из них решил не менее 5 задач

Обсуждение. Возьмем одного решившего 1 задачу, одного 2 задачи, одного решившего три задачи ( по условию такие были). Эти трое в сумме решили 1+2+3=6 задач. Остается еще 7 школьников, решивших в сумме 29 задач (35-6). Если взять задачи в качестве «кроликов» и школьников в качестве «клеток», то получится утверждение п. 3 при n=7,k=4. Что и требовалось доказать.

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

Обсуждение. Примем за «клетки»- пары учеников, сидящих друг против друга, а за «кроликов»-девушек. Так как девушек больше половины , т. е. больше 8, то найдутся «клетки», в которых будут 2 девушки.

Непрерывный принцип Дирихле.

Если n кроликов съели k кг травы, то какой-то кролик съел не меньше k\n кг травы.

Если k кроликов сидит в n клетках, то найдется клетка ,в которой сидят не меньше ,чем k\n кроликов ,и найдется клетка ,в которой сидят не более, чем k\n кроликов.

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

Если среднее арифметическое нескольких чисел больше a , то хотя бы одно из этих чисел больше a.

Пример. Пятеро программистов получили на всех зарплату в 1750$. Каждый из них хотел купить себе новый компьютер за 360$. Докажите, что кому-то это не светит.

Обсуждение. n=5,S=1750,S\n=1750:5=350$,т. е. зарплата одного из программистов не более 350$. Ему не светит покупка.

Принцип Дирихле встречается в задачах разных разделов математики.

ГЕОМЕТРИЯ

Пример. Треугольники на плоскости. На плоскости выбрано 20 точек, никакие три из которых не лежат на одной прямой. Существует ли треугольник с вершинами в этих точках и хотя бы одним углом меньшим 10о?

Обсуждение. Заметим, что все точки лежат по одну сторону от некоторой прямой АА1. Сумма углов

∟A1АА2, ∟A2АА3,. , ∟A18AA19 меньше 180о, откуда следует, что один из этих 18 углов меньше 10о.

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

Обсуждение. Средние линии треугольника разобьют данный треугольник на 4 правильных треугольника со стороной 0,5. Назовем их «клетками»,а точки- «кролики». По Дирихле две хотя бы точки попадут в один из треугольников. Расстояние между ними будет меньше 0,5,т. к. они не совпадают с вершинами.

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

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

АРИФМЕТИКА

Пример. В классе 30 учеников. Вася сделал в диктанте13 ошибок, а остальные- меньше. Докажите, что по крайней мере 3 ученика сделали ошибок поровну.

Обсуждение. Здесь «кролики»- ученики, «клетки»-число сделанных ошибок. В клетку 0 «посадим» всех, кто не сделал ни одной ошибки, в клетку 1- тех, у кого одна ошибка, в клетку 2- две,и т. д. до клетки 13, куда попал один Вася. Теперь применим принцип Дирихле для доказательства от противного утверждения задачи. Предположим, что никакие 3 ученика не сделали по одинаковому числу ошибок. Т. е. в каждую из «клеток»попало меньше трех школьников. Тогда в «клетках» (без Васиной) не более13х2=26 человек. Добавив Васю, все равно не наберем 30 ребят. Противоречие. Следовательно, по крайней мере трое учеников сделали ошибок поровну.

Пример. В классе 25 учащихся. Из них 20 занимаются английским языком, 17 увлекаются плаванием, 14 посещают математический кружок. Докажите, что в классе найдется хотя бы один ученик, который занимается английским языком, увлекается плаванием и посещает математический кружок.

Обсуждение. Занимаются английским языком и увлекаются плаванием не меньше 20 + 17 – 25 = 12 человек, кроме них - в классе не больше 25 - 12= 13 человек, а посещают математический кружок 14, значит, в классе найдется хотя бы один ученик, который занимается английским языком, увлекается плаванием и посещает математический кружок.

ШАХМАТЫ

Пример. В шахматной партии чёрные сдались после 15-го хода белых. Требуется доказать, что хотя бы одна из чёрных фигур ни разу не покидала своего поля (к фигурам отнесём и пешки).

Обсуждение. Если шахматный ход не рокировка, то передвигается 1 фигура; в случае рокировки - 2.

Чёрные успели сделать 14 ходов, и по правилам игры лишь один из них мог быть рокировкой. Поэтому самое большое количество чёрных фигур, сделавших ходы, -15. Всего же чёрных фигур 16. Значит, по крайней мере какая-то из них не сделала ни одного хода.

ТАБЛИЦЫ

Пример. Числа в таблице. Можно ли в клетках квадратной таблицы 8 х 8 расставить числа 1, -1, 0 так, чтобы все суммы - в каждом столбце, строке и на каждой из двух диагоналей - были различны?

Обсуждение. Сумма из восьми слагаемых со значениями -1,0 или 1, может принимать целые значения от -8 до 8, всего 17 значений. В таблице же 8 строк, 8 столбцов и 2 диагонали - всего 18 сумм. Таким образом, в таблице найдутся две одинаковые суммы.

АЛГЕБРА

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

Обсуждение. Введем систему координат с началом в одном из узлов, осями направленными вдоль сетки, и единичным отрезком , равном стороне клетки. Тогда все точки будут иметь координаты -целые числа. Заметим, что найдутся две точки из пяти у которых одна и та же четность координат х и у. «Кролики»-точки, «клетки»-пары возможных координат : (н,н); (н,ч); (ч,н); (ч,ч). Следовательно, найдутся две искомые точки, а середина образованного отрезка будит иметь целочисленные координаты в силу одинаковой четности концов, т. е будет проходить через узел.

Пример. Дан ряд Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, , Найдется ли среди 100000001 первых членов этого ряда число, оканчивающееся четырьмя нулями?

Обсуждение. Рассмотрим ряд остатков от деления данных чисел на 10000. Остаток, стоящий на n-м месте, обозначим символом an, тогда a1= 1, a2= 1, a6= 8, a10= 55 и т. д. Различных остатков существует 10000, различных пар остатков 100002. Рассмотрим пары a1a2; a2a3; a3a4; a100000001a100000002. По принципу Дирихле из этих 100000001 пары остатков, по крайней мере, две пары совпадают ak=am,ak+1= am+1, где k и m меньше 100000002, k

ПРИНЦИП ДИРИХЛЕ В ТЕОРИИ ЧИСЕЛ.

Если обыкновенную дробь p/q обратить в десятичную, то получится, либо конечная, либо бесконечная периодическая дробь; причем длина периода не больше чем q-1.

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

3. Заключение. ЗАДАЧИ НА ВЫРОСТ

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

   a) Если на отрезке длиной 1 расположено несколько отрезков, сумма длин которых больше 1, то, по крайней мере, два из них имеют общую точку.

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

Отдельные задачи все еще остаются для меня «задачками на вырост», поскольку в силу своего возраста я пока не могу с ними справиться. Но я понял, что принцип Дирихле – один из основных способов решения олимпиадных задач и я про него никогда не забуду.

Задача.

В конференции участвовало 1000 учеников, докажите, что хотя бы у двух из них совпадает первая и последняя буква фамилии.

Будем считать, что фамилии не могут начинаться с букв Ъ, Ь, Ы, тогда фамилии будут начинаться с 30 букв, а оканчиваться 33 буквами, т. е. всевозможных вариантов 990, а это меньше 1000. Следовательно, найдутся такие участники конференции, у которых первая и последняя буква фамилии совпадает.