Задачи на принцип Дирихле

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

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

Очевидно, что вам не удастся так сделать, ведь клеток меньше, чем зайцев. А значит, в одну из клеток придётся посадить не меньше двух зайцев, и драки избежать не получится.

Также вам не удастся посадить 9 зайцев в 4 клетки так, чтобы в каждой из них было не больше двух зайцев. В одну из клеток придётся посадить 3 зайца.

Такие подсчёты с зайцами и клетками связаны с принципом Дирихле. Давайте сформулируем этот принцип.

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

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

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

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

Давайте с вами посмотрим на русский алфавит. В нём тридцать три буквы.

Конечно же, имя не может начинаться, например, на мягкий или твёрдый знак. Но всё же букв в алфавите, на которые может начинаться имя, больше чем 20. Значит, нельзя утверждать, что среди 20 учеников найдутся хотя бы 2, имена которых начинаются с одной и той же буквы.

Ребята, а можно ли утверждать, что среди 34 учеников класса обязательно найдутся 2 ученика, имена которых начинаются с одной и той же буквы? Очевидно, что можно, ведь в алфавите только 33 буквы, причём есть буквы, на которые имена начинаться не могут.

Задача вторая. В школе 570 учеников. Верно ли, что среди них обязательно найдутся 2 ученика, которые родились в один день?

Мы знаем, что в году 365 дней или 366 дней, если год високосный. 365 меньше 570, 366 тоже меньше 570. Следовательно, среди 570 учеников школы обязательно найдутся 2 ученика, которые родились в один день.

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

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

Если бы каждый день в течение всего, например, високосного года день своего рождения отмечали 2 ученика, то всего в школе было бы не более чем 2 умножить на 366, то есть не более 732 учеников.

В условии задачи сказано, что в школе 750 учеников. 732 меньше 750, а значит, утверждать, что по крайней мере 3 ученика должны отмечать день своего рождения в один и тот же день, можно.

Задача четвёртая. Убирая урожай на школьном участке, школьники собрали 25 ящиков, в одних из которых – картофель, в других – морковь, в третьих – свёкла, в четвёртых – лук. Можно ли утверждать, что имеется по крайней мере 7 ящиков, содержимое которых составляет один из указанных видов овощей?

Ребята, давайте рассмотрим самый неблагоприятный случай. Итак, пусть имеется 6ь ящиков с картофелем, 6 ящиков с морковью, 6 ящиков со свёклой и 6 ящиков с луком. Это всё составляет 24 ящика.

Если 25-й ящик будет с картофелем, то получится 7 ящиков с картофелем

Если 25-й ящик будет с морковью, то получится 7 ящиков с морковью.

Если 25-й ящик будет со свёклой, то получится 7 ящиков со свёклой.

Если 25-й ящик будет с луком, то получится 7 ящиков с луком.

Мы рассмотрели один из случаев. В других случаях будет больше 7 ящиков, содержимым которых будет один из данных видов овощей.

Следующая задача. В спортивном лагере 10 отрядов численностью 150 человек. Найдётся ли в этом лагере отряд, в котором не менее 15 человек?

В условии задачи сказано, что всего в спортивном лагере 10 отрядов. Предположим, что в каждом отряде меньше, чем 15 человек. Тогда всего в лагере было бы не более, чем 14 умножить на 10ь, то есть не более 140 человек.

В действительности же в спортивном лагере 150 человек. А значит, наше предположение, что в каждом отряде меньше, чем 15 человек, неверно. Следовательно, в лагере найдётся отряд, в котором не менее 15 человек.

Ещё одна задача. В путешествие отправились 14 туристов. Самому старшему из них 30 лет, а самому младшему 21 год. Можно ли утверждать, что среди туристов есть одногодки?

В условии задачи сказано, что самому старшему туристу 30 лет, а самому младшему 21 год. Следовательно, возраст каждого из 14 туристов может быть равен одному из чисел от 21 до 30. То есть всего 10 вариантов.

В путешествие отправились 14 туристов. Значит, среди них обязательно будут одногодки.

Друзья, на этом время, отведённое на нашу встречу, заканчивается. Пора прощаться. До свидания. До новых встреч.