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

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

Дирихле Петер Густав Лежен (13.02.1805 Дюрен – 5.05.1859 Гетенген), немецкий математик 1831-1855 гг. профессор Берлинского, с 1855 г. Гетенгенского университетов. Основал труды в области теории чисел и математического анализа. Дирихле доказал теорему о существовании бесконечно большого числа простых чисел во всякой арифметической прогрессии из целых чисел первый член и разность которой – числа взаимно простые. В области математического анализа Дирихле впервые точно сформулировал и исследовал понятие условной сходимости ряда, дал строгое доказательство возможности разложения в ряд Фурье функции, имеющей конечное число максимумов и минимумов. Работы Дирихле посвящены механике и математической физики.

Принцип Дирихле выражает соотношение между двумя множествами. Существует несколько формулировок данного принципа.

«Если в n клетках сидят m зайцев, причём m>n, то хотя бы в одной клетке сидят, по крайней мере, два зайца».

«Пусть в n клетках сидят m зайцев, причём n>m. То найдётся хотя бы одна пустая клетка».

«Если в n клетках больше nk зайцев, то хотя бы в одной клетке сидит больше k зайцев».

«Если в n клетках сидят m зайцев, то найдётся клетка, в которой сидят не меньше, чем m/n зайцев, и найдётся клетка, в которой сидят не больше, чем m/n зайцев».

«Если m зайцев съели n килограммов травы, то какой-то заяц съел не менее m/n килограммов травы и какой-то заяц съел не больше m/n килограммов (а если кто-то съел больше среднего, то кто-то съел меньше среднего)» (непрерывный принцип).

«Если в n клетках сидят m зайцев и m ³ kn + 1, то в какой-то из клеток сидят, по крайней мере, k + 1 заяц» (обобщённый принцип).

Применяя метод Дирихле, надо:

1) определить, что удобно в задаче принять за «клетки», а что – за «зайцев»;

2) получить «клетки» (чаще всего «клеток» меньше (больше), чем «зайцев» на одну);

3) выбрать для решения требуемую формулировку принципа Дирихле.

Некоторые задачи решаются с использованием формулировок, аналогичных принципу Дирихле:

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

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

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

4) если сумма площадей нескольких фигур меньше S, то ими нельзя покрыть фигуру площади S;

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

ОБРАЗЦЫ РЕШЕНИЯ ЗАДАЧ

ЗАДАЧА 1. В классе 30 человек. Саша Иванов в диктанте сделал 13 ошибок, а остальные – меньше. Докажите что по крайней мере 3 ученика сделали ошибок поровну (может быть по 0 ошибок.)

Доказательство. Здесь “зайцы” – ученики, “клетки” – число сделанных ошибок. В клетку 0 “посадим” всех, кто сделал ни одной ошибки, в клетку 1 – тех, у кого одна ошибка, в клетку 2 – две … и так до клетки 13, куда попал один Саша Иванов.

Теперь применим принцип Дирихле. Докажем утверждение задачи от противного. Предположим, никакие три ученика не сделали по одинаковому числу ошибок, то есть в каждую из “клеток”: 0, 1, 2, …, 12 попало меньше 3школьников. Тогда в каждой из них два человека или меньше, а всего в этих 13 клетках не более 2×13=26 человек. Добавив Сашу Иванова, все ровно не наберем 30 ребят. Противоречие. Значит, наше предположение неверно и, по крайней мере, трое учеников сделали поровну ошибок.

ЗАДАЧА 2. В Москве живет более 7,8 млн. жителей, на голове у каждого не более 100 тыс. волос. Докажите что в Москве есть по крайней мере 70 человек с одинаковым числом волос на голове.

Доказательство. Построим 100001 “клетку” для тех, у кого на голове нет волос вообще (0 волос), для тех, у кого на голове ровно 1 волос, ровно 2 волоса, …, ровно 100000 волос.

Распределим население города по “клеткам” (мысленно, разумеется). Если бы в каждой клетке находилось не более 70 человек, то всего в городе было бы не более 70×100001=700070 человек.

Таким образом, утверждение задачи можно усилить – есть, по крайней мере, 78 человек с одинаковым числом волос на голове.

ЗАДАЧА 3. На земле живет более 3,6 млрд. человек. Известно, что среди не более 1% людей старше 100 лет. Докажите, что найдется два человека, которые родились в одну и ту же секунду.

