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

9 класс

Тема урока :

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

1 урок

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

Такие задачи получили название комбинаторных задач , а раздел математики, в котором рассматриваются эти задачи, называют комбинаторикой.

Раздел математики,

в котором изучают

комбинаторные задачи,

называется

комбинаторикой

м

о

и

н

а

р

и

к

а

к

о

б

- раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций , подчинённых тем или иным условиям, можно составить из заданных объектов.

Термин «комбинаторика» происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».

Термин «комбинаторика» был введён в математический обиход немецким философом, математиком Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Познакомимся с некоторыми приемами решения комбинаторных задач

• решение методом перебора;
• решение с помощью дерева возможных вариантов;
• решение с помощью комбинаторного правила умножения;
• решение с помощью таблиц;
• решение с помощью графов.

№ 715

У Ирины 5 подруг: Вера, Зоя, Марина, Полина и Светлана. Она решила двух из них пригласить в кино. Укажите все возможные варианты выбора подруг. Сколько таких вариантов?

Замечание . При решении для краткости будем писать первые буквы имен.

М арина

С вета

П олина

В ера

З оя

Решение

Составим сначала все пары, в которые входит Вера.

ВЗ, ВМ, ВП, ВС

Получим 4 пары .

Выпишем теперь пары, в которые входит Зоя, но не входит Вера.

ЗМ, ЗП, ЗС

Таких пар три .

Далее составим пары, в которые входит Марина, но не входят Вера и Зоя.

МП, МС

Их две .

Далее составим пары, в которые входит Полина.

ПС

Еще одна пара

Всего существует 4+3+2+1=10

Ответ:10 вариантов

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

Рассмотрим еще одну задачу. На цветочной клумбе сидели ш мель, ж ук, б абочка и м уха. Два насекомых улетели. Какие пары насекомых могли улететь? Укажите все возможные варианты. Сколько таких вариантов?

ш

м

ж

б

Решение

м

б

б

ж

ж

ш

б

ш

м

ж

Всего 3+2+1=6

ш

м

Ответ:6 вариантов

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

Сколько двузначных чисел можно составить, используя цифры 1; 4; 7?

Решение: Для того, чтобы не пропустить и не повторить ни одного из чисел, будем выписывать их в порядке возрастания:

11;14;17; (начали с 1)

41;44;47; (начали с 4)

71;74;77; (начали с 7)

Таким образом, из трёх данных цифр можно составить всего 9 различных двузначных чисел.

Ответ: 9 чисел.

Решим аналогичную задачу о составлении трехзначных чисел из цифр 1;4;7, так чтобы цифры не повторялись . Для её решения построим схему - дерево возможных вариантов .

число

1

4

7

1

1

7

7

4

4

7

7

1

1

4

4

Ответ: числа 147;174;417;471;714;741

6 чисел (вариантов)

Приемы решения комбинаторных задач дерево возможных вариантов

Заметим, что ответ на вопрос, можно получить, не выписывая сами числа. Будем рассуждать так.

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

Мы нашли ответ на вопрос, используя так называемое комбинаторное правило умножения

«Если объект А можно выбрать m способами, а другой объект В можно выбрать k способами, то объект « А и В » можно выбрать m ∙ k способами».

комбинаторное правило умножения

У Куклы Светы 3 юбки и 5 кофт, удачно сочетающихся по цвету. Сколько различных комбинаций одежды имеется у Светы?

Решение. 3·5 = 15

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

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

Л

В

К

М

Логинова Н.В. МБОУ «СОШ №16»

Решение

М

В

Л

К

Ответ: 12 вариантов

С помощью дерева возможных вариантов решите задачу №714 .

Обед

Борщ

Рассольник

Гуляш

Гуляш

Котлеты

Котлеты

Сосиски

Сосиски

Пельмени

Пельмени

Приемы решения комбинаторных задач задачи, решаемые с помощью таблиц

У Миши 4 ручки разного цвета и 3 блокнота разного размера. Сколько различных наборов из ручки и блокнота сможет составить Миша? Реши задачу, составив таблицу.

