Общие правила комбинаторики

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

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

3. Сколькими способами можно выбрать на шахматной доске два квадрата – белый и черный так, чтобы они не лежали на одной горизонтали и вертикали?

4. Из 12 слов мужского рода, 9 женского и 10 среднего надо выбрать по одному слову каждого рода. Сколькими способами это можно сделать?

5. У одного человека есть 7 книг по математике, а у другого – 9 книг. Сколькими способами они могут обменять книгу одного на книгу другого?

6. Из двух спортивных обществ, насчитывающих по 100 фехтовальщиков каждое, надо выделить по одному фехтовальщику для участия в состязании. Сколькими способами может быть сделан этот выбор?

7. Имеется 6 пар перчаток разных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну – на правую так, чтобы эти перчатки были различных размеров?

8. Из трех различных экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 6 экземпляров учебника физики надо выбрать по одному экземпляру каждого учебника. Сколькими способами это можно сделать?

9. Сколькими способами можно выбрать гласную и согласную буквы из слова «КАМЗОЛ»?

10. На доске написаны 7 существительных, 5 глаголов и 2 прилагательных. Для предложения нужно выбрать по одному слову каждой из этих частей речи. Сколькими способами это можно сделать?

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

12. При составлении экипажа космического корабля необходимо учитывать психологическую совместимость членов экипажа. Известно, что команда состоит из трех человек: капитана, инженера и врача. Причем на должность капитана есть четыре кандидата k₁, k₂, k₃, k₄, на место инженера – 3 кандидата i₁, i₂, i₃ и на место врача – 3 кандидата v₁, v₂, vi₃. Проведенные исследования показали, что командир k₁ психологически совместим с инженерами i₁, i₃ и врачами v₂, v₃, командир k₂ – с инженерами i₁, i₂ и со всеми врачами, командир k₃ – с инженерами i₁, i₂ и врачами v₁, v₃, командир k₄ – со всеми инженерами и врачом v₂. Кроме того, инженер i₁ психологически несовместим с врачом v₃, инженер i₂ – с врачом v₁, инженер i₃ – с врачом v₂. Сколькими способами можно составить команду корабля?

13. В Стране Чудес есть четыре города: А, Б, В и Г. Из города А в город Б ведет 6 дорог, а из города Б в город В – 4 дороги, из города А в город Г – две дороги и из города Г в город В – тоже две дороги. Сколькими способами можно проехать от А до В?

14. В магазине одежды продаются 5 видов костюмов-троек (брюки, пиджак, жилет), 7 видов брюк, 3 вида пиджаков и 2 вида жилетов, кроме того, 3 вида костюмов-двоек (брюки, пиджак). Сколькими способами можно сделать покупку, содержащую брюки, пиджак и жилет?

15. У двух начинающих коллекционеров по 20 марок и по 10 значков. Честным обменом называется обмен одной марки на одну марку или одного значка на один значок. Сколькими способами коллекционеры могут осуществить честный обмен?

16. В книжном магазине лежат 6 экземпляров романа И.С. Тургенева «Рудин», 3 экземпляра его же романа «Дворянское гнездо» и 4 экземпляра романа «Отцы и дети». Кроме того, есть 5 томов, содержащих романы «Рудин» и «Дворянское гнездо», и 7 томов, содержащих романы «Дворянское гнездо» и «Отцы и дети». Все книги различны. Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из этих романов?

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

18. Сколькими способами из полной колоды (52 карты) можно выбрать 4 карты, по одной каждой масти?

19. Сколькими способами из полной колоды (52 карты) можно выбрать 4 карты разных мастей и достоинств?

20. В корзине лежат 12 яблок и 10 апельсинов. Ваня выбирает из неё яблоко или апельсин (что-то одно), после чего Надя берет и яблоко, и апельсин. В каком случае Надя имеет большую свободу выбора: если Ваня взял яблоко или если он взял апельсин?

21. Сколькими способами можно поставить на доску две шашки – белую и черную так, чтобы белая шашка могла бить черную? Черная – белую? Обе шашки могут бить друг друга? Ни одна не может бить другую?

Формула включения и исключения

22. В автопарке имеются водители категорий В, С и Д. Водителей категории В – 17 человек, С – 15 человек, Д – 7 человек. При этом некоторые водители имеют права сразу нескольких категорий. Права категорий В и С имеют 10 человек, В и Д – 4 человека, С и Д – 3 человека; В, С и Д – 2 человека. Сколько водителей работает в автопарке?

