Подписывайтесь на канал в Яндекс. Дзен или на канал в телеграм "Математика не для всех", чтобы не пропустить интересующие Вас материалы.
Приветствую Вас, уважаемые Читатели! Сегодня расскажу Вам об основной теореме комбинаторики, которая, несмотря на тривиальность своей формулировки, чрезвычайно важна не только при решении задач, но и в повседневной жизни. Кроме того, первые её упоминания в школьном курсе математики относятся к 5(!!!) классу. В статье рассмотрим формулировку принципа Дирихле и решение одной из задач "на пальцах". Поехали!
Иоганн Дирихле. Источник: https://regnum.ru/uploads/pictures/news/2016/08/15/regnum_picture_1471269264226831_normal.jpg
Дирихле и кролики
Самая распространенная формулировка принципа Дирихле, как ни странно, связана с кроликами:
Если кролики рассажены в n клеток, причем количество кроликов больше, чем клеток, то хотя бы в одной клетке находится более одного кролика.
Если клеток, больше чем голубей, хотя бы одна клетка останется свободной.
Естественно, что под кроликами и клетками могут пониматься не только голуби и ящики (как в английском варианте формулировки), но и вообще любые объекты, которые в математике принято заменять наборами множеств:
Если в множестве А, содержащем N+1 элементов, имеется N элементов, удовлетворяющих каким-либо различным свойствам, то хотя 2 из этих элементов, имеют одинаковое свойство.
Например, есть множество разноцветных шаров цветов радуги. Если шаров будет больше 8, то хотя бы два их них будут одинакового цвета.
Доказательства принципа Дирихле
Да, Вам не показалось, даже это утверждение в математике требует доказательства. Впрочем, оно очень легкое и строится методом от противного:
Пусть есть N клеток и N+1 кролик. Предположим, что в каждой клетке не более одного кролика:
- В первой — хотя бы один;
- Во второй — хотя бы один;
- ….
- В клетке с номером N — хотя бы один.
Мы получили N неравенств, которые теперь складываем:
Слева — количество кроликов, справа — количество клеток. В итоге мы приходим к противоречию в том, что кроликов меньше, чем клеток, хотя в условии утверждалось обратное.
Задача на принцип Дирихле
С помощью принципа Дирихле легко решаются, кажущиеся на первый взгляд сложными, задачи:
Пусть диктант писали 30 человек. Вова сделал больше всех ошибок в работе — 13. Покажите, что минимум 3 ученика сделали равное количество ошибок.
Решение всех таких задач начинается с понимания, что мы относим к "клеткам", а что к "кроликам". В данном случае в качестве "кроликов" выступают ученики, а в качестве "клеток" — сделанные ими ошибки.
Источник: http://kaz.rs.gov.ru/uploads/news/cover/47829/compressed_file.jpeg
Если в первую клетку посадить учеников, которые не сделали ни одной ошибки, во вторую — сделавших две ошибки и т.д., а в тринадцатую посадить Вову, то решить задачу можно опять методом от противного:
Пусть среди класса нет учеников, сделавших одинаковое количество ошибок. Тогда в каждой клетке максимум 2 ученика. Т.к. клеток всего 14 (в последней сидит один Вова), то суммарное количество учеников не может превышать 13*2+1=27 человек. Мы пришли к противоречию, т.к. диктант писало 30 ребят. Задача решена.
В следующем материале решим еще пять-семь задач. Рассмотрим задачи из комбинаторики, теории чисел и геометрии. Принцип Дирихле поистине универсален!
Понравилось? А теперь вспомните то, что Вы должны были проходить в 10-11 классе — простой материал о производной и её применении.
Путеводитель по каналу "Математика не для всех" — здесь собрано больше 100 статей на самые разнообразные темы: как для новичков, так и для более начитанных математиков! ССЫЛКА НА ДЗЕН-КАНАЛ и TELEGRAM. Также есть группы в VK,Одноклассниках и Facebook : всё для математического просвещения!
Второй проект — канал "Русский язык не для всех".