Доказательство. Оценим сначала число секунд за 100 лет. В соответствии с ныне действующим календарем за 100 лет бывает 24 високосных года и 76 простых лет (год, оканчивающийся на 00, считается простым.) Впрочем, для наших целей достаточно знать, что в каждом из них менее чем 370 дней. А за 100 лет пройдет меньше чем 37000 дней. В минуте 60 с; в часе 60 мин, значит, в часе 60×60=3600 с. В сутках 24 часа или 3600×24=86400 с. Значит, в сутках меньше 90000 с; а за 100 лет пройдет меньше 90000×37000=3330000000 с, то есть 3,33 млрд. с. Из условия следует, что не старше 100 лет, по крайней мере, 3,6×0,99=3,564 млрд. людей. Для завершения доказательства следует сослаться на принцип Дирихле.

ЗАДАЧА 4. Если класс из 30 человек рассадить в зале кинотеатра, то в любом случае хотя бы в одном ряду окажется не менее двух одноклассников. Если то же самое проделать с классом из 26 человек, то, по крайней мере, три ряда окажутся пустыми. Сколько рядов в зале?

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

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

Значит, в кинотеатре 29 рядов. Очевидно, что в этом случае оба условия задачи выполнены.

ЗАДАЧА 5. Петя написал на гранях кубика натуральные числа от 1 до 6. Вася кубика не видел, но утверждает, что:

а) у этого кубика есть две соседние грани, на которых написаны соседние числа;

б) таких пар соседних граней у кубика не меньше двух.

Прав ли он в обоих случаях? Почему?

Решение. В наборе натуральных чисел от 1 до 6 можно найти пять пар соседних чисел: 1 и 2, 2 и 3, 3 и 4, 4 и 5, 5 и 6. Каждая такая пара может быть написана либо на двух соседних гранях кубика, либо на двух противоположных. Но пар противоположных граней у кубика всего три. Поэтому их могут занимать не более трех пар соседних чисел. Значит, по крайней мере, две такие пары занимают соседние грани. Следовательно, можно утверждать, что Вася прав в обоих случаях.

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

Доказательство. Рассмотрим двоих учеников класса, которые не дружат между собой. (Если таких учеников нет, то все ученики класса дружат между собой, значит, у каждого ученика имеются 24 друга, и задача решена.) Пусть этими двумя будут Вася и Петя. Тогда из оставшихся 23 учеников каждый дружит либо с Васей, либо с Петей. Действительно, если бы кто-то (скажем Коля) не дружил бы ни с Васей, ни с Петей, то мы имели бы троих учеников, среди которых не было бы друзей. Теперь если предположить, что и Вася, и Петя имеют не более 11 друзей, то всего в классе, кроме этих двоих было бы не больше 22 человек. Полученное противоречие показывает, что один из школьников имеет не менее 12 друзей.

ЗАДАЧА 7. Петя разрезал прямоугольный лист бумаги по прямой. Затем он разрезал по прямой один из получившихся кусков. Затем он проделал то же самое с одним из трех получившихся кусков и так далее. Докажите, что после достаточного количества разрезаний можно будет выбрать среди получившихся кусков 100 многоугольников с одинаковым числом вершин.

Доказательство. Обозначим через S_n суммарное количество сторон всех получившихся многоугольников после (n - 1)-го разделения (общее количество многоугольников при этом будет n). Докажем, что после 297 разрезов у Пети будет либо не меньше 100 треугольников, либо не меньше 100 четырехугольников. Предположим противное, тогда можно получить оценку снизу S₂₉₈≥99×3+99×4+100×5=298×4+1, поскольку среди 298 многоугольников не более 99 треугольников, не более 99 четырехугольников, а остальные многоугольники содержат не менее 5 сторон. С другой стороны, при каждом разрезании количество сторон увеличивается не более чем на 4, поэтому S_n≤298×4. Полученное противоречие доказывает утверждение.

ЗАДАЧА 8. Какое наибольшее число королей можно расставить на шахматной доске так, чтобы они не били друг друга.

Доказательство. На шахматной доске можно расположить 16 королей, как показано на рис. 1.

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

Примем эти квадраты за “ящики”, а все королей - за “предметы”. По принципу Дирихле, найдется “ящик” с двумя “предметами”, то есть найдется квадрат, на полях которого стоят два короля. Очевидно, что на одном квадрате нельзя разместить двух королей так, чтобы они не били друг друга.

Получим противоречие, значит, наше предположение неверно, и на доске можно разместить не более 16 королей.

Ответ: 16 королей.

ЗАДАЧА 9. Восемь футбольных команд провели турнир, (каждая сыграла с каждой один раз). При этом не было "ничьих". Докажите, что можно выделить такие четыре команды A, B, C, D. что A выиграла у B, C и D; B выиграла у C и D; C выиграла у D.

