Предположим, что вы не можете вспомнить последнюю цифру телефона своего друга. Какое наибольшее количество номеров придется набрать, чтобы ему дозвониться?
Поскольку в конце телефонного номера может стоять любая из десяти цифр, то вам в худшем случае придется сделать десять попыток, тем самым перебрав все возможные варианты.
Нередко в повседневной жизни мы встречаемся с задачами, решение которых требует рассмотрения и подсчета всех возможных комбинаций. Поэтому такие задачи навзывают комбинаторными.
Пример 1. Одноклассницы Оля, Валя и Катя дежурят по школе. Сколькими способами классный руководитель может расставить девочек по одной на каждом из трех этажей школы?
Решение. Предположим, что Олю назначили дежурить на третьем этаже. Тогда на втором этаже может дежурить Валя или Катя, а на первом − соответственно Катя или Валя.
Получаем два способа (две комбинации, два варианта) распределения дежурства (девочки обозначены первыми буквами их имен).
Пусть теперь дежурной на третьем этаже назначили Валю. Тогда на втором этаже может дежурить Оля или Катя, а на первом − соответственно Катя или Оля. Получаем еще два способа распределения дежурства.
И наконец, предположим, что дежурной на третьем этаже назначили Катю. Получаем еще два способа распределения дежурства.
Таким образом получилось шесть способов распределения дежурства.
Ответ: 6 способов.
При решении комбнаторных задач важно рассмотреть (перебрать) все случаи. Поэтому процесс перебора желательно сделать удобным и наглядным.
Например, решение задачи о распределении дежурства можнго проиллюстрировать с помощью такой схемы:
Эта схема позволяет записать шесть комбинаций, каждая из которых соответствует одному варианту распределения дежурства: ОВК, ОКВ, ВОК, ВКО, КВО, КОВ.
Изображженная схема напоминает перевернутое дерево. Поэтому ее называют деревом возможных вариантов.
Пример 2. Сколько углов изображено на рисунке 182?
Решение. Обозначение любого угла, изображенного на рисунке, состоит из трех букв, второй из которых обязательно является буква O, а две другие выбираются из букв A, B, C, D. Поэтому искомое количествоо углов равно количеству способов выбрать из букв A, B, C, D две буквы.
При записи всех возможных вариантов надо учесть, что, например, комбинации AB и BA соответствуют одному и тому же углу AOB.
Вначале перечислим все пары букв с первой A:
AB, AC, AD.
Теперь перечислим пары, у которых первая буква B, а вторая не является буквой A:
BC, BD.
Осталось перечислить пары, у которых первая буква C, а второй не является ни A, ни B:
CD.
Таким образом, получили шесть комбинаций:
AB, AC, AD, BC, BD, CD.
Следовательно, на рисунке 182 изображено шесть углов.
Ответ: 6 углов.
При решении этой задачи можно воспользоваться такой наглядной схемой.
Рассмотрим четыре точки, обозначенные буквами A, B, C, D (рис. 183).
Тогда количество отрезков, соединяющих каждые две точки, равно количеству углов, изображенных на рисунке 182. Например, отрезку AC на рисунке 183 соответствует угол AOC на рисунке 182, отрезку BC − угол BOC. И наоборот, каждому углу на рисунке 182 соответствует определенный отрезок на рисунке 183.
На рисунке 183 можно провести всего шесть отрезков. Следовательно, искомое количество углов равно шести.
С помощью схем, подобной той, которая изображена на рисунке 183, можно решать целый ряд задач. С помощью этой схемы решите такую задачу. При встрече четыре прямтеля обменялись рукопожатиями. Сколько всего было сделано рукопожатий? (Ответ: 6).