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

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



НазваниеПринцип Дирихле
Дата конвертации14.12.2012
Размер152.31 Kb.
ТипДокументы

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

При решении многих задач используется логический метод рассуждения — "от противного". Здесь мы рассмотрим одну из его форм — принцип Дирихле. Этот принцип утверждает, что если множество из n элементов разбито на m непересекающихся частей, не имеющих общих элементов, где n > m то, по крайней мере, в одной части будет более одного элемента. Принцип назван в честь немецкого математика Дирихле (1805-1859), который успешно применял его к доказательству арифметических утверждений.

Цель этой статьи — познакомить школьника с некоторыми задачами олимпиадного характера, при решении которых используют принцип Дирихле. Знакомство учащихся с данным методом решения задач можно начинать с 5-6 класса.

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


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


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

Другая формулировка “ принципа Дирихле“: если n + 1 предмет поместить в n мест, то обязательно хотя бы в одном месте окажутся хотя бы два предмета.

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

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


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

Решение. Достанем из мешка 3 шарика. Если бы среди этих шариков было не более одного шарика каждого из двух цветов, то всего было бы не более двух шаров – это очевидно, и противоречит тому, что мы достали три шарика (снова же, обратите внимание – использован метод от противного). С другой стороны понятно, что двух шариков может и не хватить. Ясно, что «кроликами» здесь являются шарики, а «клетками» - цвета: черный и белый.

Пример 2. В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.

Решение.
Перед нами миллион «кроликов»-елок и, увы, всего лишь 600001 «клетка» с номерами от 0 до 600000. Каждый «кролик»-елка сажается нами в «клетку» с номером, равным количеству иголок на этой елке. Так как «кроликов» гораздо больше, чем «клеток», то в какой-то «клетке» сидит по крайней мере два «кролика» – если бы в каждой сидело не более одного, то всего «кроликов»-елок было бы не более 600001 штук. Но ведь, если два «кролика»-елки сидят в одной «клетке», то количество иголок у них одинаково.

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

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

Пример 3. В некотором городе живет более 5 миллионов человек. Докажите, что у каких-то двух из них одинаковое число волос на голове, если известно, что у любого человека на голове менее миллиона волос.

Решение. Постройте миллион «клеток» с номерами от 0 до 999999 и рассадите там людей, поместив каждого жителя в «клетку», номер которой равен количеству волос на его голове.

Пример 4. Докажите, что в любой футбольной команде есть два игрока, которые родились в один и тот же день недели.

Решение. Кролики – игроки команды, клетки – дни недели. Игроков в футбольной команде – 11, а дней недели – 7. Если рассадить кроликов в клетки, то окажется, что 4 кролика будут сидеть в клетке не в одиночестве.


^ Обобщение принципа Дирихле

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

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

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

Решение. 25 ящиков-«кроликов» рассадим по 3 «клеткам»-сортам. Так как 25 = 3 ∙ 8 + 1, то применим обобщенный принцип Дирихле (для N = 3, k = 8) и получим, что в какой-то «клетке»-сорте не менее 9 ящиков.

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

 Решение. Здесь "кролики" – ученики, "клетки" – число сделанных ошибок. В клетку 0 "посадим" всех, кто не сделал ни одной ошибки, в клетку 1- тех, у кого 1 ошибка... и так до клетки 13, куда попал один Паша. Теперь применим принцип Дирихле.

Докажем утверждение задачи от противного. Предположим, никакие три ученика не сделали по одинаковому числу ошибок, то есть в каждую из "клеток" 0,1,...,12 попало меньше трех школьников. Тогда в каждой из них два человека или меньше, а всего в этих 13 клетках не более 2*13=26 человек. Добавив Пашу, все равно не наберем 30 ребят. Противоречие. Следовательно, утверждение задачи верно, по крайней мере, трое учеников сделали поровну ошибок.

Пример 7. Дано 8 различных натуральных чисел, не больших 15. Докажите, что среди их положительных попарных разностей есть три одинаковых.

Решение. Различных разностей может быть 14 – от 1 до 14 – это те 14 «клеток», в которые мы будем сажать «кроликов». Кто же будет нашими «кроликами»? Ими, конечно, должны быть разности между парами данных нам натуральных чисел. Однако имеется 28 пар и их можно рассадить по 14 «клеткам» так, что в каждой «клетке» будет сидеть ровно два «кролика» (и значит, в каждой меньше трех). Здесь надо использовать дополнительное соображение: в «клетке» с номером 14 может сидеть не более одного «кролика», ведь число 14 можно записать как разность двух натуральных чисел, не превосходящих 15, лишь одним способом: 14 = 15 – 1. Значит, в оставшихся 13 «клетках» сидят не менее 27 «кроликов», и применение обобщенного принципа Дирихле дает нам желаемый результат.

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