Доказательство. Так как, по условию, в турнире не было "ничьих", то каждый из матчей (их было C₈²==28) заканчивался чьей-либо победой. Распределим все k×n+1=28 побед между восемью командами, приняв их за "предметы", а k=8 команд – за "ящики".

По принципу Дирихле, найдется “ящик” в котором не меньше, чем n+1=3+1=4 “предмета”. Иначе говоря, среди восьми команд найдутся хотя бы одна команда A, которая выиграла у четырех других команд, то есть имеет не менее четырех побед. Эти четыре команды между собой провели C₄²==6 матчей, то есть было 6 побед. Приняв 4 команды за “ящики”, а 6 побед за “предметы”, по принципу Дирихле получим, что найдется команда B, одержавшая, по меньшей мере, 2 победы над двумя командами C и D из четырех рассматриваемых.

Пусть в матче между командами C и D победила C. Тогда получим:

A победила B, C и D.

B победила C и D.

C победила D.

Итак, мы нашли четыре команды A, B, C, D, удовлетворяющие условию задачи.

ЗАДАЧА 10. Выберем n человек. Докажите, что, по крайней мере, двое из них имеют одинаковое число знакомых среди выбранных.

Доказательство. Возможное число знакомых у каждого: 1, 2, 3,…, n-1. Возьмем n “ящиков”. Всех людей примем за “предметы”. Пусть номер каждого “ящика” соответствует числу знакомых у людей – “предметов”, содержащихся в них.

Рассмотрим два случая.

а) Людей, не имеющих ни одного знакомого, нет. В этом случае “ящик” N 0 – пуст. Тогда расположим n человек в остальных n-1 “ящиках”.

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

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

ЗАДАЧА 11. Докажите, что среди 82 кубиков, каждый из которых выкрашен в определенный цвет, всегда можно выбрать 10 кубиков таких, что-либо все они выкрашены в разные цвета, либо все одного цвета.

Доказательство. 1. Примем за “ящики” возможные цвета кубиков, а за “предметы” – сами эти кубики.

Разложим кубики – “предметы” по “ящикам”. Так, чтобы в одном “ящике” лежали кубики одного цвета, а в разных – разного.

2. Рассмотрим два случая.

а) Если “ящиков” с кубиками больше 9 (не меньше 10), взяв по одному кубику из каждого “ящика”, получим не меньше 10 кубиков разного цвета.

б) Если “ящиков” с кубиками не больше 9, то разложим в эти “ящики” 82 кубика – “предмета”. По принципу Дирихле, в самом наихудшем варианте (когда “ящиков” 9) найдется “ящик”, в котором не меньше чем n+1=9+1=10 кубиков, одинакового окрашенных. Итак, в обоих случаях найдутся 10 кубиков, удовлетворяющих условию задачи.

В СЛЕДУЮЩИХ ЗАДАЧАХ НА ПРИНЦИП ДИРИХЛЕ ИСПОЛЬЗУЕТСЯ ИНФОРМАЦИЯ О ТОМ, ЧТО В НЕКОТОРЫХ «ЯЩИКАХ» ЧИСЛО «ПРЕДМЕТОВ» МОЖНО ЗАРАНЕЕ ОГРАНИЧИТЬ ПОДХОДЯЩЕЙ КОНСТАНТОЙ.

ЗАДАЧА 12. Восемь целых чисел подчинены условию:

0< a₁ < a₂ < a_{3 …} < a₈ < 16.

Докажите, что всегда существует такое число k, что из данных восьми чисел можно выбрать не менее трех, связанных соотношением: а_i − а_j = k.

Доказательство. 1. Из условия видно, что числа а₁, а₂, …, а₈ могут быть равными 1, 2, 3, …, 15. Тогда возможные разности двух чисел а_i и а_j: 1, 2, 3, …, 14. причем ясно, что разность 14 может быть получена лишь одним способом (15-1=14).

2. Примем за “ящики” возможные разности чисел (их 14). Пусть номер каждого “ящика” соответствует значению разности пар чисел, содержащихся в нем. “Предметы” – все пары чисел из а₁; a₂; a₃; …; a₈. Их 28 C₈²=. Разложим “предметы” в “ящики”.

С учетом, что в “ящике” № 14 не более одного “предмета”. Значит, на остальные k=13 “ящиков” приходится не менее k×n=27 “предметов” – пар чисел. Следовательно, по принципу Дирихле, из этих 13 “ящиков” найдется, по крайней мере, один “ящик”, содержащий не менее трех “предметов” (n=2; n+1=3). Номер этого “ящика” соответствует числу k, так как этот номер – значение разности чисел а_i и а_j (их три пары), находящихся в этом “ящике”.

