Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 55
Текст из файла (страница 55)
В 5г каждый элемент, содержащий 6, имеет ее либо первой, либо второй цифрой. Если 6 — вторая цифра, то существуют 8 различных чисел, поскольку первое число не может быть 0 или 6. Если 6 — первая цифра, то таких чисел 9, поскольку вторая цифра не может быть 6. Таким образом, 5г содержит 8+ 9 = 17 элементов. Элемент из 5з содержит 6 как первую, вторую или третью цифру.
Если 6 — первая цифра, то существуют 9 вариантов выбора второй цифры и 9 вариантов выбора третьей цифры. Согласно комбинаторному принципу умножения, 5з содержит 9 х 9 = 81 чисел с 6 как первой цифрой. Если 6 — вторая цифра, то имеются 9 вариантов выбора третьей цифры и 8 вариантов 320 ГЛЯ8й В. Комбинаторика и вероятность выбора первой цифры, поскольку первая цифра не может быть нулем. Следовательно, 5з содержит 9 х 8 = 72 чисел, у которых 6 — вторая цифра. Аналогично, 5з содержит 72 числа, у которых 6 — третья цифра. Следовательно, всего 5з содержит 81+ 72+ 72 = 225 элементов.
Поскольку 5 = 51 О 5з и 5з, то 5 содержит 1+ 17 + 225 = 243 элементов. П ПРИМЕР 8.8. Сколько существует целых чисел между О и 1000, содержащих хотя бы одну цифру 6? Для решения этой задачи положим 5 множеством целых чисел от 0 до 1000, не содержащих цифру 6 ни в одном из разрядов. Пусть 51— подмножество множества 5, содержащее однозначные числа; 5з — подмножество множества 5, содержащее двузначные числа; 5з — подмножество множества 5, содержащее трехзначные числа; и 5к — подмножество множества 5, содержащее четырехзначные числа. Множество 51 содержит девять чисел без цифры 6, поскольку только число 6 исключено.
Множество 5з содержит числа, имеющие 8 вариантов выбора первой цифры и 9 вариантов выбора второй цифры, поскольку первая цифра не может быть ни 6, ни О, а вторая цифра не может быть 6. Поэтому 5з содержит 8 х 9 = 72 элементов без цифры 6. Множество 5з содержит числа, имеющие 8 вариантов выбора первой цифры, 9 вариантов выбора второй цифры и 9 вариантов выбора третьей цифры. Поэтому множество 5з содержит 8 х 9 х 9 = 648 элементов без цифры 6. Множество 54 содержит только число 1000.
Следовательно, 5 содержит 9+72+648+1 = 730 элементов. Пусть Т вЂ” множество всех чисел между 0 и 1000. Тогда Т вЂ” 5 — множество всех целых чисел между 0 и 1000, содержащих хотя бы одну цифру 6. Более того, 5 и Т вЂ” 5 — непересекающиеся множества. Следовательно, )5(+~Т вЂ” Я = )Т), так что 730+ОТ вЂ” Я = 1001. Значит, ~Т вЂ” 5! = 271, поэтому между 1 и 1000 существует 271 целое число, содержащее хотя бы одну цифру 6. П ПРИМЕР 8.9.
Сколькими способами можно выбрать две книги по разным темам, когда на полке находятся 15 книг по информатике, 12 книг по математике и 10 книг по химии? Если выбирать книгу по информатике и книгу по математике, то существуют 15 вариантов выбора книги по информатике и 12 вариантов выбора книги по математике, поэтому существует 12 х 15 = 180 возможностей. Если выбирать книги по информатике и по химии, то имеются 15 вариантов выбора книги по информатике и 10 вариантов выбора книги по химии, поэтому существует 15 х 10 = 150 возможностей.
Если выбирается книга по математике и книга по химии, то имеются 12 способов выбора математической книги и 10— книги по химии, поэтому имеется 12 х 10 = 120 возможностей. Следовательно, существуют 180+ 150+ 120 = 450 возможных способов выбора двух книг.
П ПРИМЕР 8.10. Сколько нечетных целых чисел находятся между числами 100 и 1000? Один из способов решения этой задачи состоит в следующем. Пусть 5 — множество нечетных целых чисел между 100 и 1000. Для г Е 11,3,5,7,9) пусть 5, — подмножество множества 5 такое, что 1 является последней цифрой его элементов. Для каждого г существуют 9 вариантов выбора первой цифры и 10 вариантов выбора второй цифры, так что каждое множество 5, содержит 90 элементов. Поскольку 5 = 51 О5з О 5з О 5, О 5э, имеем Ф! = Д!+ ~5з!+ Д~+ Фт! + Д! = РАЗДЕЛ 8. б Основные комбинеторные принципы 321 = 90+ 90+ 90+ 90+ 90 = = 450, поэтому между числами 100 и 1000 находятся 450 нечетных целых чисел.
Данную задачу можно решить, используя также комбинаторный принцип умножения. Существуют 5 вариантов выбора последней цифры, поскольку она должна быть нечетной. Существуют 10 вариантов выбора средней цифры и 9 вариантов выбора первой цифры. Таким образом, имеем 9 х 10 х 5 = 450 нечетных чисел между 100 и 1000. Этот пример показывает, каким образом принцип комбинаторного умножения следует из комбинаторного принципа сложения. П Рис.
8.2 Наконец, вернемся к тому, с чего начали, — к использованию деревьев. Предположим, что команды А и В играют между собой в турнире по бейсболу. Для победы в турнире команде необходимо выиграть три игры из пяти. Все возможные результаты игр представлены деревом на рис. 8.2, где буква в каждой вершине обозначает команду, победившую в игре. Обведенная кружком буква обозначает команду, победившую в турнире. Обратите внимание, что всего имеется 20 возможных исходов; 10 возможных побед у команды А и 10 — у команды В.
Предположим, известно, что команда В выиграла первую игру, что оставляет для рассмотрения только правую сторону дерева, начиная с вершины В. Сторона обведена пунктирной линией. Обратите внимание, что имеются четыре исхода, в которых побеждает команда А, и шесть исходов с победой команды В. Предположим, что первую игру выигрывает команда А, вторую — команда В и команда А выигрывает третью игру.
Результат игры отображен на дереве (часть дерева, обведенная сплошной линией). Обратите внимание, что имеются два исхода, когда побеждает команда А, и только один исход с победой команды В. ПРИМЕР 8.11. Предположим, что команды А и В участвуют в ежегодном чемпионате США по бейсболу, для победы в котором командам необходимо выиграть четыре игры из семи возможных. Если команда А выигрывает первые две игры, 322 Глййд 8. комбинаторика и вероятность то сколько вариантов победы есть у команды А и сколько у команды В? Дерево на рис.
8.3 показывает возможные исходы. Имеются десять исходов с победой команды А и пять возможных исходов с победой команды В. П Г ° ® В ® В ® В А ®® ®® ®® ®® Рис. 8.3 ° УПРАЖНБНИЯ 1. Сколько положительных целых чисел, меньших 700, делятся на 5? Сколько таких чисел делятся на 3? А сколько таких чисел делятся и на 5, и на 3? 2. Если авиакомпания осуществляет 15 рейсов из Сан-Франциско в Чикаго и 20 рейсов из Чикаго в Нью-Йорк, то сколько всего рейсов из Сан-Франциско в Нью-Йорк проходит транзитом через Чикаго? 3. Сколько существует способов избрания президента, вице-президента, секретаря и казначея среди членов клуба, включающего 8 студентов последнего курса, 10 студентов предпоследнего курса, 15 второкурсников и 20 первокурсников, если а) отсутствуют какие-либо ограничения? б) президентом должен быть студент последнего курса? в) студент последнего курса не может быть вице-президентом? г) первокурсники могут быть избраны только на должность секретаря? 4.
В ресторане из напитков предлагают кофе, чай, молоко или колу. Предлагают на выбор суп или салат. Имеются 10 различных бифштексов и 5 разнообразных куриных блюд. На гарнир можно выбрать картофель фри, печеный картофель, макароны с сыром или рис. На десерт подают сладкий пирог, мороженое или то и другое вместе.
а) Сколько можно составить различных меню? б) Сколько можно составить различных меню, включающих бифштекс? в) Сколько можно составить различных меню, если клиент выбирает бифштекс и картофель или не выбирает ни то, ни другое? Ряздел В. и Основные комбинеторные принципы 323 5. Сколько существует различных четырехзначных положительных чисел, если, по крайней мере, две цифры в числе совпадают? 6. Если каждый элемент матрицы размерности 4 х 5 — неотрицательное одно- цифровое число, то сколько существует таких матриц? 7. Сколько существует вариантов ответа на тест из 30 вопросов, если на каждый вопрос требуется ответ да или нет? 8.
Если часы показывают часы, минуты, секунды и лм-рм, то сколько различных моментов времени они могут показать? 9. Позывные американских радиостанций состоят из трех или четырех букв и начинаются с й или ги. Сколько существует различных позывных? 10.
Сколько существует номерных знаков для автомобилей, состоящих из двух букв и последующих четырех цифр? 11. Если имеются высказывания р, д, г и а, то а) сколько строк содержит соответствующая таблица истинности? 6) в скольких строках все р, д, г и а имеют истинное значение? в) в скольких строках хотя бы одно из четырех высказываний ложно? 12.
Сколько существует номерных знаков для автомобилей, состоящих из двух букв с последующими четырьмя цифрами, если буквы могут повторяться, а цифры — нет? !3. Сколько существует различных номеров карточек социального страхования? 14. Сколько существует номерных знаков для автомобилей, состоящих из двух букв с последующими четырьмя цифрами, если ни одна из букв не может быть гласной? Если хотя бы одна из букв должна быть гласной? 15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
