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

Страница 2

Способ 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, куда попал один Стас Иванов.

Страницы: 1 2 3


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

Математический кружок для 5-6 классов как средство развития познавательного интереса
Внеклассная работа по математике является неотъемлемой частью учебно-воспитательного процесса в школе. Она способствует углублению знаний учащихся, развитию логического мышления, расширяет кругозор. Кружок также имеет сильное воспитательное значение, так как его целью является не только освещение к ...

Нейропсихологические, психологические и психолингвистические аспекты развития письменной речи
Письменная речь – одна из форм существования языка, противопоставленная устной речи. Это вторичная, более поздняя по времени возникновения форма существования языка. Если устная речь выделила человека из животного мира, то письменность следует считать величайшим из всех изобретений, созданных челов ...

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

Меню сайта

Copyright © 2021 - All Rights Reserved - www.powereducator.ru