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

Страница 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


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

Методика и организация исследования
Зрительная память во многом оказывает влияние на успешность обучения нынешних дошкольников в школе. Важно формировать некоторые приемы зрительного запоминания у детей дошкольного возраста в целях лучшей подготовки их к школьному обучению. Для того, чтобы улучшить память дошкольников, обучить их нео ...

Формы общения педагога с родителями в ДОУ
Содержание работы с родителями реализуется через разнообразные формы. Главное – донести до родителей знания. Существуют традиционные и нетрадиционные формы общения педагога с родителями дошкольников, суть которых – обогатить их педагогическими знаниями. Традиционные формы подразделяются на коллекти ...

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

Меню сайта

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