Материал: Дискретная математика. Методичка. Кацаран

Пример 14.

Комиссия состоит из

n

человек. Документы хранятся

в сейфе. Сколько замков должен иметь сейф, сколько ключей для них
нужно изготовить и как распределить между членами комиссий, чтобы
доступ к сейфу был возможен тогда и только тогда, когда соберутся
вместе не менее

m

человек комиссии (

m

≤

n

+ 1

,

m

— наименьшее

число членов, при котором возможен доступ к сейфу)?

Решение

. Какие бы

m

−

1

членов комиссии не собрались, должен

найтись замок, который они не смогут открыть, но ключ от этого замка
имеется у каждого из

n

−

(

m

−

1) =

n

−

m

+ 1

>

0

остальных членов

комиссии (появление кого-нибудь из которых дает возможность открыть
сейф). Следовательно, число замков равно

C

m

−

1

n

; число ключей равно

(

n

−

m

+ 1)

·

C

m

−

1

n

. Замечание в условии задачи является существен-

ным, так как доступ к замкам сейфа имеют только

n

человек, которые

являются членами комиссии.

Пример 15.

Сколькими способами можно расставить в шеренгу

n

различных львов и

m

различных тигров так, чтобы никакие два тигра

не шли друг за другом (

m

≤

n

+ 1

)?

Решение

. Расставим сначала всех львов, оставив между каждыми

двумя промежуток. Это можно сделать

P

(

n

)

способами, так как все

львы разные, если бы все львы были одинаковы, то расставить их в ряд
можно было одним способом. Теперь для расстановки тигров имеется

(

n

+ 1)

место (либо одно впереди всех львов, либо одно после всех, либо

между ними —

(

n

−

1)

). Так как порядок тигров существенен (они все

разные), то число их способов расстановки равно

A

m

n

+1

. Следовательно,

общее число способов расстановки хищников найдем с помощью правила
произведения

P

(

n

)

·

A

m

n

+1

. Замечание в условии задачи (

m

≤

n

+1

) явля-

ется необходимым, в противном случае какие-нибудь два тигра окажутся
рядом.

§ 11. Задачи и упражнения для самостоятельной работы

3.1. Какого типа 4-выборки, если выбираются из десяти претенден-

тов: а) четыре кандидата на конференцию; б) президент, вице-президент,
казначей и ученый секретарь научного общества?

3.2. Из ящика с 70 разными шарами вынимается 5 шаров. Какого

типа 5-выборка? Ответ обосновать.

3.3. Какого типа 7-выборка при совершении покупки семи пирож-

ных, если в магазине имеется четыре их сорта?

3.4. На шахматной доске расставлены: а) восемь одинаковых фи-

гур; б) восемь различных фигур. К какому типу относятся 8-выборки в
случаях а) и б)?

41

3.5. Из множества цифр

{

0

,

1

,

2

, . . . ,

9

}

составляются различные на-

боры чисел по пять цифр в каждом. Какого типа выборки представляют
собой пятизначные числа?

3.6. Из множества

A

=

{

a, b, c, d

}

составить: а) упорядоченные 2-

выборки без повторений; б)неупорядоченные 2-выборки без повторений.
Сколько их всего может быть?

3.7. Составляются слова длины 4 из 32 букв русского алфавита так,

что две соседние буквы этих слов различны. Какого характера эти вы-
борки? Найти число таких наборов слов.

3.8. Из цифр 1, 2, 3, 4 составьте неупорядоченные 2-выборки с по-

вторениями. Сколько всего их? Перечислите.

3.9. Имеется 10 билетов денежно-вещевой лотереи и 15 билетов худо-

жественной лотереи. Сколькими способами можно выбрать один билет?

3.10. Сколькими способами можно подарить сувенир из имеющихся

6 авторучек, 7 репродукций и 3 альбомов? (В задаче предполагается, что
предметы различные.)

3.11. В городе работают 4 музея, 3 театра и 10 кинотеатров. Сколько

вариантов для организации культпохода в воскресенье?

3.12. Сколько существует вариантов поездки к морю, если туда мож-

но добраться тремя авиарейсами, пятью автодорогами или по железной
дороге?

