Элементы комбинаторики. Принцип Дирихле

Решение: Мы легко можем ответить на вопрос, сложив число синих и красных карандашей, 6+12=18.

Изменим вопрос к задаче: сколькими способами можно выбрать из коробки один карандаш? Получим комбинаторную задачу. Число способов выбора одного карандаша равно числу всех карандашей в коробке, т.е.18. Но 18 - это сумма 6 и 12, где 6 - число способов выбора синего карандаша, а 12 - число выбора красного карандаша. Т.о. правило суммы можно сформулировать следующим образом.

Если объект а можно выбрать n способами, а объект b можно выбрать k способами, то выбор a или b можно сделать n+k способами.

Принцип Дирихле.

В несерьёзной форме принцип Дирихле гласит: "Нельзя посадить 7 кроликов в 3 клетки, чтобы в каждой было не больше 2 кроликов. "

Более общая формулировка: "Если z зайцев сидят в k клетках, то найдётся клетка, в которой не менее z/k зайцев." Не надо бояться дробного числf зайцев: если получается, что в ящике не меньше 7/3 зайцев, значит, их больше двух.

Доказательство принципа Дирихле очень простое, но заслуживает внимания, поскольку похожие рассуждения"от противного" часто встречаются. Допустим, что в каждой клетке число зайцев меньше, чем z/k. Тогда в k клетках зайцев меньше, чем k · z/k = z. Противоречие!

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

1). В классе 30 человек. В диктанте Стас Иванов сделал 13 ошибок, а остальные - меньше. Докажите, что по крайней мере три ученика сделали ошибок поровну (может быть, по 9 ошибок).

Решение: Это доказывается с помощью принципа Дирихле. Подумайте, кто здесь зайцы, и где клетки. (Здесь "зайцы" - ученики, а "клетки" - число сделанных ошибок). В клетку 0 "посадим" всех, кто не сделал ни одной ошибки, в клетку 1 - тех, у кого одна ошибка, в клетку 2 - две,. и так до клетки 13, куда попал один Стас Иванов.

Теперь применим принцип Дирихле, докажем утверждение задачи от противного.

Предположим, никакие три ученика не сделали по одинаковому числу ошибок, то есть в каждую из клеток 0, 1,., 12 попало меньше трех школьников.

Тогда в каждой из них два человека или меньше, а всего в этих 13 клетках не больше 26 человек. Добавив Стаса Иванова, все равно не наберем 30 ребят. Противоречие.

Можно ли утверждать, что ровно трое сделали поровну ошибок? Нет, конечно. Возможно, что все ребята, кроме Стаса, написали диктант без единой ошибки, то есть, все сделали по 0 ошибок. Можно ли считать, что по крайней мере четверо попали в одну "клетку"? Нет, нельзя. Класс, в котором по 3 человека сделали 0, 1, 2 ошибки, по 2 человека - 3, 4,., 12 ошибок и один - 13, удовлетворяет условию задачи.

2). В одном доме живут 13 учеников одной и той же школы. В этой школе 12 классов. Докажите, что хотя бы два ученика, живущие в этом доме, учатся в одном и том же классе

Решение. В данной задаче классы - это клетки, а учащиеся - кролики. У нас имеется 13 "кроликов" и 12 "клеток". Учитывая принцип Дирихле, мы получаем, что хотя бы в одной клетке "кроликов" два. То есть, если в школе 12 классов, то максимум в них может учиться 12 учеников. А 13 ученик все равно будет учиться в одном из этих 12 классов.

Задачи для самостоятельного решения:

1). В магазине "Все для чая" есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем? 2). Сколько существует 6-значных чисел, все цифры которых имеют одинаковую четность? 3). У Васи на куртке 3 кармана. Каким числом способов он может положить в эти карманы две одинаковые монетки?

4). В корзине сидят котята - 2 черных, 2 рыжих и 1 полосатый. Сколькими способами можно выбрать трех котят так, чтобы они все были разной окраски?

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

6). Докажите, что любое число рублей можно уплатить, если покупатель и кассир имеют лишь трехрублевые и пятирублевые денежные знаки.

Актуально о образовании:

Плотность вещества
Для знакомства с новой для вас физической величиной, плотностью вещества, отправимся в литейный цех завода с весами и линейкой. Выберем несколько разных по размерам чугунных и алюминиевых слитков прямоугольной формы. Используя весы, измерим массу каждого слитка, используя линейку и формулу V=lbh, и ...

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

Влияние особенностей зрительного восприятия детей с нарушениями зрения на характер нарушений письма и пути их коррекции
Итак, помощью глаз человек воспринимает освещенность, цвет, величину, форму предметов, определяет движение и направление движения предметов, ориентируется в пространстве. При нарушении зрения происходит сокращение и ослабление функций зрительного восприятия у слабовидящих. У слабовидящих младших шк ...