Принцип Дирихле. Решение олимпиадных задач. Первое занятие
олимпиадные задания по алгебре (6 класс) по теме

Занятие № 3.

Лекция.

ТЕМА :«Принцип Дирихле».

Принцип Дирихле выражает соотношение между двумя множествами. Существует несколько формулировок этого принципа. Самая популярная следующая: « Если в n клетках сидит  m зайцев, причем m>n, то хотя бы в одной клерке сидят, по крайней  мере два зайца». Принцип Дирихле легко доказывается методом доказательства от противного. Некоторые задачи на применение данного принципа также можно решить, используя метод доказательства от противного, но не все.

На первый  взгляд непонятно, почему это совершенно очевидное предложение, тем не менее, является мощным математическим методом решения задач, причем самых разнообразных. Дело в том, что в каждой конкретной задаче нелегко понять, что же здесь выступает в роли «зайцев», а что – в роли «клеток». И почему надо, чтобы «зайцев» было больше, чем «клеток». Выбор «зайцев» и «клеток» часто неочевиден. Далеко не всегда по формулировке задачи можно определить, что следует применить принцип Дирихле. Главное же достоинство этого метода решения состоит в том, что он дает неконструктивное решение (т.е. мы знаем, что такие клетки есть, но где именно они находятся, часто указать не можем); попытка же дать конструктивное доказательство приводит к большим трудностям.

Рассмотрим другие формулировки принципа Дирихле :

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

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

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

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

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

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

Рассмотрим примеры задач, решаемых данным методом.

1. «Клетки и кролики»

Задача №1. В классе 30 человек. В диктанте Витя Медведев сделал 13 ошибок, а остальные – меньше. Докажите, что по крайней мере три ученика сделали ошибок поровну (может быть по  ошибок)

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

Задача №2.  Пусть в классе 41 человек, а не 30. Докажите, что найдутся четверо, сделавшие одинаковое число ошибок. (стальные условия – как в предыдущей задаче.)

Док-во: Здесь надо рассадить 40 человек по 13 «клеткам». 40 =  13*3+1. Значит, найдется «клетка», в которой сидят четыре человека.

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

Задача №3  В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?

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

Ответ: Можно

3. «Принцип Дирихле и делимость»

Задача № 4 Верно ли, что из шести любых целых чисел найдутся два числа, разность которых делится на 5?

Решение: Шесть чисел – зайцы, клетки – остатки от деления чисел на 5: 0, 1, 2, 3, 4, значит, найдется клетка, в которой будут сидеть 2 зайца – числа с равными остатками от деления их на 5. Тогда и разность этих чисел делится на 5.

(26:5 = 5*5+1; 16:5=3*5+1;        26 – 16 = 10, 105)

4. Точки многоугольники и принцип Дирихле

Задача №5 На шахматной доске размером 8х8 Вася расставил 14 фигур. Докажите, что найдется квадрат размером 2х2, в котором не будет фигур. (Фигуры размещаются внутри клеток размером 1х1)

Решение: Разобьем квадрат 8х8 следующим образом

Тогда получаем 16 «клеток» и 14 «зайцев» - фигур. Так как 16>14, то найдется как минимум одна клетка, которая будет пустой.

5. «Наверняка»

Задача №6 В мешке лежат 10 белых и 10 черных шаров. Они тщательно перемешаны и неразличимы на ощупь. Какое наименьшее число шаров нужно вынуть из мешка вслепую, чтобы среди них наверняка оказались два шара 1) одного цвета,  2) разного цвета, 3) белого цвета?

Решение: 1) Цвета шаров обозначим за «клетки» (их две), значит «зайцев» надо больше. Достанем из мешка 3 шара. Так как 3>2 , то по принципу Дирихле найдется «клетка» (цвет шара), в которую попадут как минимум 2 «зайца» (шара). Значит, надо достать наименьшее число шаров – 3.

2) Так как подряд могут попадаться все время шары одного цвета, то надо достать наименьшее число шаров – 11

3) наименьшее число шаров будет 12

Занятия в малых группах

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

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

Задача № 2  В классе 37 учеников. Докажите, что среди них найдутся 4 ученика, отмечающие день рождения в одном месяце.

Док-во: 1 способ: Пусть 37 учеников – «зайцы», а 12 месяцев – «клетки». Так как 37  12*3+1, то, применяя обобщенный принцип Дирихле, мы получаем, что найдется 4 ученика, родившиеся в один месяц

2 способ: Если в каждый месяц родилось не более 3 учеников, то всего учеников будет 36. А по условию задачи их 37,  значит, такого быть не может. Поэтому найдется 4 ученика,  отмечающие день рождения в один месяц.

Задача №3 Дано 12 целых чисел. Докажите, что  из них можно выбрать 2, разность которых делится на 11.

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