б

м

с

с

ч

к

з

ч

с

к

з

б

с

м

12 различных наборов

Приемы решения комбинаторных задач задачи, решаемые с помощью таблиц

Сколько четных двузначных чисел можно составить из цифр 0,1,2,4,5,9?

0

2

4

1 2

1

1 4

1 0

2

2 4

2 2

2 0

4

Ответ:15 чисел (5·3)

4 0

4 2

4 4

5

5 4

5 2

5 0

9

9 0

9 2

9 4

м

о

и

н

а

р

и

к

а

к

б

о

ГРАФ – совокупность объектов со связями между ними. Объекты представляются как вершины , или узлы графа , а связи – как дуги , или ребра .

вершины

ребра

Логинова Н.В. МБОУ «СОШ №16»

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

Ответ: 10 рукопожатий

Решите задачу, используя граф

Сколько различных завтраков, состоящих из 1 напитка и 1 вида выпечки, можно составить из ч ая, к офе, б улочки, п еченья и в афель?

в

ч

б

п

к

Логинова Н.В. МБОУ «СОШ №16»

Приемы решения комбинаторных задач графы

выпечка

напитки

б

ч

в

к

п

6 завтраков

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

к

ч

б

в

б

п

п

в

Логинова Н.В. МБОУ «СОШ №16»

Решение задачи с помощью таблицы

Напитки

Выпечка

ч

к

б

б

б

к

ч

п

п

п

ч

к

в

в

в

к

ч

Решите задачу, используя граф

Шесть семей уехали отдыхать в разные города. Приехав к месту отдыха, они поговорили друг с другом по телефону. Сколько звонков было сделано?

Закончи построение графа, соответствующего данной задаче.

Приемы решения комбинаторных задач графы

Ответ :15 звонков

Приемы решения комбинаторных задач задачи, решаемые с помощью таблиц

1

1

2

2

3

3

4

4

5

5

6

6

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

Ответ :15 звонков

Домашнее задание:

• п. 30
• № 716 (перебор), 720 (дерево), 723 (граф), 725 (таблица), 727 (умножение).

Приемы решения комбинаторных задач дополнительные задачи

Задача 1

В магазине продают воздушные шары: красные, желтые, зеленые, синие. Какие наборы можно составить из двух разных шаров? Сколько наборов у тебя получилось?

Задачи, решаемые

методом организованного перебора

Задача 1

5 наборов

Приемы решения комбинаторных задач Задача 2

В парке 4 пруда. Было решено засыпать песком дорожки между ними так, чтобы можно было пройти от одного пруда к другому кратчайшим путем, т.е. не нужно было идти в обход.

Задание: покажи, какие дорожки надо сделать.

Графы

Решение

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

В танцевальном кружке занимаются пять девочек: Женя, Маша, Катя, Юля и Даша и пять мальчиков: Олег, Вова, Стас, Андрей и Иван. Сколько различных танцевальных пар можно составить? Заполни таблицу.

Задачи, решаемые

с помощью таблиц

Женя

Маша

Катя

Юля

Даша

Олег

Олег

Олег

Олег

Олег

Олег

Катя

Женя

Даша

Юля

Маша

Вова

Вова

Вова

Вова

Вова

Вова

Катя

Даша

Женя

Юля

Маша

Стас

Стас

Стас

Стас

Стас

Стас

Катя

Даша

Маша

Юля

Женя

Андрей

Андрей

Андрей

Андрей

Андрей

Андрей

Катя

Юля

Маша

Женя

Даша

Иван

Иван

Иван

Иван

Иван

Иван

Катя

Даша

Юля

Маша

Женя

Ответ : 25 пар

Задачи, решаемые с помощью таблиц

На завтрак Миша может выбрать: плюшку, бутерброд, пряник, или кекс, а запить он может: кофе, соком, кефиром. Сколько возможных вариантов завтрака?

Ответ:12 (4·3=12)

Существует много видов комбинаторных задач, это лишь некоторые из них.

Спасибо за внимание!