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

Способ 2: Для каждого из трех городов существует 2

варианта маршрута по оставшимся городам. Если 3 умножить на 2, получится 6. Такой же ответ получится при помощи дерева вариантов.

Про второй способ рассуждений обычно говорят так: мы использовали правило умножения.

Комбинаторные задачи бывают самых разных видов. Но большинство из них решается с помощью двух основных правил – правила суммы и правила произведения. Продолжим знакомиться с правилом произведения (умножения), сформулируем утверждение: Если первую компоненту пары можно выбрать n способами , а вторую можно выбрать k способами , то число всевозможных комбинаций пар равно произведению чисел n и k.

Задача 3:

Саша, Петя, Денис, Оля, Настя часто ходят в кафе. Каждый раз, обедая там, они рассаживаются по-разному. Сколько дней друзья смогут это сделать без повторения?

Решение: Пронумеруем стулья, на которых должен сесть каждый, и будем считать, что они рассаживаются поочередно:

№1 - Саша - есть возможность выбрать из 5 вариантов (стульев)№2 - Петя - 4 варианта№3- Денис - 3 варианта№4- Оля - 2 варианта№5 - Настя- 1 вариант

Используя правило умножения, получаем: 5х4х3х2х1=120

Теперь решим задачу, применяя правило сложения.

Задача 4:

В коробке 6 синих карандашей и 12 красных. Сколько всего карандашей в коробке?

Решение: Мы легко можем ответить на вопрос, сложив число синих и красных карандашей, 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, куда попал один Стас Иванов.

Новое в образовании:

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

Распределение функциональных обязанностей при проведении диагностики
Врач детского сада и приглашенные из поликлиники специалисты узкого профиля оценивают и прогнозируют здоровье детей, разрабатывают рекомендации для воспитателей. Наличие или отсутствие заболеваний у ребенка определяют врачи-специалисты. Функциональное состояние органов и систем выявляются клиническ ...

Взаимодействие школы и семьи
Люди постоянно общаются, вступая друг с другом во взаимодействие. Можно сказать, взаимодействие - одно из воплощений связей, отношений между людьми утверждал Б. З. Фульфов. Взаимодействие людей в воспитательной системе школы строится на различных уровнях, причем семья от этой системы неотделима. Им ...