3. Итак, мы доказали, что найдется число k такое, что из чисел а₁; …;а₈ найдутся не менее трех пар, связанных соотношением: а_i − а_j = k.

ЗАДАЧА 13. По краю круглого стола равномерно расставлены таблички с фамилиями дипломатов, участвующих в совещании. После начала совещания оказалось, что ни один из дипломатов не сидит против своей таблички. Можно ли повернуть стол так, чтобы, по крайней мере, два дипломата сидели против своих табличек?

Решение. 1. Пусть за столом сидят n дипломатов. Рассмотрим возможные положения стола по отношению к дипломатам. Число этих положений, очевидно, равно n. Примем их за “ящики”.

2. За “предметы” примем дипломатов, каждому из которых удовлетворяет лишь одно положение стола. Всего “предметов” n. Разместим “предметы” в “ящики”. С учетом, что в одном из положений – “ящиков” нет ни одного “предмета” (то есть, нет ни одного дипломата, которому удовлетворяет начальное положение стола). Следовательно, на остальные n-1 “ящиков” приходится n “предметов”. Отсюда, по принципу Дирихле, найдется “ящик”, в котором не менее двух “предметов”, то есть найдется положение стола, удовлетворяющее не менее чем двум дипломатам. Значит, можно повернуть стол так, чтобы два дипломата оказались напротив своих табличек.

ЗАДАЧА 14. Даны n+1 натуральных различных чисел, меньших 2n. Докажите, что из них можно выбрать три такие числа, что одно из них равна сумме двух других.

Доказательство. Рассмотрим наибольшее из n+1 выбранных чисел. По условию, оно меньше, чем 2n. Рассмотрим “наихудший” вариант, когда это число принимает наибольшее значение, то есть равно 2n−1. Все предыдущие 2n−2 чисел ряда разобьем на n−1 “ящиков” следующим образом:

I II III · · · · · · n−1

1; 2; 3; · · · · · · n−1

2n-2 2n-3 2n-4 · · · · · · n

Сумма чисел в каждом “ящике” равна 2n-1, то есть, равна наибольшему из n+1 выбр. чисел.

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

Во всех остальных вариантах (то есть, когда наибольшее из n+1 чисел меньше, чем 2n+1) “ящиков” будет меньше, чем n-1, а “предметов” – по-прежнему n. Значит, в этом случае тем более найдутся два числа, сумма которых равна третьему – наибольшему числу.

ЗАДАЧА 15. На шахматной доске расставлены числа от 1 до 64. Докажите, что при любой их расстановке найдутся две соседние клетки (имеющие общую сторону) такие, что разность между стоящими в них числами будет больше 4.

Доказательство. Поместим числа от 1 и 64 в противоположные клетки диагонали. Их соединяет линия, проходящая через 15 попарно соседних клеток, то есть содержащая 14 переходов. Допустим, что на каждом переходе приращение не превышает 4. Тогда общее не превышает 4×14=56<63. Но это противоречит условию, значит наше допущение не верно.

ЗАДАЧА 16. 106 т строительных материалов упаковано в ящиках; масса каждого не превышает 6 т. Грузовой лифт перевозит их на крышу небоскреба. Если масса груза более 25 т, лифт автоматически отключается. Какое количество рейсов лифта достаточно для перевозки груза?

Решение. В каждый из рейсов можно загрузить не менее 19 т. Поэтому достаточно 106:19, то есть 6 рейсов. 5 рейсов может оказаться недостаточно. Например, если 21 одинаковый ящик попытаться перевезти в 5 рейсов, то в одном из рейсов 5 ящиков общей массой 106×5/21>5 т.

ЗАДАЧА 17. Требуется доказать, что существует хотя бы одно иррациональное число – такое действительное число, которое нельзя представить в виде отношения m/n, двух натуральных чисел.

Доказательство. Такое число – это . В самом деле, по теореме Пифагора, есть диагональ квадрата со стороной 1. Если бы оно выражалось отношением натуральных чисел m и n, то отрезок длинной 1/n укладывался бы n раз в стороне единичного квадрата, и m раз в его диагонали, а значит, был бы их общей мерой, что невозможно.

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

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

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

ЗАДАЧА 19. На длинной прямолинейной дороге с равными интервалами вырыты небольшие поперечные канавки (рис. 5). Расстояние между центрами каждых двух соседних канавок равно √2 метров. Доказать, что какими бы узенькими эти канавки ни были сделаны, человек, шагающий по дороге и имеющий длину шага 1 метр, рано или поздно попадет в одну из канавок.

рис. 5

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