Элементы дискретной математики - 6 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

Составители: 

Рубрика: 

6
Из города А в город Б ведет 6 дорог, а из города Б в город В – 4 дороги, Из города А в
город Г – 2 дороги, и из города Г в город В – тоже 2 дороги. Сколькими способами
можно проехать от А до В?
Решение.
Из города А в город В можно попасть либо через город Б, либо через город Г. По
правилу произведения через город Б можно проехать 6·4=24 способами, через город Г
– 2·2=4 способами. Тогда из города А в город В можно попасть 24+4=28 способами.
Часто удается разбить все изучаемые комбинации на несколько классов, причем
каждая комбинация входит в один и только один класс. В этом случае общее число
комбинаций равно сумме чисел комбинаций во всех классах. Это утверждение называют
правилом суммы.
Если некоторый объект А можно выбрать m способами, а другой объект В можно
выбрать n способами, то выбор «либо А, либо В» можно осуществить m+n
способами.
При использовании правила суммы необходимо следить, чтобы ни один из способов
выбора объекта А не совпадал с каким-нибудь способом выбора объекта В.
В рассмотренной выше задаче число выборов после каждого шага зависит от того,
какие элементы были выбраны на предыдущих шагах. Рассмотрим пример ещё одной такой
задачи.
Задача.
Сколькими способами можно поставить на шахматную доску белого и черного королей
так, чтобы получилась допустимая по правилам игры комбинация.
Решение.
Шахматное поле имеет 64 клетки, поэтому белого короля можно поставить 64
способами. Как известно, король бьет клетки, расположенные непосредственно рядом с
ним. Таким образом, если король находится в углу, то под боем находятся 3 клетки,
если у стены, то – 5, если в центре, то – 8. Очевидно, что ставить черного короля нельзя
в ту же клетку, где находится белый король и в клетку, которая находится под боем.
Так как существует 4 способа поставить короля в угол, 24 способа – у стены и 36
способов – в центре поля, то ответ на вопрос задачи вычисляется следующим образом:
4·(64-4)+24·(64-6)+36·(64-9)=3612
Рассмотрим теперь вопрос, как вычислить количество способов выбора
объекта «либо А, либо В», если известно, что некоторые из способов выбора объекта А
совпадают с некоторыми способами выбора объекта В?

Страницы