Занятие №1. Комбинаторные задачи. Перебор всех возможных вариантов
.
В начале занятия учащимся необходимо дать понятие о таком разделе математики, как комбинаторика, и привести примеры нескольких комбинаторных задач для привития интереса к данному разделу.
В науке и практике часто встречаются задачи, решая которые приходится составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций. Такие задачи получили название комбинаторных задач, а раздел математики, в котором рассматриваются подобные задачи, называют комбинаторикой. Слово «комбинаторика» происходит от латинского слова combinare, которое означает «соединять, сочетать». Методы комбинаторики находят широкое применение в физике, химии, биологии, экономике, теории вероятностей и других областях знаний.
Приведем примеры некоторых комбинаторных задач.
1) Сколькими способами можно расположить в электрической цепи 7 различных приборов?
2) Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из 5 языков: русского, английского, французского, немецкого, итальянского, на любой другой из этих 5 языков?
3) Вова точно помнит, что в формуле азотной кислоты подряд идут буквы H, N, O и что есть один нижний индекс – то ли двойка, то ли тройка. Сколько имеется вариантов, в которых индекс стоит не на втором месте?
4) Сколько разных типов гамет может дать гибрид, гетерозиготный по 3 независимым признакам?
5) Перечислить все трехзначные числа, в записи которых встречаются только цифры 1 и 2.
6) Три друга – Антон, Борис и Виктор – приобрели два билета на футбольный матч. Сколько различных вариантов посещения футбольного матча для троих друзей?
Таким образом, различают следующие типы комбинаторных задач:
· Задачи, в которых требуется перечислить все решения (пример 5).
· Задачи, состоящие в требовании выделить из всех возможных решений такое, которое удовлетворяет заданному дополнительному требованию (пример 3).
· Задачи, в которых требуется подсчитать число решений (пример 1, 2, 6, 4).
Процесс навыков подсчета комбинаторных объектов можно расчленить на три этапа в зависимости от времени обучения и методов подсчета:
- подсчет методом непосредственного перебора;
- подсчет с использованием комбинаторных принципов;
- подсчет с использованием формул комбинаторики.
Каждый из этих этапов готовит почву для формирования навыков следующих этапов. Поэтому на начальном этапе с учащимися нужно обязательно рассмотреть бесформульные методы.
Рассмотрим основные методы, используемые в решении комбинаторных задач.
Перебор всех возможных вариантов
Операция перебора раскрывает идею комбинирования, служит основой для формирования комбинаторных понятий, поэтому на первом месте должна стоять задача по формированию навыков систематического перебора.
Пример 1. Из группы теннисистов, в которую входят четыре человека – Антонов, Григорьев, Сергеев и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары?
Составим сначала все пары, в которые входит Антонов (для краткости будем писать первые буквы фамилий). Получим три пары: АГ, АС, АФ.
Выпишем теперь пары, в которые входит Григорьев, но не входит Антонов. Таких пар две: ГС, ГФ.
Далее составим пары, в которые входит Сергеев, но не входит Антонов и Григорьев. Такая пара только одна: СФ.
Других вариантов составления пар нет, так как все пары, в которые входит Федоров, уже составлены.
Итак, мы получили 6 пар: АГ, АС, АФ, ГС, ГФ, СФ. Значит, всего существует 6 вариантов выбора тренером пары теннисистов из данной группы.
Способ рассуждений, которым мы воспользовались при решении задачи, называют перебором возможных вариантов.
Тут же необходимо пояснить учащимся, что в данном примере нам не важен порядок выбора пары: Антонов и Григорьев или Григорьев и Антонов, и привести пример задачи, где учитывается порядок элементов в комбинации.
Пример 2. Три друга – Антон, Борис и Виктор – приобрели два билета на футбольный матч на 1-е и 2-е места первого ряда стадиона. Сколько у друзей есть вариантов занять эти два места на стадионе?
Если на матч пойдут Антон и Борис, то они могут занять места двумя способами: 1-е место – Антон, 2-е – Борис, или наоборот. Аналогично Антон и Виктор, Борис и Виктор. Таким образом, мы получили 6 вариантов: АБ, БА, АВ, ВА, БВ, ВБ.