Если вы уже научились вытаскивать из темноты предметы (смотрите пред. статью в нашем канале), то пора двигаться дальше!
Сегодня мы перейдём к более сложным задачам в одной из самых интересных тем олимпиадной математики — принципу Дирихле. Часто этот принцип объясняют так:
"Если в N (здесь для лучшего понимания можно подставить любое число) клетках сидит (N+1) кролик, то по крайней мере в одной клетке сидит не менее двух кроликов".
Это кажется очевидным в данной формулировке. Но с учеником обязательно нужно обсудить доказательство и рациональнее всего воспользоваться методом от противного.
Представим, что такой клетки нет, и во всех клетках менее двух кроликов, то есть один или ноль. Так как всего клеток N, то и количество кроликов в таком случае не должно превышать числа N (то есть ровно N или меньше), но по условию их (N+1), получаем противоречие.
Следует проговорить, что эта формулировка условная, для лучшего понимания. В общем виде принцип Дирихле звучит так: "если (N+1) элемент разбит на N множеств, то по крайней мере одно множество содержит не менее двух элементов".
В задачах не всегда легко понять, кто является "кроликами", а что — "клетками". Поэтому очень важно подробно обсудить с учеником, как он понимает эту формулировку, и как происходит процесс «рассадки кроликов по клеткам". Также необходимо определить, в чем разница условий "не менее", "менее", "более", "не более". Это тоже очень часто вызывает у учеников сложности при решении задач.
Сначала рассмотрим задачу из предыдущей статьи, которую можно так же решить основываясь на принципе Дирихле.
1) В новогоднем мешке дед Мороз принес шоколадки трех видов: темный, молочный и белый. Какое наименьшее число шоколадок надо взять наугад из мешка, чтобы среди них обязательно были хотя бы две одного вида?
Пусть шоколадки - это “кролики”, а вид - “клетки”. Каждый “кролик”-шоколадка сажается нами в “клетку” с названием - видом шоколадки. В каждой “клетке” окажется по одному “кролику”, но как только достанем четвертую шоколадку, то у нас не будет выбора - она попадет в “клетку”, в которой “кролик” уже есть.
Действительно, “клеток” - 3, значит, по принципу Дирихле должно быть 4 “кролика”.
Ответ: 4.
Перейдем к решению некоторых простых задач и будем решать их как методом от противного, так и принципом Дирихле.
2) В школе 367 учеников. Докажите, что по крайней мере у двух учеников день и месяц рождения совпадают.
Решение.
Метод от противного. Предположим, что у всех учеников разные даты рождения (без учёта года). В году 365 (или 366) дней. Это означает, что количество учеников не может превышать 366, что противоречит исходному условию.
Принцип Дирихле. Пусть ученики - "кролики", а даты рождения "клетки". Рассаживая "кроликов" по "клеткам" получим, что по принципу Дирихле окажутся хотя бы два "кролика" в одной "клетке".
3) В школу привезли 28 коробок с учебниками по математике, русскому языку и обществознанию (в каждой коробке были учебники только по одной дисциплине). Докажите, что среди них есть по крайней мере 10 коробок с учебниками по одному и тому же предмету.
Метод от противного. Предположим, что нет 10 коробок с учебниками по одной и той же дисциплине. То есть максимальное количество коробок для каждого предмета - 9. Значит, всего коробок получилось бы не более 27, что противоречит условию.
Воспользуемся обобщенным принципом Дирихле: “Если в N клетках сидят не менее (kN +1) кроликов, то в какой-то из клеток сидит по крайней мере (k + 1) кролик.”
Пусть коробки - "кролики", а дисциплина - "клетки". Так как 28=3*9+1, то применяя "обобщенный принцип Дирихле" для N=3, k=9, получим, что в какой-то "клетке"-дисциплине сидит не менее 10 "кроликов" - коробок.
4) В литературной гостиной сидят по кругу 24 ученика 5В класса, в котором девочек больше половины. Докажите, что какие-то две девочки сидят друг напротив друга.
Метод от противного. Предположим, что в каждой паре учеников сидящих напротив друг друга либо два мальчика, либо девочка и мальчик. Тогда количество девочек не превышает количества пар: 24:2=12, что противоречит условию.
Принцип Дирихле. Мы разделим всех учеников на 12 пар, которые будут сидеть друг напротив друга. Эти пары можно представить как «клетки», а девочек — как «кроликов». Поскольку девочек больше половины, то, согласно принципу Дирихле, найдётся пара «клеток», в которой будут находиться две девочки-«кролика».