Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 57
Текст из файла (страница 57)
8.7 Рис. 8.8 РАЗДЕЛ 8.2. Комбинеторный принцип сложения 327 Известно, что 85 человек предпочитают смотреть драмы. Поскольку 75 из них уже перечислены, остальные 10 должны смотреть только драмы. Рассуждая аналогичным образом, получаем, что из 110 тех, кто смотрит спорт, уже перечислены 90 человек, поэтому оставшиеся 20 должны смотреть только спорт.
И наконец, замечаем, что из 120 тех, кто смотрит комедии, 95 уже учтены. Таким образом, 25 человек смотрит только комедии. Если подсчитать количество людей в непересекюшихся подмножествах, то получим число 170. Поэтому 30 человек не смотрят ни спорт, ни комедии, ни драмы (диаграмма Венна, рис. 8.7).
Используя эту диаграмму, можно, например, установить следуюшие факты: 35 человек смотрят драмы, но не спорт; 50 человек смотрят спорт или драму, но не комедии; 55 человек предпочитают только одну из трех программ; 85 предпочитают две программы из трех; 85 человек смотрят комедии или спорт, но только не драмы. ПРИМЕР 8.17. Предположим, что из 100 опрошенных студентов 50 изучают химию, 53 — математику, 42 — физику, 15 — химию и физику, 20 занимаются физикой и математикой, 25 — математикой и химией и 5 студентов изучают все три предмета. а) Сколько студентов изучают хотя бы один из трех перечисленных предметов? б) Сколько студентов не изучают ни один из трех перечисленных предметов? в) Сколько студентов изучают только математику? г) Сколько студентов изучают физику или химию, но не изучают математику? д) Сколько студентов не изучают ни математику, ни химию? Поскольку 5 человек изучают все три предмета, а 15 человек — химию и физику, остаются 10 человек, изучаюших химию и физику, но не изучаюших математику.
Аналогично, 25 — 5 = 20 человек занимаются математикой и химией, но не физикой, и 20 — 5 = 15 человек изучают математику и физику, но не изучают химию. Данную ситуацию изображает диаграмма Венна, приведенная на рис. 8.8. Рис. 8.8 Рис. 8.~ Поскольку 50 студентов изучают химию, и 35 из них уже учтены, то оставшиеся 15 изучают только химию. Аналогично, 53 студента занимаются математикой, и 40 из них уже учтены, поэтому 13 человек изучают только математику. Наконец, 42 студента изучают физику, и 30 из них уже учтены, поэтому 12 человек изучают только физику. а) Суммируя количество людей, принадлежаших семи непересекающимся подмножествам, получаем 90 тех, кто изучает хотя бы один из трех предметов.
328 ГллВА 8. комбинаторика и вероятность б) Поскольку 90 из 100 студентов изучают хотя бы один предмет, то 100 — 90 = 10 человек не изучают ни один из этих трех предметов. в) Из диаграммы Венна следует, что 13 человек изучают только математику. г) Тридцать семь студентов занимаются химией или физикой, но не изучают математику. д) Из диаграммы Венка, изображенной на рис. 8.9, следует, что 75 человек изучают математику или физику.
Поэтому 100 — 75 = 25 студентов не изучают ни математику, ни физику. П ПРИМЕР 8.18. Сколько положительных целых чисел, меньших 1001, делятся на 2, 3 или 5? Сколько положительных целых чисел, меньших 1001, не делятся на 2, 3 или 5? Имеется всего — = 500 целых чисел, которые делятся на 2. Имеется всего — = 333 целых числа, которые делятся на 3. Имеется всего — = 200 целых чисел, которые делятся на 5. Если целое число делится на 2 и на 3, то оно делится на 6, поэтому существует — = 166 целых чисел, которые делятся на 2 и на 3. Если целое число делится на 2 и 5, то оно делится на 10, поэтому существует — = 100 целых чисел, которые делятся на 2 и на 5.
Если целое число делится на 3 и на 5, то оно делится на 15, поэтому имеется — = 66 целых чисел, которые делятся на 3 и на 5. Наконец, если целое число делится на 2, 3 и 5, то оно делится на 30, и существует целых числа, которые делятся на 2, 3 и 5. Следовательно, количество чисел, которые делятся на 2, 3 или 5, равно 500+ 333+ 200 — 166 — 100 — 66+ 33 = 734.
Количество положительных чисел, которые не делятся ни на одно из указанных целых чисел, равно 1001 — 734 = 267. П Рда~2ЕЛ В.д Комйинеглорный принцип сложения 329 ПРИМЕР 8.19. Сколько неотрицательных целых чисел, меньших 100000, содержат цифры 3, 6 и 9? Пусть универсум 1? будет множеством всех неотрицательных целых чисел, меньших 100000. Следовательно, Щ = 100000. Пусть 5з — множество всех целых чисел, меньших 100000, которые не содержат цифру 3. Пусть 5б — множество всех целых чисел, меньших 100000, которые не содержат цифру 6.
Пусть 5д — множество всех целых чисел, меньших 100000, не содержащих цифру 9. Нас интересует 15з О 5б О 5д(, но ф,'О5,'П5,'~ =!Ц вЂ” 15~ О5б О5,~, 15з О5б О5д! = = 153 ~ + Фб! + 15д 1 153 О 5б! 153 О 5д! 15б О 5д ! + | 53 Й 5б Й 5д !.
Для 5з существуют девять вариантов выбора каждой из пяти цифр, поскольку только цифра 3 исключена. Поэтому 15з! = 9з. Аналогично, 15б) = 15д( = 9'. Поскольку каждая цифра числа из множества 5з О 5б может быть любой, за исключением 3 и 6, то существуют восемь вариантов выбора каждой цифры, по- этомУ фз й 5б) = 8б. Аналогично, (5з О 5д! = 15б Гт 5д) = 8з. КажДаЯ цифРа числа из 5з И 5б О 5д может быть любой, исключаЯ 3, 6 и 9, поэтомУ сУШествУют семь вариантов выбора каждой цифры. Отсюда 15з и 5б О 5д! = 7б. Следовательно, 15з О5б О 5д) = 9б+9б+9з — 8з — 8б — 8з+ 7б = 95650 5з О 5г О 5д = ) Ц вЂ” (5з О 5б О 5д) = 100 000 — 95 650 = 4350. П ° УПРАЖНЕНИЯ 1.
В классе из 200 студентов 120 человек изучают историю Канзаса 1995 — 96 гг., 110 занимаются тестированием продукта "Йогурт И", а 80 студентов делают и то, и другое. Сколько студентов изучают хотя бы один из этих курсов? Сколько студентов не изучают ни одного из них? 2. Сколько целых чисел между 1 и 401 делятся на 5 или на 7? 3. Сколько целых чисел между 1 и 401 делятся на 7 или на 11? 4. Сколько целых чисел между 1 и 401 делятся на 6 или на 10? 5.
Сколько целых чисел между 1 и 401 делятся на 10 или на 15? 8. Сколько целых чисел между 1 и 1001 делятся на 10, но не делятся на 40? 7. Сколько целых чисел между 1 и 1001 делятся на 10, но не делятся на 14? 8. Год является високосным, если (а) количество дней в нем делится на 4, но не делится на 100, или (б) если он делится на 400. Сколько високосных годов было между 1001 и 2001 годами? 9. Сколькими способами можно разместить положительные целые числа, меньшие 1О, так чтобы 4 было расположено сразу после 5 или 5 было расположено сразу после 4? Сколько сушествует размещений, в которых 4 и 5 не стоят рядом? ззо ГЛКНА 8.
Комбинвторикв и вероятность Сколькими способами можно разместить положительные целые числа, мень- шие !О, так что 4 было бы расположено сразу после 3 или 7 было бы распо- ложено сразу после 6? Сколько существует положительных целых чисел, содержащих не более пяти цифр, в которых а) первой цифрой является 3? б) последней цифрой является 5? в) первой цифрой является 3 или последней цифрой является 5? г) ни первая цифра не равна 3, ни последняя цифра не равна 5? 10.
11. 12. Сколько целых чисел между 1 и 2003 делится на 3, 5 или 7? 13. Сколько целых чисел между 1 и 2003 делится на 5, 7 или 11? 14. Сколько целых чисел между 1 и 2003 делится на 4, 5 или 6? 15. Сколько целых чисел между 1 и 2003 делится на 6, 7 или 8? социологию, 35 изучают математику и социологию, 20 — историю и социологию, 25 изучают математику и историю, 15 студентов — все три предмета.
а) Сколько студентов изучают хотя бы один из трех предметов? б) Сколько студентов изучают только один из трех предметов? в) Сколько студентов изучают историю или математику, но не изучают социологию? г) Сколько студентов не изучают ровно два из трех предметов? д) Сколько студентов не выбрали историю или математику? 17. Согласно опросу 250 телезрителей, 95 из них нравится смотреть новости, 125 предпочитают смотреть спорт, 125 — комедии, 25 — новости и комедии, 45— спорт и комедии, 35 — новости и спорт, 5 любят все три вида программ. а) Сколько телезрителей смотрят новости, но не смотрят спорт? б) Сколько телезрителей смотрят новости или спорт, но не любят комедии? в) Сколько телезрителей не любят смотреть ни новости, ни спорт? г) Сколько телезрителей смотрят не только спорт? д) Сколько телезрителей смотрят спорт и комедии, но не смотрят новости? 18.