Материал: Дискретная математика. Методичка. Кацаран
3.71. Сколькими способами можно расселить 9 студентов в комнаты,
каждая из которых рассчитана на трех человек?
3.72. Сколькими способами можно составить набор из 8 пирожных,
если имеется 4 сорта пирожных?
3.73. Сколькими способами можно выбрать
13
из
52
стандартных
карт, различая их только по масти?
3.74. Сколько всего существует результатов опыта, заключающегося
в подбрасывании двух одинаковых игральных костей?
3.75. Сколько различных подмножеств из трех элементов имеет мно-
жества
A
=
{
1
,
2
,
3
,
4
,
5
}
,
B
=
{♣
,
♦
,
♥
,
♠}
?
3.76. Сколькими способами из трех спортивных обществ, насчиты-
вающих соответственно 40, 40 и 60 человек, можно выбрать команды по
5 человек для участия в соревнованиях?
3.77. Из группы в 20 человек каждую ночь выделяется наряд из трех
человек. Сколько существует вариантов составления наряда?
3.78. Из группы, состоящей из 7 мужчин и 4 женщин, надо выбрать
6 человек так, чтобы среди них было не менее двух женщин. Сколькими
способами это можно сделать?
3.79. Сколькими способами можно выбрать 12 человек из 17, если
данные двое человек из этих 17 не могут быть выбраны вместе?
3.80. Сколько трехбуквенных слов можно образовать из букв слова
арбуз
?
3.81. Из
20
учащихся кружка математики четверых необходимо по-
слать на олимпиаду. Сколькими способами можно составить команду?
3.82. В меню столовой имеется
4
первых,
5
вторых и
6
третьих
блюд. Сколькими способами можно выбрать обед из одного первого, од-
ного второго и одного третьего блюда?
3.83. Сколькими способами можно расставить белые фигуры (2 ко-
ня, 2 слона, 2 ладьи, ферзя и короля) на первой линии шахматной доски?
3.84. Четыре автора должны написать книгу из 17 глав, причем пер-
вый и третий должны написать по 5 глав, второй — 4 главы, а четвертый
— 3 главы книги. Сколькими способами можно распределить главы меж-
ду авторами?
3.85. Сколько существует перестановок элементов
1
,
2
, . . . , n
, в ко-
торых элемент 1 находится не на своем месте?
3.86. Сколько ожерелий можно составить из семи бусинок разных
размеров?
3.87. Сколько различных браслетов можно сделать из четырех оди-
наковых рубинов, пяти одинаковых сапфиров и шести одинаковых изу-
мрудов, если в браслете должны быть все 15 камней? Сколькими спосо-
46
бами можно из этих камней выбрать три камня для кольца?
3.88. Сколькими способами можно разбить
(
n
+
m
+
p
)
предметов
на три группы так, чтобы в одной было
n
, в другой
m
, а в третьей
p
предметов?
3.89. Сколькими способами можно переставить буквы в слове а)
математика
; б)
комбинаторика
?
3.90. Сколькими способами можно переставить цифры числа
a
) 12 341 234;
б
) 12 345 612
.
3.91. Сколько существует вариантов того, что три человека, сдавшие
свои шляпы в гардероб, не получат свою шляпу обратно?
3.92. Четыре человека сдают свои шляпы в гардероб. Предполагая,
что шляпы возвращаются наугад, найти число случаев и вероятность
того, что в точности
k
человек получат свои шляпы. Рассмотреть все
значения
k
(
k
= 1
,
2
,
3
,
4
).
3.93. Возможно ли равенство
P
n
= 36
A
2
n
−
1
, если да, то при каких
n
?
3.94. Доказать, что
C
m
−
1
n
+
m
−
1
=
H
n
m
.
3.95. Найти натуральное число
n
, удовлетворяющее уравнению
C
5
n
= 2
C
5
n
−
1
.
3.96. Доказать следующие свойства биноминальных коэффициен-
тов:
1
. C
n
n
=
C
0
0
;
2
. C
k
n
=
C
n
−
k
n
;
3
. C
k
n
=
C
k
−
1
n
−
1
+
C
k
n
−
1
;
4
. C
k
n
·
C
m
−
k
n
−
k
=
C
k
m
·
C
m
n
;
5
.
P
n
k
=0
C
k
n
= 2
n
;
6
.
P
n
k
=0
(
−
1)
k
C
k
n
= 0;
7
.
P
n
k
=0
C
2
k
n
=
P
n
k
=0
C
2
k
+1
n
,
k
= 1
, n.
3.97. Сколькими способами могут 4 человека разместиться в четы-
рехместном купе железнодорожного вагона?
3.98. Найти число простых чисел, не превосходящих 250.
3.99. У одного человека есть 7 книг, у другого 9. Сколькими спосо-
бами они могут обменять книгу одного на книгу другого, если все книги
различны? Та же задача, но меняются две книги одного на две книги
другого.
3.100. Автомобильные номера состоят из одной, двух или трех букв
и четырех цифр. Найти число таких номеров, если используются 27 букв
русского алфавита.
3.101. Сколькими способами можно составить список из 7 студентов?
47
3.102. Из спортклуба, насчитывающего 30 человек, надо выбрать
команду из 4 человек для участия в беге на 1000 м. Сколькими способами
можно это сделать? А если нужно выбрать команду из четырех человек
для участия в эстафете
100 + 200 + 400 + 800
?
3.103. Сколько различных четырехзначных чисел можно составить
из семи цифр
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
, если каждая из них может повторяться
несколько раз?
3.104. Сколько пятизначных чисел можно составить из цифр
1
,
2
,
3
,
4
,
5
,
6
,
7
, если никакую цифру не использовать более одного раза?
3.105. На танцевальном вечере присутствуют 12 девушек и 15 юно-
шей. Сколькими способами можно выбрать из них четыре пары для тан-
цев?
3.106. Изучаются 10 учебных предметов. В понедельник надо поста-
вить 6 уроков, причем все разные. Сколькими способами можно соста-
вить расписание на понедельник?
3.107. Сколькими способами читатель может выбрать 3 разные кни-
ги из пяти?
3.108. Сколькими способами можно переставить буквы в слове
тик-
так
так, чтобы никакие буквы не шли друг за другом? То же самое для
слова
тартар
.
3.109. Сколькими способами можно переставить цифры числа
12 341 234 так, чтобы никакие две одинаковые цифры не шли друг за
другом.
3.110. Сколько разных чисел можно составить, переставляя цифры
в числе 987 654? Напишите эти цифры.
3.111. В комнате
n
лампочек. Сколько всего разных способов осве-
щения комнаты, при которых горит ровно
k
лампочек? Сколько всего
может быть различных способов освещения данной комнаты?
3.112. Сколькими способами можно разместить 4 разные книги на
полке?
3.113. Сколько можно составить перестановок из
n
элементов, в
которых данные два элемента не стоят рядом?
3.114. Студенту надо сдать 4 зачета за 8 дней. Сколькими способа-
ми можно это сделать? А если последний зачет обязательно сдавать на
восьмой день?
3.115. В магазине на полке стоят 15 кассет с видеофильмами. Сколь-
кими способами можно выбрать 3 видеофильма так, чтобы никакие два
из них не стояли рядом?
3.116. Сколькими способами можно рассадить
n
гостей за круглый
стол?
48
3.117. На собрании должны выступить 4 человека А, В, С, Д. Сколь-
кими способами их можно разместить в списке ораторов, если В не может
выступать до того момента, пока не выступит А?
3.118. Сколько натуральных чисел в
n
-й системе счисления можно
записать
k
знаками?
3.119. Сколько неудачных попыток может быть сделано человеком,
не знающим секретного кода, составленного из пяти цифр, и подбираю-
щего его наудачу?
3.120. Сколькими способами можно сфотографировать 4 танкистов,
4 летчиков и 2 артиллеристов, поставив их в один ряд так, чтобы пред-
ставители одного рода войск стояли рядом?
3.121. Сколько различных слов получится в результате перестановки
слов: а)
уравнение
, б)
вероятность
?
3.122. Сколько слов можно составить из 12 букв: четырех букв
a
,
четырех букв
б
, двух букв
в
и двух букв
г
?
3.123. Сколькими способами можно распределить
n
предметов сре-
ди
k
лиц?
3.124. Имеется 3 курицы, 4 утки и 2 гуся. Сколько имеется комби-
наций для выбора нескольких птиц так, чтобы среди выбранных были и
куры, и гуси, и утки?
3.125. Сколькими способами можно сервировать стол на четверых
человек, если имеется 6 разных тарелок, 8 разных вилок и 7 разных
ножей?
3.126. Определить количество способов разбиения
n
предметов на
k
групп: чтобы в первой группе содержалось
n
1
предметов, во второй
—
n
2
предметов,
. . .
, в
k
-й группе —
n
k
предметов; порядок групп
существенен, а порядок элементов внутри группы не играет роли.
3.127. Сколько целых чисел, которые не делятся ни на 2, ни на 3, ни
на 5, ни на 7?
3.128. Найти число целых положительных чисел, не превосходящих
1000
и не делящихся ни на одно из чисел
3
,
5
и
7
.
3.129. Найти число целых положительных чисел, не превосходящих
1000
и не делящихся ни на одно из чисел
6
,
10
и
15
.
3.130. Показать, что если
n
= 30
m
, то число целых чисел, не пре-
восходящих
n
и не делящихся ни на одно из чисел
6
,
10
и
15
, равно
22
m
.
3.131. Показать, что количество натуральных чисел, делящихся на
n
и не превосходящих
x
, равно
[
x
n
]
.
3.132. Сколько чисел среди первых 100 натуральных не делится ни
на 2, ни на 3, ни на 5?
49
3.133. Сколько чисел среди первых 100 натуральных не делится ни
на 3, ни на 4, ни на 5?
Примечание: Количество натуральных чисел, делящихся на
m
и
не превосходящих
a
, равно целой части
[
a
m
]
числа
a
m
.
3.134. Определить число всех дней с плохой погодой, если 12 дней
шел дождь, 8 дней дул ветер, 4 дня было холодно, причем 5 дней были
и дождливыми, и ветреными, 3 дня — дождливыми и холодными, 2 дня
— ветреными и холодными, 1 день — дождливый, ветреный и холодный,
а дней с хорошей погодой не было за данный период.
3.135. В группе 35 учащихся. Из них 20 посещают математический
кружок, 11 – физический, 10 учащихся не посещают ни одного из этих
кружков. Сколько учащихся посещают оба кружка? Сколько учащихся
посещают только математический кружок?
3.136. На одной из кафедр университета работают тринадцать че-
ловек, причем каждый из них знает хотя бы один иностранный язык.
Десять человек знают английский, семь – немецкий, шесть – француз-
ский. Пять знают английский и немецкий, четыре – английский и фран-
цузский, три – немецкий и французский. Сколько человек знают все три
языка? Сколько человек знают ровно два языка? Сколько человек знают
только английский язык?
3.137. В отделе НИИ работают несколько сотрудников, знающих хо-
тя бы один иностранный язык. Из них 6 человек знают английский, 6
– немецкий, 7 – французский, 4 – английский и немецкий, 3 – француз-
ский и немецкий, 2 – французский и английский, 1 человек знает все три
языка. Сколько человек работает в отделе? Сколько из них знают только
английский язык? Сколько человек знают только один язык?
3.138. Староста одного класса дал следующие сведения об учениках:
В классе учатся 45 человек, в том числе 25 мальчиков; 30 учеников
учатся на хорошо и отлично, в том числе 16 мальчиков. Спортом зани-
маются 28 учеников, в том числе 18 мальчиков и 17 школьников, которые
учатся на хорошо и отлично. 15 мальчиков учатся на хорошо и отлично
и занимаются спортом
. Докажите, что в этих сведениях есть ошибка.
3.139. В магазине лежат 6 экземпляров романа И.С. Тургенева
Ру-
дин
, 3 экземпляра его же романа
Дворянское гнездо
и 4 экземпляра
романа
Отцы и дети
. Кроме того, есть 5 томов, содержащих рома-
ны
Рудин
и
Дворянское гнездо
, и 7 томов, содержащих романы
Дворянское гнездо
и
Отцы и дети
. Сколькими способами можно
сделать покупку, содержащую по одному экземпляру каждого из этих
романов? Та же задача, если, кроме того, в магазине есть 3 тома, в ко-
торые входят романы
Рудин
и
Отцы и дети
.
50