Решение. Разобьём данный квадрат на 25 одинаковых квадратиков ("клеток") со стороной 1/5. В один из них попадёт не менее трёх точек ("зайцев"). Окружность, описанная около квадратика со стороной 1/5, имеет радиус , поэтому этот квадратик можно накрыть кругом радиуса 1/7.


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

Возможна следующая переформулировка принципа Дирихле:

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

При делении с остатком на p может встретиться конечное число различных остатков: 0, 1, 2, . . . , p-1. Они то и играют здесь роль "клеток", а сами целые числа являются "зайцами". Так как чисел ("зайцев") больше, чем остатков ("клеток"), то хотя бы два числа "сидят в одной клетке", т.е. имеют одинаковые остатки при делении на p. Рассмотрим классические примеры.

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

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

Пример 10. Доказать, что если имеется 100 целых чисел x1, x2, . . . , x100, то из них можно выбрать несколько чисел (может быть, одно), сумма которых делится на 100.

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

,

,

,

…………………



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



делится на 100, и поэтому сумма xn + 1+. . .+ xm является искомой.


^ Принцип Дирихле для длин и площадей


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

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

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

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

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

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

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

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

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

Решение. Пусть S1, S2, . . . , S100 - площади данных фигур, а , …,  - площади фигур, дополняющих их до квадрата. Понятно, что . По условию S1+S2+. . .+S100 > 99S, поэтому

+ + … + = (S- S1)+ (S- S2)+. . .+ (S- S100) = 100S-(S1+ S2+. . .+ S100) < 100S-99S = S.

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

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

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


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


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

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

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

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

или в терминах "зайцев":

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

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

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

Понятно, что если рассматривать только углы между соседними лучами, то всего получится N углов (см. рисунок). В сумме они составляют полный угол, равный 360°. Следовательно,




по непрерывному принципу Дирихле градусная мера одного из этих углов не менее 360°/N (иначе их сумма будет меньше 360°).

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

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

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

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

Решение. Пусть A - наименьшее из выписанных на доске чисел, а B - наибольшее. Покажем, что B-A =7.

Запишем числа в порядке возрастания (заметим, что никакие два числа не равны):



(здесь x1 = A, x64 = B).

Тогда





Допустим теперь, что утверждение задачи неверно, т.е. в любой паре соседних клеток числа отличаются меньше чем на 1/2. Рассмотрим две клетки, в которых записаны числа A и B. Понятно, что, переходя из клетки в клетку, можно попасть из клетки A в клетку B, сделав не более 14 переходов. Самый худший случай, когда нужно сделать ровно 14 переходов, показан на рисунке (A, B - противоположные клетки). По предположению приращение на каждом переходе меньше 1/2. Поэтому B - A < 14·(1/2) = 7. Противоречие.


Упражнения


1. (5-6 класс) В классе 15 учеников. Докажите, что найдутся как минимум 2 ученика, отмечающие дни рождения в один месяц.

2. (5-6 класс) Дано 12 целых чисел. Докажите, что из них можно выбрать два числа, разность которых делится на 11.

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

4. (5-6 класс) В классе 35 учеников. Можно ли утверждать, что среди них найдутся хотя бы два ученика, фамилии которых начинаются с одной буквы?

5. (5-6 класс) На дискотеку в студенческое общежитие, в котором 42 комнаты, пришло 36 гостей. Докажите, что найдется комната, в которую не пришёл ни один гость.

6. (5-6 класс) Шесть школьников съели семь конфет. Докажите, что один из них съел не менее двух конфет.

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

8. (7-8 класс) В классе 26 учеников, из них более половины – мальчики. Докажите, что какие-то 2 мальчика сидят за одним столом, если в классе 13 столов.

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

10. (7-8 класс) Можно ли окрасить клетки таблицы так, чтобы во всех строках и во всех столбцах таблицы число закрашенных клеток было различно?

11. (7-8 класс) В городе N более 201 улицы. На каждой улице не менее 52 и не более 252 домов. Докажите, что найдутся, по меньшей мере, две улицы с одинаковым числом домов.