3.13. Сколькими способами можно купить один пирожок, если в про-

даже 7 пирожков с мясом, 10 пирожков с повидлом и 12 пирожков с
капустой?

3.14. Сколькими способами можно указать на шахматной доске два

квадрата: белый и черный? А если нет ограничения в цвете квадратов?

3.15. Сколькими способами можно выбрать на шахматной доске бе-

лый и черный квадраты, не лежащие на одной горизонтали и вертикали?

3.16. Имеется три волчка с 6, 8 и 10 гранями соответственно. Сколь-

кими различными способами они могут упасть? А если известно, что по
крайней мере два волчка упали на одну сторону, помеченную цифрой

1

?

3.17. Сколькими способами можно выбрать из полной колоды карт

(52 карты) по одной карте каждой масти?

3.18. В корзине лежат 8 различных яблок и 7 различных груш.

Сколькими способами можно взять плод из корзины?

3.19. Сколько существует двухзначных чисел в десятизначной си-

стеме счисления, в которых нет одинаковых цифр?

3.20. Сколько существует нечетных трехзначных чисел?
3.21. На ферме есть 20 овец и 24 козы. Сколькими способами можно

42

выбрать одну овцу и одну козу? Если такой выбор уже сделан, сколькими
способами можно сделать его еще раз?

3.22. Сколькими способами можно выбрать по одному экземпляру

каждого учебника, если имеется 3 экземпляра учебника алгебры, 7 экзем-
пляров учебника геометрии и 10 экземпляров учебника информатики?

3.23. Сколькими способами можно выбрать из натуральных чисел

от 1 до 20 два числа так, чтобы их сумма была нечетным числом?

3.24. Имеется 5 видов конвертов без марок и 4 вида марок. Сколь-

кими способами можно выбрать конверт и марку для посылки письма?

3.25. Сколькими способами можно выбрать согласную и гласную

буквы из слов

здание

? Из слова

кабинет

?

3.26. В корзине лежат 12 яблок и 10 груш. Мальчик выбирает из

нее яблоко или грушу, после чего девочка берет и яблоко, и грушу. В
каком случае девочка имеет большую свободу выбора: если мальчик взял
яблоко или грушу?

3.27. Сколькими способами можно совершить круговой рейс из А в

В и обратно, если на обратном пути выбирать новую дорогу и известно,
что А и В соединены семью дорогами?

3.28. У некоторых народов принято давать детям несколько имен.

Сколькими способами можно назвать ребенка, если ему дают не более
трех имен, а общее число имен равно 300?

3.29. Сколько различных натуральных делителей имеет число

n

= 2

7

·

3

10

·

7

15

·

11

9

?

3.30. Сколько есть шестизначных чисел, начинающихся с двух оди-

наковых цифр?

3.31. Сколько есть пятизначных чисел, в каждом из которых сосед-

ние цифры различны?

3.32. Сколько есть пятизначных чисел, делящихся на

4

, в записи

которых не используются цифры

0

,

4

,

6

,

8

?

3.33. Сколько есть шестизначных чисел, в каждом из которых нет

одинаковых цифр, а вторая и четвертая цифры нечетны?

3.34. Сколько существует нечетных пятизначных чисел, в которых

нет одинаковых чисел?

3.35. Из цифр составляются всевозможные числа, каждое из кото-

рых содержит не менее трех цифр. Сколько таких чисел можно соста-
вить, если повторение цифр в числах запрещено?

3.36. Сколько всего костей домино, если используется для их обра-

зования 7 цифр: 0, 1, 2, 3, 4, 5, 6. Ответ обосновать.

3.37. Сколько существует всего двухзначных чисел, составленных из

цифр

0

,

1

, . . . ,

9

?

43

3.38. Сколько неотрицательных целых чисел меньше миллиона со-

стоит только из цифр 1, 2, 3, 4?

3.39. Сколько существует различных пятизначных четных чисел, ко-

торые начинаются цифрой 2 и оканчиваются цифрой 4, если использу-
ются цифры 1, 2, 3, 4, 5?

3.40. Сколько различных четырехзначных чисел, делящихся на 4,

можно составить из цифр 1, 2, 3, 4, 5?

3.41. Сколько есть пятизначных чисел, оканчивающихся двумя се-