Задача №4: В ковре размером 4х4 метра моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1х1 метр, не содержащий внутри себя дырок. (дырки считать точечными)

Док-во: Ковер 4х4 метра можно разрезать на 16 ковриков размером 1х1 метр. А так как дырок 15, то хотя бы один из них окажется без дырки.

Задача №5: В мешке лежат 100 белых и 100 черных шариков. Они тщательно перемешаны и неразличимы на ощупь. Какое наименьшее число шариков нужно вынуть из мешка вслепую так, что бы среди них заведомо оказались два шара 1) одного цвета, 2) разного цвета, 3) белого цвета

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

2) наименьшее число шаров – 101

3) наименьшее число шаров – 102

Малая олимпиада

Задача №1: На дискотеку в студенческое общежитие, в котором 42 комнаты, пришли 36 гостей. Докажите, что найдется комната, в которую не пришел ни один гость

Док-во: Обозначив комнаты – «клетками», а гостей – «зайцами», имеем: 36<42. Тогда по принципу Дирихле найдется как минимум одна пустая «клетка», т.е. в какую-то комнату не придет не одного гостя.ъ

Задача№2: В школе 33 класса, 1150 учеников. Найдется ли класс, в котором меньше 35 учеников?

Решение: Допустим, что во всех классах не менее 35 учеников, тогда по всей школе будет не менее чем 35*33=1155 (учеников), что противоречит условию задачи. Значит в школе найдется класс в котором меньше, чем 35 учеников

Задача №3:Дано 9 целых чисел. Докажите, что из них можно выбрать 2, разность которых делится на 8

Док-во: Обозначим за «клетки» 0 остатки от деления на 8: 0, 1, 2, 3, 4, 5, 6, 7. «Клеток» будет 8. За «зайцев» обозначим 9 целых чисел. Так 9>8, то 2 целых числа будут иметь одинаковый остаток при делении на 8, а поэтому их разность будет делиться на 8.

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

Решение: Пусть 5 точек – «зайцы». Так как «клеток» должно быть меньше, то пусть их будет 4. Чтобы получить 4 «клетки», разобьем равносторонний треугольник с помощью средних линий на 4 равных треугольника – «клетки». Так как «зайцев» - 5,  «клеток» - 4 и 5>4, то по принципу Дирихле найдется клетка – равносторонний треугольник со стороной 0,5см, в который попадут не менее 2 зайцев – точек. А так как все 4 треугольника равны и расстояние между точками в любом треугольнике будет меньше, чем 0,5см, то мы доказали, что между некоторыми 2 точками из 5 расстояние будет меньше, чем 0,5см

Задача №5: В ящике комода, который стоит в темной комнате, лежат 10 коричневых и 10 красных носков одного качества и размера. Сколько носков нужно взять из ящика комода, не глядя, что бы среди них обязательно оказалась пара носков одного цвета?

Решение: Хорошо, что на левую и правую ногу носки одинаковые, поэтому достаточно побеспокоится только о цвете.

Заочная олимпиада

Задача №1: В классе 35 учеников. Можно ли утверждать, что среди них найдутся хотя бы 2 ученика, фамилии которых начинаются с одной буквы?

Решение: Обозначим 35 учеников за зайцев, а буквы за клетки. В  русском алфавите 33 буквы. Фамилии не могут начинаться на твердый и мягкий знак. Так как 35>31, то по принципу Дирихле найдется 2  ученика, у которых фамилия начинается с одной буквы

Задача №2: В школе 735 учащихся. Можно ли утверждать, что по крайней мере 3 ученика должны отмечать день своего рождения в один день?

Решение: Да, даже с учетом високосного года. 735=366*2+3

Задача №3: Верно ли, что из любых трех целых чисел можно выбрать два, сумма которых четна?

Решение: Так как числа бывают четные и нечетные, а всего чисел 3, то, применяя принцип Дирихле, как минимум 2 из них будут оба четными или оба нечетные. В первом и во втором случаях сумма чисел будет четной. Значит верно.

Задача №4:Внутри правильного шестиугольника со стороной 1см расположено 7 точек. Докажите, что расстояние между двумя точками меньше, чем 1см.

Док-во: Примем 7 точек за зайцев. Построим 6 клеток. Для этого разобьем правильный шестиугольник на 6 правильных треугольников, как на рисунке. Так как 7>6, то по принципу Дирихле хотя бы в один треугольник попадут не менее 2 точек. А расстояние между любыми 2 точками в правильном треугольнике со стороной 1см меньше 1см

Задача №5: В ящике комода, который стоит в темной комнате, лежат 10 пар коричневых и 10 пар черных перчаток одного качества и размера. Сколько перчаток нужно взять из ящика комода, не глядя, что бы среди них обязательно оказалась пара перчаток одного цвета?

Решение: Можно вытащить 10 черных перчаток на левую руку и 10 коричневых – на правую. А 21-я обязательно образует пару