12. (7-8 класс) 10 друзей послали друг другу праздничные открытки. Каждый послал 5 открыток. Докажите, что двое послали открытки друг другу.

13. (7-8 класс) В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка - точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.

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

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

16. (7-8 класс) Докажите, что из любых трех натуральных чисел можно найти два, сумма которых делится на 2.

17. (7-8 класс)Винни-Пух, Сова, Кролик и Пятачок вместе съели 70 бананов, причем каждый из них съел хотя бы один банан. Винни-Пух съел больше всех, Сова и Кролик вместе съели 45 бананов. Сколько бананов съел Пятачок?

18. (7-8 класс) Докажите, что в любой копании из пяти человек двое имеют одинаковое число знакомых.

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

20. (7-8 класс) Если 30 человек рассадить в зале кинотеатра, то хотя бы в одном ряду окажется не менее двух человек. Если в зале рассадить 26 человек, то по крайней мере 3 ряда окажутся пустыми. Сколько рядов в зале?

21. (7-8 класс) 15 мальчиков собрали 100 орехов. Докажите, что какие-то два из них собрали одинаковое число орехов.

22. (8-9 класс) В розыгрыше кубка по футболу (в один круг) участвуют 30 команд. Доказать, что в любой момент найдутся две команды, сыгравшие одинаковое число игр.

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

24. (9-11 класс) На плоскости нарисовали 5 прямых. Докажите, что угол между какими-то двумя из них не больше 36°. (Если какие-нибудь прямые параллельны, считайте, что угол между ними равен 0°).

25. (8-11 класс) Докажите, что среди любых 6 человек либо трое попарно знакомых, либо трое попарно незнакомых.

26. (10-11 класс) Шесть кругов имеют общую внутреннюю точку. Докажите, что центр одного из них лежит внутри другого.

27. (10-11 класс) Первоклассник Петя знает только цифру 1. Доказать, что он может написать число, делящееся на 1997.

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


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

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

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

[3] Д. X. Муштари. Подготовка к математическим олимпиадам: задачи, темы, методы. Казанский ун-т, 1990.

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

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

[6] А. А. Леман. Сборник задач московских математических олимпиад. Под ред. В.Г. Болтянского. М.: Просвещение, 1965.

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






Похожие:

Принцип Дирихле icon12 Принцип Дирихле 30 ноября-2декабря Примеры
Докажите, что среди 26 учеников 7«м» класса найдутся трое, отмечающие день рождения в один и тот же месяц
Принцип Дирихле icon12а Принцип Дирихле (дополнительно) 6 декабря Это дополнительные задачи – их можно сдавать устно наряду с основными
После начала переговоров оказалось, что ни один из дипломатов не сидит против своей таблички. Докажите, что можно повернуть стол...
Принцип Дирихле icon№ Классификация электронных приборов
Назначение, устройство, принцип действия, принцип включения, основное свойство, виды, уго тиристоров
Принцип Дирихле iconГлавные принципы жизни принцип зеркала
...
Принцип Дирихле iconЗанятие 3 10-й класс
Закономерности заполнения электронной оболочки атома: принцип Паули, принцип наименьшей энергии, правило Клечковского, правило Гунда...
Принцип Дирихле iconПринцип ассоциативной доминанты в творчестве Ю. И. Ковалева «Стихи пишутся затем, чтобы сказать больше, чем можно в прозе»
Целью нашей работы является попытка проследить как раскрывается принцип ассоциативной доминанты на примере творчества Ю
Принцип Дирихле iconДетство там, где ему рады!
Здесь важен не принцип параллельности, а принцип взаимопроникновения двух социальных институтов Важнейшим условием преемственности...
Принцип Дирихле iconЗдоровьесберегающие технологии на уроках Учитель русского языка и литературы Митрофанова И. Н
Наглядность. Принцип непрерывности физического воспитания и образования личности на всех этапах жизнедеятельности. Принцип дифференцированного...
Принцип Дирихле iconПринципы здоровьесберегающей педагогики Принцип не нанесения вреда
Принцип не нанесения вреда. «No nocere!» одинаково первостепенно и для медиков, и для учителей, и для родителей
Принцип Дирихле iconОбразовательная программа для организации учебно-воспитательного процесса. Руководство
Свою управленческую деятельность администрация школы строит на следующих принципах организации совместной деятельности: принцип целевой...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib.podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов