Занимательные задачи: принцип Дирихле. Часть 1
Предмет: Математика, 5 класс
Автор: Черняев Игорь Владимирович

Цели и задачи урока: познакомить обучающихся с принципом Дирихле и дать представление о красоте и полноте данного метода решения соответствующего класса задач.

Предметные результаты: уметь решать задачи с помощью принципа Дирихле; показать его применение для решения разнообразных задач.

Метапредметные и личностные результаты: развивать вычислительные навыки, умения решать задачи, развивать логическое мышление учащихся, воспитывать интерес к математике.

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

1. Вводная задача.

В непрозрачном мешке лежат 5 белых и 2 черных шара.

а) Какое наименьшее количество шаров нужно вытащить, чтобы среди них обязательно оказался хотя бы один белый шар?

б) Сколько шаров нужно вытащить, чтобы среди них оказался хотя бы один белый и хотя бы один черный шар?

Давайте посмотрим: мы вытаскиваем один шар. Он может быть либо черным либо белым. Если он белый, то ура, мы вытащили хотя бы один белый шар. Если он черный, то тащим снова. Ситуация повторяется. Если он черный – то нам снова придется тащить шар, и вот теперь он оказывается заведомо белым, потому что все два черных мы уже вытащили. Получается, что в «худшем» случае, у нас будет белым третий вытащенный нами шар. В чем опасность? Без разбора всех случаев не понятно, ну или, более точно, остается не доказанным, почему в других ситуациях не придётся вытаскивать ещё большее число шаров. То есть без обоснования почему именно этот случай «худший» и чем именно он «плох» наше решение может быть не полно, а может быть просто не верно. Например, можно ошибочно предположить, что так как случай, когда мы вытягиваем белый шар вторым, «хуже» ситуации, когда мы вытягиваем его же, но первым, то это и есть наш «худший» случай.

Заметим, что какой бы шар мы не вытащили первым, шар одного из цветов у нас уже появится, а значит вопрос сводится к рассмотрению двух задач аналогичных задаче из предыдущего пункта: если первым мы вытащим белый шар, то сколько шаров нужно вытащить, чтобы среди них обязательно оказался хотя бы один черный шар, причем белых шаров 4, а черных 2, и наоборот, если вытащим черный шар, то сколько шаров придется вытащить, чтобы среди них обязательно оказался хотя бы один белый шар, причем белых шаров 5, а черный 1?

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

А во втором случае нам достаточно неудачно вытащить 1 черный шар, для того чтобы все оставшиеся шары оказались белыми, откуда и имеем, что нам придётся вытащить 3 шара в исходной задаче при условии, что первый шар оказался черным. Значит нам придётся вытащить 6 шаров для выполнения условия задачи в любом случае.

Легко заметить, что рассуждения о «худшем случае» оказываются и неэффективны и опасны. При этом если мы рассмотрим ситуацию более сложную, то путать он нас будет ещё сильнее.

2. Вводная задача на принцип Дирихле

Докажите, что если 101 кролик рассадить в 100 клеток, то по крайней мере в одной клетке будет хотя бы 2 кролика.

И вот тут начинается настоящая засада для любителей «худшего случая». Потому что сформулировать, по какому критерию случай признается «худшим» в данной ситуации бесконечно тяжело. Иными словами не понятно почему при всех, действительно всех, рассадках по клеткам кроме предложенной (и названной «худшей») у нас будет либо больше клеток где хотя бы 2 кролика, либо клетка где их сильно больше 2. Перебор всех вариантов кажется нам также слабопривлекательной идеей… И тут остается подход, который носит пышное название принципа Дирихле:

Ну хорошо, давайте действовать от противного. Предположим обратное: допустим не найдётся клеток, где содержится хотя бы два кролика. Значит в любой клетке оказывается не более 1 кролика, а значит в 100 клетках их не более 100. А у нас по условию их 101. Значит наше предположение было не верно, и клетка где содержится хотя бы 2 кролика всё же найдется.

Замечу, что если мы в данном рассуждении оценки, то есть неравенства, попытаемся заменить на равенства, то всё сломается: например, фраза «значит в любой клетке оказывается 1 кролик» не описывает ситуации когда в какой-то клетке кролика нет. А значит не описывает все возможные варианты, и следовательно требует отдельного пояснения, что накладно.

Задача 3. В школе 20 классов. В ближайшем доме живёт 23 ученика этой школы. Можно ли утверждать, что среди них будет хотя бы два одноклассника?

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

Задача 4. Коля подсчитал, что за день, на завтрак, обед и ужин он съел 10 конфет. Докажите, что хотя бы один раз он съел не меньше 4 конфет.

Давайте действовать от противного. Предположим обратное: допустим за каждый прием пищи он съедал не более 3 конфет. Значит всего их не более 9. А у нас по условию их 10. хотя бы один раз он съел не меньше 4 конфет.

Задача 5. В коллекции 25 монет по 1, 2, 5, 10 рублей. Имеется ли среди них 7 монет одинакового достоинства?

Пусть нет. Тогда каждого достоинства не более 6 монет, а всего их тогда не более 24. Но по условию их 25, что невозможно. А значит наше предположение было не верно, и среди них есть 7 монет одинакового достоинства.

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

Дополнительная информация

Рекомендуемые практикумы:

Задача 1. В непрозрачном мешке лежат 5 белых и 2 черных шара.

Какое наименьшее число шаров нужно вытащить, чтобы среди них обязательно оказалось 3 белых и 1 черный шар?

Сколько шаров нужно вытащить, чтобы среди них обязательно оказались 2 шара одного цвета?

Задача 2. Верно ли, что если 743 кролика рассадить в 35 клеток, то по крайней мере в одной клетке будет хотя бы 22 кролика.

Задача 3. В школе учится 370 человек. Докажите, что среди всех учащихся найдутся два человека, празднующие свой день рождения в один и тот же день.

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