ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 6260
Скачиваний: 13
66
Пример 5. Ребенок, не умеющий читать, рассыпал состав-
ленное из букв разрезной азбуки слово «искусство», выбрал из
них четыре карточки и расположил их в один ряд. Найти веро-
ятность того, что у него получится слово «куст».
Решение. Рассмотрим четыре события: A — выбрана буква
«к», B — выбрана буква «у», C — выбрана буква «с», D — вы-
брана буква «т». Найдем их вероятности. Вероятность события
A равна: p(A) = 1/9. Так как событие A состоялось, то среди рас-
сыпанных осталось 8 карточек. Следовательно, вероятность со-
бытия B равна: p(B) = 1/8. Теперь осталось 7 карточек и вероят-
ность события C равна: p(C) = 3/7. Осталось 6 карточек. Вероят-
ность события D равна: p(D) = 1/6. По правилу произведения
вероятностей получаем:
1 1 3 1
1
.
9 8 7 6
1008
p
= ⋅ ⋅ ⋅ =
Ответ: 1/1008.
Пример 6. Из колоды, в которой 36 карт, наугад вынимают
две карты. Найти вероятность того, что обе они будут пиковой
масти.
Решение. Две карты из 36 можно извлечь
2
36
630
С
=
спосо-
бами. Следовательно, знаменатель найден. В колоде из 36 карт
содержится 9 карт пиковой масти. Две из них можно извлечь
2
9
36
С
=
способами. Искомая вероятность равна 36/630. После
сокращения получаем p = 2/35.
Ответ: 2/35.
Пример 7. Некто задумал 10-значное двоичное число (чис-
ла могут начинаться с нуля). Найти вероятность того, что в чис-
ле содержится хотя бы один нуль и хотя бы одна единица.
Решение. Всего возможно 1024 10-значных двоичных чи-
сел. Существует одно число, состоящее из десяти нулей, и одно
число, состоящее из десяти единиц. Во всех остальных 1022
числах содержится хотя бы один нуль и хотя бы одна единица.
Следовательно, искомая вероятность равна p = 1022/1024. После
сокращения на 2 p = 511/ 512.
Ответ: 511/ 512.
67
4 ᇉ‡˜Ë ËÁ письменной ÍÓÌÚðÓθÌÓÈ ð‡·ÓÚ˚.
íÂχ 9: «äÓÏ·Ë̇ÚÓðË͇»
Прежде чем решать комбинаторные задачи из данной кон-
трольной работы, рекомендуется просмотреть решения всех ни-
жеприведенных задач. Знакомство с ними может существенно
снизить трудозатраты на выполнение контрольной работы и по-
высит вероятность того, что решение задачи будет верным.
Пример 1. Десятизначное двоичное число разделили на две
неравные части — левую и правую. Левая часть состоит из че-
тырех знаков, правая — из шести. Сколько существует таких
чисел, в каждом из которых слева единиц больше, чем справа?
Решение. В левой части может быть 0 единиц (т.е. ни од-
ной), либо одна, либо две, либо три, либо четыре. В соответст-
вии с этим разобьем задачу на пять более простых задач:
а) в левой части нет единиц. В этом случае нет ни одного
десятизначного двоичного числа, удовлетворяющего условию
задачи;
б) в левой части одна единица, тогда в правой части долж-
ны быть только нули. Всего существует 4 таких числа:
0001 000000; 0010 000000; 0010 000000; 1000 000000;
в) в левой части две единицы, тогда в правой может быть
либо 0 единиц, либо одна единица. Две единицы в левой части
дают
2
4
6
C
= четырехзначных чисел. Столько же существует
искомых чисел, если в правой части единиц нет. Одна единица в
правой части может располагаться 6 способами. Тогда сущест-
вует 6
⋅6 = 36 искомых чисел. Одно их них: 0101 001000. Таким
образом, всего существует 36 + 6 = 42 числа, в каждом из кото-
рых слева две единицы, а справа нет единиц или 1 единица;
г) слева три единицы, тогда справа их может быть либо 0,
либо 1, либо 2. Три единицы слева могут располагаться четырь-
мя способами. Если справа единиц нет, то получаем 4 искомых
числа. Если справа одна единица, то существует 4
⋅6 = 24 иско-
мых числа. Одно из них: 1011 010000. Если справа две единицы,
то существует
2
6
4
60
C
=
искомых чисел. Одно из них имеет вид:
1011 001010. Таким образом, всего получаем:
68
4 + 24 + 60 = 88,
т.е. существует 88 чисел, у которых слева три единицы, а справа
0, либо 1, либо 2 единицы;
д) слева четыре единицы. Справа же может быть либо
0 единиц, либо 1, либо 2, либо 3. Четыре единицы слева
дают только один вариант их расположения. Если справа
единиц нет, то получаем одно число из искомых. Оно име-
ет вид: 1111 000000. Если справа одна единица, то воз-
можно 6 искомых чисел. Одно из них: 1111 001000. Если
справа две единицы, то существует
2
6
15
C
=
искомых чисел.
Одно из них: 1111 010100. Если справа три единицы, то
возможно
3
6
20
C
=
искомых чисел. Сложим полученные ре-
зультаты:
1 + 6 + 15 + 20 = 42.
То есть всего существует 42 числа, у которых слева четыре
единицы, а справа 0, либо 1, либо 2, либо 3 единицы.
Сложим числа, полученные в результате решения всех пяти
простых задач:
0 + 4 + 42 + 88 + 42 = 176.
Ответ: 176.
Ответ к данной задаче можно проверить. Для этого решим
еще две задачи:
1) сколько существует чисел, в каждом из которых слева
столько же единиц, сколько и справа?
2) сколько существует чисел, в каждом из которых слева
единиц меньше, чем справа?
Сумма ответов ко всем трем задачам должна быть равной
1024. Именно столько всего существует десятизначных двоич-
ных чисел.
Решаем первую проверочную задачу. Если слева единиц
нет, то их не должно быть и справа. Такое число существует
только одно: 0000 000000.
Если слева одна единица, то и справа должна быть только
одна. Например: 0100 000010. Всего возможно 4
⋅6 = 24 таких
числа.
69
Если слева и справа по две единицы, то всего таких чисел
существует
2
2
4
6
6 15
90.
C
C
⋅
= ⋅ =
Если слева и справа по три единицы, то количество таких
чисел равно
3
3
4
6
4 20
80.
C
C
⋅
= ⋅
=
Если слева и справа по четыре единице, то количество та-
ких чисел равно
4
4
4
6
1 15 15.
C
C
⋅
= ⋅ =
Сложим полученные числа: 1 + 24 + 90 + 80 + 15 = 210.
Таким образом, ответ к первой проверочной задаче: 210.
Решаем вторую проверочную задачу. Как и в исходной за-
даче, рассмотрим пять простых задач:
а) слева единиц нет. Тогда справа может быть одна единица
(таких чисел 6), либо две (таких чисел существует
2
6
15
C
=
), ли-
бо три (количество их
3
6
20
C
=
), либо четыре (таких чисел суще-
ствует
4
6
15
C
=
), либо пять (
5
6
6
C
= ), либо шесть (одно число).
Всего: 6 + 15 + 20 + 15 + 6 + 1 = 63;
б) слева одна единица. Она может располагаться четырьмя
вариантами среди четырех разрядов. Каждому из них соответст-
вует справа две единицы (15 чисел), либо три (20 чисел), либо
четыре (15 чисел), либо пять (6 чисел), либо шесть (одно число).
Всего: 4
⋅(15 + 20 + 15 + 6 + 1) = 228;
в) слева две единицы. Существует 6 четырехзначных дво-
ичных чисел, содержащих по две единицы. Каждому из них со-
ответствует справа три единицы (20 чисел), либо четыре (15 чи-
сел), либо пять (6 чисел), либо шесть (одно число). Всего полу-
чаем 6
⋅(20 + 15 + 6 + 1) = 252 числа;
г) слева три единицы. Существует 4 четырехзначных дво-
ичных числа, содержащих по три единицы. Каждому из них со-
ответствует справа четыре единицы (15 чисел), либо пять (6 чи-
сел), либо шесть (одно число). Всего 4
⋅(15 + 6 + 1) = 88 чисел;
д) слева четыре единицы. Четырехзначное такое число су-
ществует только одно. Справа возможно пять единиц (6 чисел)
либо шесть (одно число). Всего 6 + 1 = 7 чисел.
Сложим полученные числа и получим ответ ко второй
проверочной задаче: 63 + 228 + 252 + 88 + 7 = 638.
70
Таким образом, существует 176 чисел, в которых слева боль-
ше единиц, чем справа; существует 210 чисел, в которых слева
столько же единиц, сколько и справа; существует 638 чисел, в ко-
торых слева меньше единиц, чем справа. Сложим эти три числа:
176 + 210 + 638 = 1024.
Отсюда следует, что исходная задача решена правильно.
Пример 2. В n-значном двоичном числе точно три едини-
цы, которые нигде рядом не стоят. Известно, что существует 220
таких чисел. Найдите n.
Решение. Если в n-значном числе три единицы, то число
нулей в нем равно
3.
n
− Запишем эти
3
−
n
нулей в один ряд.
Между нулями, а также слева и справа от них можно ставить по
одной единице. Всего возможно
2
−
n
таких мест, т.е. на едини-
цу больше, чем нулей. При этом всякий раз будут получаться
числа, в которых нет рядом стоящих единиц. Так как в данном
случае имеется три единицы, то расположить их можно по
2
−
n
местам k способами, где
3
2
(
2)!
(
2)!
.
3!(
2
3)!
3!(
5)!
n
n
n
k
C
n
n
−
−
−
=
=
=
− −
−
Запишем это выражение следующим образом:
(
2)!
(
5)!(
4)(
3)(
2)
.
3!(
5)!
3!(
5)!
n
n
n
n
n
k
n
n
−
−
−
−
−
=
=
−
−
После сокращения получаем:
.
!
3
)
2
)(
3
)(
4
(
−
−
−
=
n
n
n
k
Число k известно. Оно равно 220. Получаем уравнение:
.
220
!
3
)
2
)(
3
)(
4
(
=
−
−
−
n
n
n
Запишем его в виде
.
3
2
11
2
5
2
6
220
)
2
)(
3
)(
4
(
⋅
⋅
⋅
⋅
⋅
=
⋅
=
−
−
−
n
n
n
Раскрывать скобки нет необходимости. Слева записаны три
числа в порядке возрастания на единицу. Из чисел правой части
составим такие же три числа. Это можно сделать следующим
образом: 10, 11, 12. Решаем уравнение n – 2 = 12, откуда получа-
ем: n = 14.
Ответ: n = 14.