Задачи по комбинаторике

Задачи 1-50 с ответами

содержание задачника

1. Из города А в город В ведут пять дорог, а из города В в город С — три дороги. Сколько путей, проходящих через В, ведут из А в С?
2. Из двух спортивных обществ, насчитывающих по 100 фехтовальщиков каждое, надо выделить по одному фехтовальщику для участия в состязании. Сколькими способами может быть сделан этот выбор?
3. Имеется пять видов конвертов без марок и четыре вида марок одного достоинства. Сколькими способами можно выбрать конверт с маркой для посылки письма?
4. Сколькими способами можно выбрать гласную и согласную буквы из слова «камзол»?
5. Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?
6. Бросают игральную кость с шестью гранями и запускают волчок, имеющий восемь граней. Сколькими различными способами могут они упасть?
7. На вершину горы ведут пять дорог. Сколькими способами турист может подняться на гору и спуститься с нее? То же самое при условии, что спуск и подъем происходят по разным путям.
8. На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?
9. Сколькими способами можно указать на шахматной доске два квадрата — белый и черный? А если нет ограничении на цвет выбранных квадратов?
10. Сколькими способами можно выбрать на шахматной доске белый и черный квадраты, не лежащие на одной и той же горизонтали и вертикали?
11. Из 12 слов мужского рода, 9 женского и 10 среднего надо выбрать по одному слову каждого рода. Сколькими способами может быть сделан этот выбор?
12. Имеется 6 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну — на правую руку так, чтобы эти перчатки были различных размеров?
13. Из 3 экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 7 экземпляров учебника тригонометрии надо выбрать по одному экземпляру каждого учебника. Сколькими способами это можно сделать?
14. В букинистическом магазине лежат 6 экземпляров романа И. С. Тургенева «Рудин», 3 экземпляра его же романа «Дворянское гнездо» и 4 экземпляра романа «Отцы и дети». Кроме того, есть 5 томов, содержащих романы «Рудин» и «Дворянское гнездо», и 7 томов, содержащих романы «Дворянское гнездо» и «Отцы и дети». Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из этих романов?
15. В букинистическом магазине лежат 6 экземпляров романа И. С. Тургенева «Рудин», 3 экземпляра его же романа «Дворянское гнездо» и 4 экземпляра романа «Отцы и дети». Кроме того, есть 5 томов, содержащих романы «Рудин» и «Дворянское гнездо», 7 томов, содержащих романы «Дворянское гнездо» и «Отцы и дети» и 3 тома, в которые входят «Рудин» и «Отцы и дети». Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из этих романов?
16. В корзине лежат 12 яблок и 10 апельсинов. Ваня выбирает из нее яблоко или апельсин, после чего Надя берет и яблоко, и апельсин. В каком случае Надя имеет большую свободу выбора: если Ваня взял яблоко или если он взял апельсин?
17. Имеются три волчка с 6, 8 и 10 гранями соответственно. Сколькими различными способами могут они упасть? Та же задача, если известно, что по крайней мере два волчка упали на сторону, помеченную цифрой 1.
18. Сколькими способами можно выбрать три различные краски из имеющихся пяти?
19. Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов? Та же задача, если одна из полос должна быть красной?
20. Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, французского, немецкого, итальянского, на любой  другой из этих пяти языков?
21. На сколько больше словарей придется издать, если число различных языков равно 10 (смотрите задачу 20)?
22. Сколькими способами можно выбрать из полной колоды карт по одной карте каждой масти? То же самое при условии, что среди вынутых карт нет ни одной пары одинаковых, то есть двух королей, двух десяток и так далее.
23. Сколькими способами можно выбрать из полной колоды карт (содержащей 52 карты) по одной карте каждой масти так, чтобы карты красных мастей и карты черных мастей образовывали пары (например, девятки пик и треф и валеты бубен и червей)?
24. У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если общее число имел равно 300, а ему дают не более трех имен?
25. Несколько человек садятся за круглый стол. Будем считать, что два способа рассадки совпадают, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколькими различными способами можно посадить четырех человек? А семь человек? Во скольких случаях два данных человека из семи оказываются соседями? Во скольких случаях данный человек (из семи) имеет двух данных соседей?
26. Пять девушек и трое юношей играют в городки. Сколькими способами они могут разбиться на две команды по 4 человека в каждой команде, если в каждой команде должно быть хотя бы по одному юноше?
27. Надо послать 6 срочных писем. Сколькими способами это можно сделать, если для передачи писем можно послать трех курьеров и каждое письмо можно дать любому из курьеров?
28. У одного человека есть 7 книг по математике, а у другого — 9 книг. Сколькими способами они могут обменять книгу одного на книгу другого?
29. У одного человека есть 7 книг по математике, а у другого — 9 книг. Сколькими способами они могут обменять две книги одного на две книги другого?
30. На собрании должны выступить 5 человек: А, Б, В, Г и Д. Сколькими способами можно расположить их в списке ораторов при условии, что Б не должен выступать до того, как выступит А?
31. На собрании должны выступить 5 человек: А, Б, В, Г и Д. Сколькими способами можно расположить их в списке ораторов при условии, что А должен выступить непосредственно перед Б?
32. Сколькими способами можно посадить за круглый стол 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом?
33. Сколькими способами можно посадить на карусель 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом. Способы, переходящие друг в друга при вращении карусели, считаются совпадающими.
34. Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется хотя бы одни туз? Во скольких случаях ровно один туз? Во скольких случаях не менее двух тузов? Ровно два туза?
35. На железнодорожной станции имеется m светофоров. Сколько может быть дано различных сигналов, если каждый светофор имеет три состояния: красный, желтый и зеленый?
36. В некотором государстве не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения государства (наибольшее число зубов равно 32)?
37. В купе железнодорожного вагона имеется два противоположных дивана по 5 мест в каждом. Из 10 пассажиров четверо желают сидеть липом к паровозу, а трое — спиной к паровозу, остальным трем безразлично, как сидеть. Сколькими способами могут разместиться пассажиры?
38. В организацию избрано 9 человек. Из них надо избрать председателя, заместителя председателя, секретаря и культорга. Сколькими способами это можно сделать?
39. Из состава конференции, на которой присутствует 52 человека, надо избрать делегацию, состоящую из 5 человек. Сколькими способами это можно сделать?
40. Автомобильные номера состоят из одной, двух или трех букв и четырех цифр. Haйти число таких номеров, если используются 32 буквы русского алфавита.
41. У мамы 2 яблока и 3 груши. Каждый день в течение пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?
42. У мамы m яблок и n груш. Каждый день в течение пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?
43. У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течение пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?
44. У отца есть 5 попарно различных апельсинов, которые он выдает своим восьми сыновьям так, что каждый получает либо один апельсин, либо ничего. Сколькими способами можно это сделать?
45. У отца есть 5 попарно различных апельсинов, которые он выдает своим восьми сыновьям так, что каждый получает либо некоторое количество апельсинов, либо ничего. Сколькими способами можно это сделать?
46. Сколько различных слов можно получить, переставляя буквы в слове «математика»? В слове «парабола»? В слове «ингредиент»?
47. Из спортивного клуба, насчитывающего 30 членов, надо coставить команду из 4 человек для участия и беге на 1000 м. Сколькими способами можно это сделать? А сколькими способами можно составить команду из 4 человек для участия в эстафете 100+200+400+800?
48. Сколькими способами можно расставить белые фигуры (2 коня, 2 слона, 2 ладьи, ферзя и короля) на первой линии шахматной доски?
49. Имеется n абонентов телефонной сети. Сколькими способами можно одновременно соединить три пары?
50. В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить в нем 12 открыток? Сколькими способами можно купить 8 открыток? Сколькими способами можно купить 8 различных открыток?

Ответы

1. 15
2. 10000
3. 20
4. 8
5. 9
6. 48
7. 25; 20
8. 480; 437
9. 1024; 4032
10. 768
11. 1080
12. 30
13. 147
14. 134
15. 143
16. если взято яблоко
17. 22
18. 10
19. 36
20. 20
21. 70
22. 17160
23. 169
24. 26820600
25. 24; 360; 120; 24
26. 30
27. 729
28. 63
29. 756
30. 60
31. 24
32. 28800
33. 2880
34. $C_{52}^{10}-C_{48}^{10}; C_{4}^{1}C_{48}^{9}; C_{52}^{10}-C_{48}^{10}-4C_{49}^{9}; C_{4}^{2}C_{48}^{8}$
35. $3^m$
36. $2^{32}$
37. 43200
38. 3024
39. 2598960
40. 338200000
41. 10
42. $C_{m+n}^{m}$
43. 1260
44. 6720
45. 32768
46. P(4,3,3,2,1,1); P(3,1,1,1,1,1); P(2,2,2,1,1,1)
47. 27405; 657720
48. 5040
49. $\frac{n!}{48(n-6)!}$
50. $C_{21}^{12}; C_{17}^{8}; C_{10}^{8}$