Принцип Дирихле. Важнейшая математическая теорема, которую Вы должны помнить с 5 класса

Amney

Администратор
Сообщения
260
Реакции
125
Возраст
28
Приветствую Вас, уважаемые Читатели! Сегодня расскажу Вам об основной теореме комбинаторики, которая, несмотря на тривиальность своей формулировки, чрезвычайно важна не только при решении задач, но и в повседневной жизни. Кроме того, первые её упоминания в школьном курсе математики относятся к 5(!!!) классу. В статье рассмотрим формулировку принципа Дирихле и решение одной из задач "на пальцах". Поехали!

Иоганн Дирихле. Источник: https://regnum.ru/uploads/pictures/news/2016/08/15/regnum_picture_1471269264226831_normal.jpg
Дирихле и кролики
Самая распространенная формулировка принципа Дирихле, как ни странно, связана с кроликами:

Если кролики рассажены в n клеток, причем количество кроликов больше, чем клеток, то хотя бы в одной клетке находится более одного кролика.
1600727498562.png
Естественно, что под кроликами и клетками могут пониматься не только голуби и ящики (как в английском варианте формулировки), но и вообще любые объекты, которые в математике принято заменять наборами множеств:
Если в множестве А, содержащем 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 ребят. Задача решена.
 

mexan

Администратор
Сообщения
797
Реакции
118
Блин, у меня с математикой с детства проблемы))). Статья интересная, но тяжеловато дается в нее вникнуть.
 
Верх