ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16655
Скачиваний: 202
46
разрядному двоичному коду, содержащему m единиц (и n нулей), будет соот-
ветствовать вполне определённый путь, соединяющий точки A и B. Например,
кодом 0110111010 представлен путь, выделенный на рисунке 2.2 жирными ли-
ниями. Следовательно, чтобы решить поставленную задачу, достаточно найти
число (m + n)-разрядных двоичных кодов, содержащих n нулей и m единиц. Со-
гласно формуле (2.12), это число равно:
.
!
!
)!
(
n
m
m
n
С
m
m
n
+
=
+
(2.14)
Согласно условию n = 4, m = 6:
6
4 6
(4 6)!
10!
7 8 9 10
210.
4! 6!
4! 6!
1 2 3 4
С
+
+
⋅ ⋅ ⋅
=
=
=
=
⋅
⋅
⋅ ⋅ ⋅
Таким образом, число N кратчайших путей, ведущих от А к В, равно 210;
2) чтобы определить число кратчайших путей от А до В, проходящих че-
рез точку С, сначала найдём число N
1
путей, соединяющих точки А и С, затем
определим число N
2
путей, соединяющих точки С и В. По формуле (2.14) нахо-
дим:
4
1
6
6!
15;
4! 2!
N
С
=
=
=
⋅
2
2
4
4!
6.
2! 2!
N
С
=
=
=
⋅
По правилу произведения:
N = 15·6 = 90.
Таким образом, через точку C проходит 90 путей;
3) число путей, ведущих от А к В и не проходящих через точку С, равно:
210 – 90 = 120.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.25
· · · · · · · · · · · · · · · · · · · · · ·
Сколько существует семизначных чисел двоичной системы счисления, в
которых нет рядом стоящих единиц, если считать, что числа могут начинаться с
нуля?
Обозначим искомое число буквой N. Оно состоит из нескольких слагае-
мых. Рассмотрим каждое из них:
а) в числе нет единиц. Такое число существует только одно (оно состоит
из семи нулей), следовательно, п
1
= 1;
б) в числе содержится точно одна единица. Таких чисел 7, т. е. п
2
= 7;
47
в) в числе содержатся точно две единицы и пять нулей. Запишем после-
довательность из пяти нулей. Между нулями, а также слева и справа от них по-
ставим по одной точке. Получим шесть точек. Заменим какие-либо две точки
единицами, а все остальные точки удалим. Получится семизначное двоичное
число, содержащее пять нулей и две единицы, которые стоять рядом не могут.
Всего существует
2
6
С
= 15 способов замены двух точек из шести единицами,
следовательно, п
3
= 15;
г) в семизначном числе может содержаться три единицы и четыре нуля.
Запишем нули в ряд и расставим точки по аналогии с предыдущим случаем.
Получим пять точек. Заменить их тремя единицами можно
3
5
С
= 10 способами.
Следовательно, п
4
= 10;
д) число, в котором четыре единицы и три нуля, существует только одно:
1010101, следовательно, п
5
= 1.
Сумма всех найденных величин даёт искомое число:
N = 1 + 7 + 15 +10 + 1 = 34.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.26
· · · · · · · · · · · · · · · · · · · · · ·
Сколько существует пятизначных десятичных чисел, не начинающихся с
нуля, в которых цифры идут:
1) в порядке возрастания слева направо?
2) в порядке убывания слева направо?
На первый взгляд ответы в обоих случаях должны быть одинаковыми. Но
это не так:
1) запишем десятичные цифры в порядке их возрастания слева направо,
удалив нуль, так как по условию с нуля пятизначные числа не начинаются.
Пять цифр из девяти можно выбрать
5
9
С
= 126 способами. Таким образом, отве-
том к первой задаче является число 126;
2) вторая задача решается точно таким же образом, но с учётом того, что
нуль не удаляется. Все десятичные цифры записываем, начиная с 9, в порядке
убывания слева направо. Так как нуль стоит в конце этой последовательности,
то он не может оказаться первой цифрой в пятизначном числе. Следовательно,
в сочетаниях участвуют все 10 цифр и количество пятизначных чисел, в кото-
рых цифры идут в порядке убывания, равно:
5
10
С
= 252.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
48
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 2.27
· · · · · · · · · · · · · · · · · · · · · ·
Множество A состоит из 4-значных десятичных чисел. Повторы цифр
возможны. Числа могут начинаться с нуля. Сколько в этом множестве таких
чисел, в которых:
1) единиц больше, чем нулей?
2) нулей больше, чем единиц?
3) нулей столько же, сколько единиц?
Из этих трёх задач достаточно решить только одну, а ответы к остальным
можно найти очень простыми рассуждениями. Однако в данном случае решим
их независимо одна от другой.
1. Обозначим буквой M количество чисел, в которых единиц больше, чем
нулей. Рассмотрим шесть случаев:
а) в числе одна единица и нет нулей. Если число начинается с единицы,
то в каждом из остальных разрядов может стоять одна цифра из восьми. Таких
чисел возможно 512. Единица может занимать любое из четырёх мест в числе.
Следовательно, всего возможно 512
⋅4 = 2 048 чисел, в которых нет нулей, и со-
держится точно одна единица;
б) в числе две единицы и нет нулей. Так как два места в числе заняты
единицами, то для других цифр остаётся также два места. Они могут быть заня-
ты 8
⋅ 8 = 64 вариантами. Для размещения двух единиц существует
6
2
4
=
C
спо-
собов. Тогда чисел с двумя единицами и без нулей существует
64 6 384
⋅ =
;
в) в числе две единицы и один нуль. С этими характеристиками возможно
96
8
4
2
3
=
⋅
⋅
C
чисел;
г) в числе три единицы и нет нулей. Таких чисел существует
;
32
8
1
4
=
⋅
C
д) в числе три единицы и один нуль. Так как других цифр нет, то числа
можно рассматривать как двоичные:
;
4
1
4
=
C
е) в числе четыре единицы. Это число 1111.
Таким образом:
M = 2048 + 384 + 96 + 32 + 4 + 1 = 2 565.
Столько возможно чисел, в каждом из которых единиц больше, чем ну-
лей.
2. Количество чисел, в которых нулей больше, чем единиц, обозначим
буквой N. Если чисел, в которых единиц больше, чем нулей, существует 2 565,
49
то столько же возможно и тех чисел, в которых нулей больше, чем единиц, то
есть
N = M = 2 565.
3. Количество чисел, в которых нулей столько же, сколько единиц, обо-
значим буквой K. Как и в первом примере, разобьём задачу на более простые
подзадачи. Необходимо рассмотреть только три случая:
а) в числе нет нулей и нет единиц. Таких чисел существует
8
4
= 2
12
= 4 096;
б) в числе одна единица и один нуль. Таких чисел возможно
;
768
2
8
2
4
=
⋅
⋅
C
в) в числе две единицы и два нуля: 1100, 1010, 1001, 0110, 0101, 0011 –
шесть чисел.
Таким образом, количество чисел, в каждом из которых нулей столько
же, сколько и единиц, равно:
K = 4 096 + 768 + 6 = 4 870.
Проверим решения. Так как в каждом числе либо единиц больше чем ну-
лей, либо нулей больше чем единиц, либо единиц и нулей поровну, то должно
выполняться равенство:
M + N + K = 10 000,
(2.15)
где 10 000 – это общее количество четырёхзначных чисел, которые могут начи-
наться с нуля, и в которых нет ограничений на повторы цифр. Подставим в
(2.15) значения M, N и K:
2 565 + 2 565 + 4 870 = 10 000.
Таким образом, равенство (2.15) выполняется, следовательно, ошибок
нет.
Заметим, что поскольку M = N, то формулу (2.15) можно записать в виде
2M + K = 10 000.
(2.16)
Отсюда следует, что хотя в данном примере приведены три задачи, ре-
шать их все нет необходимости. Достаточно, как уже упоминалось, решить
только одну: найти число K. А числа M и N согласно (2.16) определить по фор-
муле:
10 000
.
2
K
M
N
−
=
=
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
50
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Сколько существует 7-значных двоичных чисел, в каждом
из которых содержится точно три единицы? Числа могут начинать-
ся с нуля.
2.
Сколько существует 10-значных двоичных кодов, содер-
жащих по 6 нулей? Коды могут начинаться с нуля.
3.
Сколько существует 8-значных двоичных чисел, начинаю-
щихся с нуля, если в каждом коде четыре нуля?
4.
Сколько существует 10-разрядных двоичных чисел, в кото-
рых четное число единиц? Числа могут начинаться с нуля.
5.
В шахматном городе размером
n
m ×
число кратчайших
диагональных путей, состоящих из 11 отрезков, равно 462. Найдите
m и n, если
m
< n, m ≠ 1.
6.
В числе 32514768 три цифры заменили нулями. Получилось
новое число. Если в заданном числе заменить нулями другие три
цифры, получим ещё одно число. Сколько новых восьмизначных
чисел можно получить, если нулями заменять какие-либо три циф-
ры? Новые числа могут начинаться с нуля.
7.
Замок сейфа открывается одновременным нажатием трех
кнопок с номерами i, j, k, где i, j, k = 1,2,3, …, 12; i
≠
j; i
≠
k; j
≠
k.
Тройка этих номеров образует кодовый ключ. Некто решил открыть
сейф путем проб и ошибок (будем считать, что сирена, подающая
сигнал тревоги на неправильный код, отключена). Сколько троек
ему придется проверить в самом неблагоприятном случае?
8.
Сколько существует четырехзначных десятичных чисел, у
которых каждая следующая цифра больше предыдущей? С нуля
числа не начинаются.
9.
Сколько существует четырехразрядных десятичных чисел,
у которых каждая следующая цифра меньше предыдущей?
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·