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

Пример 14. Комиссия состоит из n человек. Документы хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как распределить между членами комиссий, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся вместе не менее m человек комиссии ( m ≤ n + 1 , m наименьшее число членов, при котором возможен доступ к сейфу)?

Решение. Какие бы m − 1 членов комиссии не собрались, должен найтись замок, который они не смогут открыть, но ключ от этого замка имеется у каждого из n − (m − 1) = n − m + 1 > 0 остальных членов комиссии (появление кого-нибудь из которых дает возможность открыть сейф). Следовательно, число замков равно Cnm−1 ; число ключей равно (n − m + 1) · Cnm−1 . Замечание в условии задачи является существенным, так как доступ к замкам сейфа имеют только n человек, которые являются членами комиссии.

Пример 15. Сколькими способами можно расставить в шеренгу n различных львов и m различных тигров так, чтобы никакие два тигра не шли друг за другом ( m ≤ n + 1 )?

Решение. Расставим сначала всех львов, оставив между каждыми двумя промежуток. Это можно сделать P (n) способами, так как все львы разные, если бы все львы были одинаковы, то расставить их в ряд можно было одним способом. Теперь для расстановки тигров имеется (n + 1) место (либо одно впереди всех львов, либо одно после всех, либо между ними (n − 1) ). Так как порядок тигров существенен (они все разные), то число их способов расстановки равно Amn+1 . Следовательно, общее число способов расстановки хищников найдем с помощью правила произведения P (n)·Amn+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 = 27 · 310 · 715 · 119 ?

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

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 человек получат свои шляпы. Рассмотреть все

3.95. Найти натуральное число n , удовлетворяющее уравнению

Cn5 = 2Cn5−1.

3.96. Доказать следующие свойства биноминальных коэффициен-

тов:

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 групп: чтобы в первой группе содержалось n1 предметов, во второйn2 предметов, . . . , в k -й группе nk предметов; порядок групп существенен, а порядок элементов внутри группы не играет роли.

3.127. Сколько целых чисел, которые не делятся ни на 2, ни на 3, ни на 5, ни на 7?

3.128. Найти число целых положительных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 3 , 5 и 7 .

3.129. Найти число целых положительных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 6 , 10 и 15 .

3.130. Показать, что если n = 30m , то число целых чисел, не превосходящих n и не делящихся ни на одно из чисел 6 , 10 и 15 , равно

22m .

3.131. Показать, что количество натуральных чисел, делящихся на n и не превосходящих x , равно [ nx ] .

3.132. Сколько чисел среди первых 100 натуральных не делится ни на 2, ни на 3, ни на 5?

49

3.133. Сколько чисел среди первых 100 натуральных не делится ни на 3, ни на 4, ни на 5?

Примечание: Количество натуральных чисел, делящихся на m и не превосходящих a , равно целой части [ ma ] числа ma .

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