ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 6265
Скачиваний: 13
71
Решение можно проверить. Для этого определим количест-
во всех 14-значных двоичных чисел, в каждом из которых точно
три единицы и которые нигде рядом не стоят. Если в 14-значном
числе три единицы, то в нем 11 нулей. Запишем их в ряд, отде-
лив один нуль от другого точками и поставив по одной точке
слева и справа от нулей:
.0.0.0.0.0.0.0.0.0.0.0.
Получилось 12 точек. Каждую точку можно заменить одной
единицей. Всего единиц 3. Следовательно, заменить единицами
можно любые три точки (остальные точки при этом удаляются).
Всего существует k способов выбора трех нулей для замены их
единицами, где
3
12
12!
10 11 12
220.
3!(12
3)!
1 2 3
k
C
⋅ ⋅
=
=
=
=
−
⋅ ⋅
Именно это число приведено в условии задачи, следова-
тельно, решение верно.
Пример 3. Десятизначное двоичное число, в каждом из ко-
торых нет рядом стоящих единиц, разделили на две равные час-
ти — левую и правую. Сколько существует 10-значных двоич-
ных чисел, в каждом из которых слева нулей больше, чем спра-
ва?
Решение. Рассмотрим левую часть. Запишем все пятизнач-
ные числа, не содержащие рядом стоящих единиц. Всего их су-
ществует 13:
00000 10000 10100 10101
01000
10010
00100
10001
(1)
00010
01010
00001
01001
00101
Здесь четыре колонки. В первой нет единиц, во второй од-
на, в третьей две и в четвертой три единицы. Очевидно, что та-
кие же числа могут стоять и в правой части.
Разобьем задачу на ряд простых подзадач. Пусть слева в 10-
значном числе записано 00000. Тогда справа может быть любое
число из 13 за исключением того же числа 00000, поскольку со-
гласно условию задачи слева должно быть больше нулей, чем
72
справа. Следовательно, найдено 12 чисел, удовлетворяющих
условию примера.
Пусть слева содержится одна единица. Из них четыре числа
оканчиваются нулями. После каждого из них может быть по-
ставлено любое число из третьей и четвертой колонок из списка
(1). Это значит, что найдено еще 28 чисел из искомых. Если сле-
ва записано число 00001, то правое число не может начинаться с
единицы. Отсюда получаем еще три искомых числа. Добавим их
к 28 — получим 31 число.
Пусть слева содержится две единицы и три нуля — третья
колонка в списке (1). Тогда справа может быть только одно чис-
ло 10101. Слева могут быть записаны только те числа, которые
оканчиваются нулем. Следовательно, на этом этапе получаем
три новых числа.
Результаты трех вычислений сложим: 12 + 31 + 3 = 46.
Столько существует 10-значных двоичных чисел, в каждом из
которых нет рядом стоящих единиц и где слева нулей больше,
чем справа.
Ответ: 46.
Этот ответ можно проверить. Обозначим: k
1
— количество
чисел, удовлетворяющих условию примера; k
2
— количество
чисел, удовлетворяющих тому же условию примера, но для слу-
чая, когда слева нулей меньше, чем справа; k
3
— количество чи-
сел, в которых слева столько же единиц, сколько и справа; k —
общее количество 10-значных чисел, в каждом из которых нет
рядом стоящих единиц. Очевидно, что справедливо соотношение
k = k
1
+ k
2
+ k
3
.
(2)
Их этих четырех величин известными являются только две:
k
1
= k
2
= 46. Необходимо найти k и k
3
.
Определяем число k:
а) если в числе нет единиц, то стоять рядом они не могут.
Такое число существует одно;
б) если в числе только одна единица, то в нем также едини-
цы стоять рядом не могут. Таких чисел существует 10;
в) если в числе две единицы, то всего возможно
2
9
36
С
=
та-
ких чисел;
г) если в числе три единицы, то количество их:
3
8
56;
С
=
73
д) если в числе четыре единицы, то всего возможно таких
чисел
4
7
35;
С
=
е) если в числе пять единиц, то количество их:
5
6
6.
С
=
Суммируем все эти числа:
k = 1 + 10 + 36 + 56 + 35 + 6 = 144.
Осталось определить число k
3
:
а) если слева и справа нет единиц, то существует только од-
но число из искомых;
б) если слева четыре нуля, то и справа должно быть четыре
нуля. Из списка (1) видно, что если левое число оканчивается
нулем, то после каждого из них справа можно поставить любое
число из второй колонки. Получится 20 искомых чисел. Напри-
мер: 01000 10000, 00010 10000 и т.д. Если же левое число окан-
чивается единицей, то справа можно поставить только четыре
числа из второй колонки:
00001 01000, 00001 00100, 00001 00010, 00001 00001.
Всего получаем 24 искомых числа;
в) если слева две единицы и левое число оканчивается ну-
лем (всего их три), то справа после каждого из них можно по-
ставить любое число из шести. Получаем 18 искомых чисел. Ес-
ли же левое число оканчивается единицей, то справа можно ста-
вить только числа, начинающиеся с нуля. Получаем еще девять
чисел. Всего получаем 27 чисел из искомых.
Суммируем результаты проведенных вычислений:
k
3
= 1 + 24 + 27 = 52.
Находим число k:
k = 46 + 46 + 52 = 144.
Проверочное соотношение (2) выполняется, следовательно,
задача решена правильно.
Пример 4. Сколько существует 9-значных двоичных чисел,
каждое из которых начинается с единицы и оканчивается нулем
и в каждом числе нулей больше, чем единиц?
Решение. Запишем заданное число в виде:
1
∗ ∗ ∗ ∗ ∗ ∗ ∗ 0,
где звездочки можно заменять двоичными знаками.
Представим задачу в виде ряда простых подзадач:
74
а) заменим все звездочки нулями. Тогда в числе будет 8 ну-
лей и одна единица. Следовательно, одно число найдено;
б) одну из звездочек заменим единицей, а все остальные —
нулями. Получим 7 искомых чисел;
в) единицами заменим две звездочки. Тогда в числе будет
три единицы и 6 нулей. Получим
2
7
21
С
=
новых искомых чисел;
г) единицами заменим три звездочки. Тогда в числе будет 4
единицы и 5 нулей. Таких чисел существует
3
7
35;
С
=
д) единицами заменим 4 звездочки. Тогда в числе будет 5
единиц и 4 нуля, т.е. нулей окажется меньше, чем единиц.
Суммируем полученные промежуточные результаты:
1 + 7 + 21 + 35 = 64.
Ответ: 64.
Пример 5. Семизначное двоичное число 1001011 арифме-
тически сложили с двоичным числом a. Сумма 1001011 a
+ ока-
залась восьмизначным числом, т.е. с единицей в старшем разря-
де. Например, при a = 1110011 получается восьмизначное число:
1001011 + 1110011 = 10111110. Найдите число значений a, при
которых сумма 1001011 a
+ является восьмизначным числом,
т.е. содержит единицу в старшем разряде? Найдите a
min
и a
max
.
Решение. Если к числу 1001011 (75 в десятичном представ-
лении) арифметически прибавить его инверсный код 0110100
(десятичное 52), то получим семизначное число 1111111 (127).
Прибавим к инверсному коду единицу. Получим 0110101 (53).
Это наименьшее число, которое в сумме с числом 1001011 (75)
дает восьмизначное число 10000000 (128). Отсюда следует, что
наименьшее значение величины a найдено. Оно равно 0110101
(53), т.е. a
min
= 53.
Наибольшее восьмизначное число состоит из восьми еди-
ниц: 11111111 (255). Следовательно, всего восьмизначных чисел
с единицей в старшем разряде существует:
11111111 – 01111111 = 10000000 (десятичное 128).
Столько же существует и значений a, при которых сумма
a
+
1001011
является восьмизначным числом. Отсюда находим
наибольшее значение величины a:
a
max
= 128 + 52 = 180.
75
Ответ: всего существует 128 значений a, при которых сум-
ма
a
+
1001011
является восьмизначным числом;
a
min
= 53;
a
max
= 180.
Пример 6. Даны два двоичных числа a и b. Число a семи-
значное, число b пятизначное. Эти числа приставили одно к дру-
гому: слева a, справа b. В результате получилось 12-значное
число c (будем называть их c-числами). Сколько существует 12-
значных c-чисел, если в числе a нечетное число единиц и в чис-
ле b — нечетное?
Решение. Разобьем данную задачу не несколько простых
подзадач:
а) пусть в числе a содержится одна единица. Получим 7
значений величины a. Каждому из них можно поставить в соот-
ветствие 16 правых чисел b. Число 16 получено следующим об-
разом. Существует пять 5-значных двоичных чисел, содержа-
щих по одной единице, кроме того, существует
3
5
10
С
= чисел,
содержащих по три единицы и одно число, состоящее из пяти
единиц. В сумме — 16. Таким образом, если слева одна едини-
ца, то всего возможно 7
⋅16 = 112 c-чисел;
б) пусть в числе a содержится три единицы. Таких чисел
существует
3
7
35.
С
=
Каждому из них можно поставить в соот-
ветствие 16 правых чисел. Следовательно, получаем еще 560 c-
чисел;
в) допустим, что в числе a пять единиц. Тогда получим
5
7
16
336
С
⋅ =
c-чисел;
г) в числе a может быть 7 единиц. Такое число существует
только одно. Следовательно, получаем еще 16 новых c-чисел.
Суммируем полученные результаты:
112 + 560 + 336 + 16 = 1024.
Ответ: 1024.
Этот же ответ можно получить гораздо более коротким пу-
тем. Число a семизначное. Всего их существует 128. Среди них
в половине чисел четное число единиц, тогда в 64 числах — не-
четное. Из 32 правых чисел 16 содержат нечетное число единиц.
Тогда всего возможно 64
⋅16 = 1024 c-чисел.