мерками?

3.42. Сколько есть перестановок цифр 0, 1, 2,

. . .

, 9, в которых цифра

3 занимает третье место, а цифра 5 — пятое?

3.43. Сколько существует шестизначных телефонных номеров, со-

стоящих из различных цифр?

3.44. Сколько имеется пятизначных чисел, которые делятся на 5?
3.45. Сколько имеется пятизначных чисел, у которых все цифры

нечетные?

3.46. У рояля 88 клавиш. Сколькими способами можно извлечь по-

следовательно: а) 4 звука; б) 4 разных звука?

3.47. Сколькими способами можно выбрать 6 одинаковых или раз-

ных пирожных в кондитерской, где продаются 11 разных сортов пирож-
ных?

3.48. Сколькими способами можно выписать в колонку фамилии

30

учеников?

3.49. Сколькими способами можно расставить на шахматной доске

8 одинаковых ладей так, чтобы никакие две из них не били друг друга?

3.50. Переставляются буквы слов: а)

март

, б)

мама

. Сколько

получается различных перестановок? Перечислите их. К какому типу
выборки можно отнести эти комбинации букв?

3.51. Сколько есть пятизначных чисел, в которых каждая цифра

встречается по одному разу, а цифра

0

следует непосредственно за циф-

рой

1

?

3.52. Сколько можно составить слов длины

k

из 32 букв русского

алфавита? Рассмотреть случай

k

= 2

,

3

,

4

.

3.53. В забеге участвуют 5 человек. Сколькими способами могут рас-

пределиться 2 первых места?

3.54. Сколькими способами могут 7 человек встать в очередь за би-

летами в театральной кассе?

3.55. Сколькими различными способами 2 друга могут одновременно

посетить кого-либо из своих общих трех знакомых?

3.56. В некотором государстве не было двух жителей с одинаковым

44

набором зубов. Какова наибольшая численность этого государства?

3.57. В условии задачи примера 5 одна полоса обязательно должна

быть красного цвета.

3.58. В одной из первых поколений ЭВМ

Стрела

ОЗУ имело

2048 ячеек, каждая ячейка состояла из 43 разрядов. Какое максимальное
количество различных чисел в двоичной системе счисления можно было
поместить в ОЗУ?

3.59. Абитуриенту необходимо сдать 4 экзамена за 10 дней. Скольки-

ми способами можно составить ему расписание, если в один день можно
сдавать только один экзамен?

3.60. Четверо студентов сдают экзамен. Сколькими способами могут

быть поставлены им оценки, если известно, что никто не получил оценки

неудовлетворительно

?

3.61. Сколько словарей надо издать, чтобы можно было выполнять

переводы с любого из пяти языков на любой другой из этих пяти языков?
На сколько больше словарей надо издать, если число различных языков
равно 10?

3.62. Сколько существует четырехзначных натуральных чисел, у ко-

торых все цифры различные?

3.63. Номер машины состоит из трех букв русского алфавита и трех

цифр. Сколько можно составить различных номеров автомашин?

3.64. В комнате общежития живут трое студентов. У них есть 4

разные чашки, 5 разных блюдец и 6 разных чайных ложек. Скольки-
ми способами они могут накрыть стол для чаепития (каждый студент
получает одну чашку, одно блюдце и одну ложку)?

3.65. Из 20 студентов надо назначить 5 дежурных. Сколькими спо-

собами это можно сделать?

3.66. Найти число всех подмножеств множества, состоящего из

n

элементов.

3.67. Волк, догоняя зайца, пробежал по лестнице из

7

ступенек,

возможно, перепрыгивая через некоторые. Сколькими способами он мог
это сделать?

3.68. Сколькими способами можно составить бригаду из четырех

плотников, если имеются предложения от 10 человек?

3.69. Сколькими способами можно выбрать

3

дежурных из

5

уча-

щихся, если: а) они все дежурят в столовой; б) один дежурный идет в
столовую, второй – в раздевалку, третий – мыть полы в класс?

3.70. Сколькими способами пять девушек и трое юношей могут раз-

биться на две команды по четыре человека в команде, если в каждой
команде должно быть хотя бы по одному юноше?

45