Откуда мы знаем, что такое точка? | страница 10

m + m + … + m = m∙k (1)

(слева в (1) k слагаемых). Маршруты мы считаем различными, если они не совпадают хотя бы в одной из своих частей.

Возможна ситуация, когда, например,

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

Применим теперь правило произведения к решению простейшей задачи. Пусть города А и В связаны сетью дорог, как показано на рис. 6.3.

Ехать из А в В можно только по направлениям, указанным стрелками (так что мы, по существу, имеем дело с ориентированным графом). Спрашивается, сколькими способами можно доехать из А в В? Нетрудно видеть, что выбор первого участка маршрута (до развилки) можно осуществить пятью способами, после чего выбрать второй участок пути всегда (т.е. при любом выборе первого участка) можно тремя способами. Таким образом, применимо правило произведения, и общее количество способов, которыми можно добраться из А в В, равно 5∙3 = 15.

Поставим теперь следующий вопрос: а сколькими способами можно вернуться из В в А? (Разрешается ехать только против направления стрелок на рис. 6.3).

Из рис. 6.3 очевидно, что правило произведения «в обратную сторону» не работает. Тем не менее, понятно, что каждому маршруту из А в В соответствует в точности один маршрут из В в А (мы увидим этот маршрут, если «прокрутим киноленту» в обратном направлении). Значит, вернуться из В в А можно по-преж-

нему 15-ю способами.

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

А именно, пусть на этот раз города А и В связаны сетью дорог, изображенной на рис. 6.4.

Понятно, что в качестве упорядоченной пары (a, b) здесь следует брать пару: (малый начальный участок маршрута, малый конечный участок маршрута).

Выбор такой пары, очевидно, полностью определяет сам маршрут из А в В, и общее количество маршрутов из А в В вычисляется по правилу произведения и равно 2∙3 = 6. Число маршрутов из В в А тем самым также равно шести.

Возможны еще более любопытные конфигурации дорог между А и В, к которым по-прежнему применимо правило произведения для подсчета числа возможных маршрутов из