Конспект урока: Комбинаторные задачи

Метод перебора вариантов

Представьте, что за вами должно приехать такси. По телефону оператор называет номер машины 24… А последнюю цифру в номере вы не услышали. Сколько существует номеров автомобиля с первыми цифрами 2, 4 (буквы не учитываем)? 

Последней цифрой может быть любая от 0 до 9. Получается, что таких номеров 10. Такие варианты номеров называются комбинациями, а сами задачи — комбинаторными.

Коля, Вася и Петя участвовали в эстафете. Сколько вариантов распределения мест среди этих трех учеников может быть?

Решение способом 1

Рассмотрим первый случай. Первое место занимает Коля, тогда либо Вася второе и Петя третье, либо Петя второе, а Вася третье. 

Если первое место занимает Вася, тогда либо Петя второе и Коля третье, либо Коля второе, а Петя третье.

Если первое место занимает Петя, тогда либо Вася второе и Коля третье, либо Вася третье, тогда Коля занимает второе место. 

Удобнее посмотреть все варианты в таблице:

Рис. 1. Пример 1. Способ 1

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

Метод «дерево возможных вариантов»

Способ 2

Задачу можно решить еще более наглядным способом с помощью схемы, где верхний ряд — первое место, второй ряд — второе место, третий ряд — третье место. 

Решение

Рис. 2. Пример 1. Способ 2

Такая схема называется деревом возможных вариантов.

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

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

Способ 3

На первом месте может оказаться один из трех ребят. Значит на втором двое, так как третий занял первое место. Значит на каждый из трех вариантов 1 места приходится по 2 варианта второго места (3 · 2). На третьем месте — один вариант, так как первое и второе места заняты. То есть на каждый вариант 2 места приходится только 1 вариант 3 места. 

Получаем  3 · 2 · 1 = 6.

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

Сколько углов на рис. 3?

Рис. 3. Пример 2. Углы с общей вершиной

Решение

Угол обозначим 3 буквами, одной из которых будет О, как вершина угла. Учтем, что углы BOC и COB — один и тот же угол. 

Начнем с буквы B. Выпишем углы, которые начинаются с этой буквы: BOC, BOD, BOE.

Берем букву С, но помним, что букву В повторно использовать уже не можем: COD, COE.

Осталась буква D, буквы C и В не используем: DOЕ.

C точки Е назвать угол не сможем, так как этот угол будет повторным. 

Итого получили 6 углов.

Ответ: 6 углов.

Графы

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

Рис. 4. Пример 3

Решение

 

Построим 4 точки, которые соответствуют четырем приятелям. Каждое рукопожатие отметим отрезком. Осталось сосчитать количество отрезков. Заметим, что если 1 пожал руку 2, то и 2 пожал руку 1 — засчитываем как одно рукопожатие. Получаем 6 отрезков. Такой графический метод решения задачи называется методом графов.

Ответ: 6

1. Укажите все трёхзначные числа, для записи которых используются только цифры (цифры не могут повторяться) 1, 2 и 3.

2. Сколько различных двузначных чисел можно составить из цифр 0, 1 и 2 (цифры могут повторяться)?

3. Сколько существует различных прямоугольников, площади которых равны 12 см², а длины сторон выражены целым числом сантиметров?

1. Что такое «комбинаторные задачи»?

2. Что такое дерево возможных вариантов?

3. Какие способы решения комбинаторных задач вы знаете?