Решение комбинаторных задач

Тема урока: Решение комбинаторных задач

Методы решения комбинаторных задач:

• метод перебора (подбираются задачи на развитие мышления);

• табличный метод (все условия вносятся в таблицу, в ней же выполняется решение);

• построение дерева возможных вариантов решений;

• правило умножения.

Табличный метод

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

Задача 1. Сколько нечетных двузначных чисел можно составить из цифр 1, 3, 4, 6, 7, 8, 9?

Решение. Составим таблицу: слева первый столбец - первые цифры искомых чисел, вверху первая строка - вторые цифры.

Ответ: 28.

Задача 2. Маша, Оля, Вера, Ира, Андрей, Миша и Игорь готовились стать ведущими на Новогоднем празднике. Назовите возможные варианты, если ведущими могут быть только одна девочка и один мальчик.

Решение. Составим таблицу: слева первый столбец - имена девочек, вверху первая строка - имена мальчиков.

Ответ: Все возможные варианты перечисляются в строках и столбцах таблицы. Всего 12 вариантов.

Задача 3. В школьной столовой приготовили на завтрак плов (П), кашу (К), блины (Б), а из напитков – сок (С), чай (Ч) и молоко (М). сколько различных вариантов завтрака можно составить?

Ответ: 9 вариантов.

Метод построения дерева возможных вариантов решений

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

Если его правильно построить, ты не упустишь ни один из возможных вариантов решения.

Рассмотрим задачу 1. Учитель попросил Олега разложить на полке 3 шара - желтый, красный, синий. Сколькими способами Олег может это сделать?

Начать можно и с желтого, и с красного, и с синего шара. Дерево вариантов будет выглядеть так:

Эта схема действительно похожа на дерево, правда, «вверх ногами» и без ствола. Каждый первый шар - это «корень» дерева, а ветви дерева - это различные варианты расположения шаров. По этой схеме несложно посчитать, что возможных комбинаций всего 6.

Ответ: 6 способов.

Схему-дерево возможных рассуждений можно располагать по-разному (корень вверху или внизу).

Правило умножения

Применяется для нахождения числа всех возможных исходов независимого проведения двух испытаний А и В, перемножив число всех исходов испытания А и число всех исходов испытания В.

Задача.

Сколько трехзначных чисел можно составить из цифр: 1, 2, 5, 8 используя в записи числа каждую из них не более одного раза?

Решение.

Первую цифру выбираем четырьмя способами (1, 2, 5, 8), вторую цифру можно выбрать тремя способами, и на выбор третьей цифры остается два способа. Количество искомых трехзначных чисел равно произведению 4 · 3 · 2 = 24.

Ответ: 24.

Решить самостоятельно:

1. В финальном забеге на 100 м участвуют Смирнов, Петров и Орлов. Назовите возможные варианты распределения призовых мест. (Решить, используя табличный метод)

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

3. Сколько трехзначных чисел можно составить из цифр: 1, 2, 5, 8 используя в записи числа каждую из них не более одного раза?

(Решить по правилу умножения)