Принцип Дирихле и его  применение  при решении задач.

Слайд 1

Слайд 2

Принцип назван в честь немецкого математика Дирихле (1805-1859), который успешно применял его к доказательству арифметических утверждений.

Слайд 3

Самая популярная формулировка принципа Дирихле звучит так: " Если в n клетках сидит n +1 или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два зайца". Заметим, что в роли зайцев могут выступать различные предметы и математические объекты - числа, отрезки, места в таблице и т. д.

Слайд 4

Примеры задач: 1. Дано 12 целых чисел. Докажите, что из них можно выбрать 2, разность которых делится на 11. Решение: примем числа за «зайцев», их 12,значит клеток должно быть меньше. Пусть «клетки » - остатки от деления целого числа на 11.Всего таких» клеток» будет 11: 0,1,2, 3,4,5,6,7,8,9,10.Тогда по принципу Дирихле найдется «клетка», в которой будут сидеть не менее чем 2 «зайца», то есть найдутся 2 целых числа с одним остатком. А разность 2 чисел с одинаковым остатком от деления на 11, будет делиться на 11: =(11m + q) – (11n + q) = 11(m – n).

Слайд 5

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

Слайд 6

2. В ковре размером 4х4 метра моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1х1 метр, не содержащий внутри себя дырок. (Дырки можно считать точечными). Решение: Разрежем ковер на 16 ковриков размером 1х1 метр. Так как ковриков- «клеток» - 16, а дырок –«зайцев»- 15, то найдется хотя бы одна «клетка», в которой не будет «зайцев», то есть найдется коврик без дырок внутри. Здесь применяют вторую формулировку принципа Дирихле.

Слайд 7

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

Слайд 8

3. В классе 27 учеников. Найдется ли месяц, в котором отмечают свои дни рождения не меньше, чем три ученика этого класса. Решение : В году 12 месяцев. Обозначим их за «клетки», а учеников за «Зайцев ». Так как 27 ≥ 12•2 + 1, то по обобщенному принципу Дирихле найдется «клетка», в которой сидят не менее 3 «Зайцев», то есть найдется месяц, в котором дни рождения празднуют не менее 3 учеников

Слайд 9

4.В бригаде 7 человек и их суммарный возраст – 332.Доказать, что из них можно выбрать 3 человека, сумма возрастов которых не меньше 142 лет. Решение 1 . Выберем трех старших членов бригады. Если им вместе 142 года, то хотя бы одному из них больше 47 лет. Если самому младшему из троих больше 47 лет, то им троим больше 142 лет. Пусть самому младшему из троих 47 лет или меньше, им троим вместе менее 142 лет. Тогда на долю остальных четверых приходится более 320 – 142 = 190 лет. Разделим 190 на 4 с остатком: 190 =4•47 + 2. Тогда по принципу Дирихле одному из четверых больше 47 лет. Это противоречит выбору троих самых старших в бригаде. Решение 2 . Рассмотрим все возможные тройки рабочих бригады. Всего таких троек = = 35. Сумма их суммарных возрастов равна 332∙35∙ = 4980. Значит по принципу Дирихле есть тройка, суммарный возраст в которой не меньше, чем 4980 : 35, что больше 142. Решение 3 . Средний возраст трех самых старших не меньше среднего возраста по бригаде, который равен . Поэтому сумма их возрастов по меньшей мере года.