23. В классе учатся 45 школьников, в том числе 25 мальчиков. 30 школьников учатся на «хорошо» и «отлично», в том числе 16 мальчиков. Спортом занимаются 28 учеников, в том числе 18 мальчиков и 17 учащихся на «хорошо» и «отлично». 15 мальчиков учатся на хорошо и отлично и в то же время занимаются спортом. Докажите, что в этой информации сдержатся ошибки.

24. В отделе научно-исследовательского института работают несколько человек, причем каждый из них знает хотя бы один иностранный язык. Шестеро знают английский, шестеро – немецкий, семеро – французский. Четверо знают английский и немецкий, трое – немецкий и французский, двое – французский и английский. Один человек знает все три языка. Сколько человек работают в отделе? Сколько человек знают только английский язык? Только французский?

25. Сколько чисел в первой сотне не делится ни на одно из чисел 2, 3, 5?

26. Сколько существует натуральных чисел меньших 1000, которые не делятся ни на 3, ни на 5, ни на 7?

27. В ожесточенном бою 70 из 100 пиратов потеряли один глаз, 75 – одно ухо, 80 – одну руку и 85 – одну ногу. Страховая компания «Веселый Роджер», в которой застрахованы пираты, задалась вопросом: каково минимальное число потерявших одновременно глаз, ухо, руку или ногу (страховой случай Total Permanent Disablement, при котором выплаты компании максимальны)?

Размещения с повторениями

28. Назовем натуральное число «симпатичным», если в его записи встречаются только нечетные цифры. Сколько существует 4-значных «симпатичных» чисел?

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

30. На железнодорожной станции имеется m светофоров. Сколько может быть дано различных сигналов, если каждый светофор имеет три состояния: красный, желтый, зеленый?

31. Сколькими способами можно отправить 6 писем с тремя курьерами?

32. В клубе велосипедистов считается плохим знаком иметь членский билет, в номере которого есть цифра 8. Поэтому председатель клуба решил выдавать билеты с номерами, в которые ни одна 8 не входит. Сколько было членов в группе, если известно, что использованы все трехзначные номера, не содержащие ни одной восьмерки?

33. На флоте применяют семафор флажками. Каждой букве соответствует определенное положение флажков. Всего положений каждого флажка пять – вниз отвесно, вниз наклонно, горизонтально, вверх наклонно и вверх отвесно. Как правило, флажки находятся по разные стороны от тела сигнальщика. Но при передаче некоторых букв оба флажка расположены по одну и ту же сторону. Почему пришлось сделать такое исключение?

34. В селении проживают 2000 жителей. Доказать, что, по крайней мере, двое из них имеют одинаковые инициалы.

35. Каждую клетку квадратной таблицы 2×2 можно покрасить в черный или белый цвет. Сколько существует различных раскрасок этой таблицы?

36. Крокодил имеет 68 зубов. Доказать, что среди 16¹⁷ крокодилов может не оказаться двух с одним и тем же набором зубов.

37. В некотором государстве не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения государства? (Наибольшее число зубов равно 32.)

38. При передаче сообщений по телеграфу используется код Морзе. В этом коде буквы, цифры и знаки препинания обозначаются точками и тире. При этом для одних букв используется только один знак (Е ∙), а для некоторых приходится использовать пять знаков (Э ∙ ∙ - ∙ ∙). Почему нельзя обойтись меньшим числом знаков?

39. Сколькими способами можно заполнить одну карточку в лотерее «Спортпрогноз»? (В этой лотерее нужно предсказать итог тринадцати спортивных матчей. Итог каждого матча – победа одной из команд либо ничья; счет роли не играет).

40. Трое юношей и две девушки выбирают место работы. В городе есть три завода, где требуются рабочие в литейный цех (туда берут лишь мужчин), две ткацкие фабрики (туда приглашают лишь женщин) и две фабрики, где требуются и мужчины, и женщины. Сколькими способами могут они распределиться между этими предприятиями?

41. Алфавит племени Мумбо-Юмбо состоит из трех букв А, Б и В. Словом является любая последовательность, состоящая не более чем из 4 букв. Сколько слов в языке племени Мумбо-Юмбо?

Размещения без повторений

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

43. В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?

44. Научное общество состоит из 25 человек. Надо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост?

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

46. Забор состоит из 100 дощечек. У Тома Сойера есть краски 150 различных цветов. Сколько существует различных раскрасок забора, если все дощечки покрашены в разный цвет? Та же задача, но дощечки могут быть покрашены в одинаковый цвет.

47. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили два различных числа?

48. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4 и 5? Тот же вопрос, но при условии, что ни одна цифра не повторяется?

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

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

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

52. Сколькими способами можно составить расписание на день из 5 различных уроков, если изучается 14 предметов?

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