Задачи комбинаторики.
Чтобы научиться быстро бегать, нужно много бегать. Чтобы научиться хорошо решать сложные задачи, нужно решать много простых задач. И то, и другое надо делать с умом. Последовательно тренировать определенные группы мышц, и постепенно вникать в смысл математических выражений.
Давайте рассмотрим несколько очень простых задач, сравнивая их между собой. Сравнение поможет нам понять и запомнить, как выбрать нужную формулу для подсчёта числа вариантов в той или иной ситуации. А чтобы никто не усомнился в том, что задачи действительно простые, я взяла за основу Сборник тестовых заданий к учебнику Н.Я. Виленкина и др. "Математика. 5 класс". Конечно, для пятиклассников это задания высокого уровня сложности "С", но они справляются. Дело в том, что эти задачи можно решить как простым перебором вариантов, тем быстрее, чем выше уровень обобщения, так и по формулам комбинаторики. Старшеклассникам рекомендую повторить формулы и правила комбинаторики, если вы попали на эту страницу из поисковика, миновав теорию.
Итак,
- внимательно читаем условия 2-ух задач из одной строки таблицы;
- решаем обе задачи любыми доступными способами (желательно не одним);
- открываем ответы нажатием на зеленые кнопки и сравниваем их со своими ответами;
- открываем решения и комментарии к ним нажатием на желтые кнопки.
Помните, что ваше решение не обязательно должно совпадать с моим, достаточно, чтобы оно было логичным и позволяло получить верный ответ.
Задачи и решения.
| Задача 1a | Задача 1b |
|---|---|
| При окончании деловой встречи специалисты обменялись визитными карточками. Сколько всего визитных карточек перешло из рук в руки, если во встрече участвовали 6 специалистов? | При встрече каждый из друзей пожал другому руку. Сколько всего было рукопожатий, если встретились 6 друзей? |
| Ответ: 30 | Ответ: 15 |
|
Решение.
Каждый из 6-ти специалистов отдал по 5 карточек (всем, кроме себя). Потребовалось 6·5 = 30 карточек. |
Решение.
В одном рукопожатии равноправно участвуют два человека. 6 друзей объединялись в группы по 2 без учёта порядка следования. Такие группировки (выборки) называются сочетаниями. Число сочетаний определяем по формуле С62 = 6!/2!/(6 - 2)! = 6!/2!/4! = 5·6/2 = 15. о вычислениях подробнее |
| Задача 2a | Задача 2b |
| В хоровом кружке занимаются 9 человек. Необходимо выбрать двух солистов. Сколькими способами это можно сделать? | В спортивной команде 9 человек. Необходимо выбрать капитана и его заместителя. Сколькими способами это можно сделать? |
| Ответ: 36 | Ответ: 72 |
|
Решение.
Два солиста равноправны. (Может быть, и петь планируют дуэтом.) Нас не волнует порядок следования в группе из 2-ух человек, выбранных из 9-ти. Значит определяем число сочетаний из 9 по 2. С92 = 9!/2!/(9 - 2)! = 9!/2!/7! = 8·9/2 = 36. |
Решение.
Казалось бы, мы снова выбираем 2-ух человек из 9-ти, но теперь между ними качественная разница. Они будут выполнять разные обязанности в команде. Мы выбираем капитана И заместителя независимо друг от друга. Поэтому применим правило умножения вариантов (И-правило). Из 9-ти человек капитана можно выбрать 9-тью способами. Его заместителя из оставшихся 8-ми человек - 8-мью способами. Общее число вариантов: 9·8 = 72. (Заметьте, что если сначала выбрать заместителя из 9 человек, а потом капитана из оставшихся 8-ми, результат будет тот же.) Можно рассуждать иначе. Есть два места для капитана и его заместителя, нужно разместить на них 2-ух человек, выбрав их из 9-ти. Такие группировки (выборки) называются размещениями. Число размещений определяем по формуле А92 = 9!/(9 - 2)! = 9!/7! = 8·9 = 72. о формуле подробнее |
| Задача 3a | Задача 3b |
| Сколько существует вариантов рассаживания вокруг стола 6 гостей на 6 стульях? | В понедельник в пятом классе 5 уроков: музыка, математика, русский язык, литература и история. Сколько различных способов составления расписания на понедельник существует? |
| Ответ: 720 | Ответ: 120 |
|
Решение.
Легко понять, что в этой задаче речь идет о перестановках. 6 гостей занимают все 6 стульев и могут только меняться местами. Число перестановок из 6 определяем по формуле P6 = 6! = 1·2·3·4·5·6 = 720. |
Решение.
Может быть, не так очевидно, но это тоже перестановки. С точки зрения математики, вообще та же самая задача. Представьте себе, что расписание составляете вы. Чертите таблицу с пятью строками для пяти уроков ("готовите стулья") и вписываете в каждую строку название одного из 5-ти предметов ("рассаживаете гостей"). Число перестановок из 5 определяем по формуле P5 = 5! = 1·2·3·4·5 = 120. |
| Задача 4a | Задача 4b |
| Пятеро друзей сыграли между собой по одной партии в шахматы. Сколько всего партий было сыграно? | Сколькими способами 10 футбольных команд могут разыграть между собой золотые, бронзовые и серебряные медали? |
| Ответ: 10 | Ответ: 720 |
|
Решение.
В шахматной партии 2 равноправных участника (точно также, как в задаче о рукопожатиях). Значит из 5-ти человек формируем группы по 2 без учета порядка следования - сочетания. Определяем число сочетаний из 5 по 2. С52 = 5!/2!/(5 - 2)! = 5!/2!/3! = 4·5/2 = 10. |
Решение.
На пьедестале почёта находятся 3 команды из 10, и для них очень существенно, кто какое место занял, т.е. порядок следования. Составление групп с учетом порядка следования - размещения. Число размещений определяем по формуле А103 = 10!/(10 - 3)! = 10!/7! = 8·9·10 = 720. Другой способ решения с использованием И-правила, как в задаче 2б. Однако, чем больше выборка, тем удобнее сразу применять готовую формулу. |
|
| |
| Задача 5a | Задача 5b |
| В меню столовой предложено на выбор 2 первых блюда, 6 вторых и 4 третьих блюда. Сколько различных вариантов обеда, состоящего из первого, второго и третьего блюда, можно составить? | Имеется 6 видов овощей. Решено готовить салаты из трёх видов овощей. Сколько различных вариантов салатов можно приготовить? |
| Ответ: 48 | Ответ: 20 |
|
Решение.
Выбираем три блюда: первое, И второе, И третье. Едим каждое блюдо отдельно (независимо друг от друга). Следовательно, можем применить правило умножения вариантов (И-правило). Из 2-ух первых блюд одно можно выбрать 2-мя способами, из 6-ти вторых одно можно выбрать 6-тью способами, из 4-ёх третьих одно - 4-мя способами. 2·6·4 = 48. |
Решение.
Чем отличается салат от описанного ранее обеда? Обед едим последовательно, а салат перемешиваем. Выбранные овощи в салате равноправны, очередность их попадания в общее блюдо не важна. Значит наши выборки это сочетания из 6 по 3. С63 = 6!/3!/(6 - 3)! = 6!/3!/3! = (4·5·6)/(1·2·3) = 20. |
| Задача 6a | Задача 6b |
| В магазине продаются блокноты 7 разных видов и ручки 4 разных видов. Сколькими разными способами можно выбрать покупку из одного блокнота и одной ручки? | В магазине продаются блокноты 7 разных видов и ручки 4 разных видов. Сколькими способами можно выбрать покупку из двух разных блокнотов и одной ручки? |
| Ответ: 28 | Ответ: 84 |
|
Решение.
Выбираем одну ручку И один блокнот. Одну ручку из 4-ёх 4-мя способами, один блокнот из 7-ми - 7-ю способами. Применяем правило умножения 4·7 = 28. |
Решение.
Выбираем одну ручку И два блокнота. Снова можем применить правило умножения вариантов. Одну ручку из 4-ёх можем выбрать 4-мя способами, два блокнота из 7-ми - ? способами. Чтобы определить сколько способов выбора 2-ух блокнов из 7-ми, воспользуемся формулой для числа сочетаний, т.к. для нас несущественно в каком порядке это было сделано. С72 = 7!/2!/(7 - 2)! = 7!/2!/5! = 6·7/2 = 21. Теперь применяем правило умножения 4·21 = 84. |
| Задача 7a | Задача 7b |
| На прививку в медпункт отправились 7 друзей. Сколькими разными способами они могут встать в очередь у медицинского кабинета? | Секретный замок состоит из 4 барабанов, на каждом из которых можно выбрать цифры от 0 до 9. Сколько различных вариантов выбора шифра существует? |
| Ответ: 5040 | Ответ: 10000 |
|
Решение.
Число способов встать в очередь равно числу перестановок 7-ми друзей в пределах этой очереди. P7 = 7! = 1·2·3·4·5·6·7 = 5040. Задача такая же, как о гостях и стульях, но обратите внимание, насколько быстро растет число вариантов при увеличении числа переставляемых предметов. |
Решение.
На каждом барабане можно выбрать 1-ну цифру из 10-ти 10-тью способами и независимо от других, поэтому применяем правило умножения: 10·10·10·10 = 10000. Можно также считать, что нужно разместить 10 цифр на 4-ёх местах с повторениями. В комбинаторике существует раздел "Выборки с повторениями" (см. подробнее). В данном случае нам нужна формула для размещений. Число размещений с повторениями определяется как nk, где n - количество элементов для выбора (здесь n = 10 цифр), k - объём выборки или количество возможных повторов одного элемента (здесь k = 4, одна и та же цифра может быть установлена на всех четырех барабанах). Таким образом, искомое число вариантов 104 = 10000. |
| Задача 8a | Задача 8b |
| Сколько различных трёхзначных чисел можно составить при помощи цифр 4, 7, 9? (Цифры в записи числа не повторяются). | Сколько различных трёхзначных чисел можно составить с помощью цифр 1, 3, 7? (Цифры могут повторяться). |
| Ответ: 6 | Ответ: 27 |
|
Решение.
Трёхзначное число состоит из 3-ёх цифр, которые нам даны. Поскольку цифры не могут повторяться, то получать различные числа можно только путем их перестановки. Число перестановок из 3-ёх определяем по формуле P3 = 3! = 1·2·3 = 6. |
Решение.
Если цифры могут повторяться, то по разрядам их можно размещать независимо от друг от друга. Значит можем применить правило умножения вариантов (И-правило). Одну цифру из трёх для разряда сотен можно выбрять 3-мя способами, И одну цифру из тех же трёх для разряда десятков - 3-мя способами, И одну из трёх для разряда единиц - 3-мя способами. Общее число вариантов 3·3·3 = 27. |
|
| |
| Задача 9a | Задача 9b |
| Сколько различных трёхзначных чисел можно составить с помощью цифр 7 и 3? | Сколько различных двузначных чисел можно составить при помощи цифр 4, 7, 9? (Цифры в записи числа не повторяются). |
| Ответ: 8 | Ответ: 6 |
|
Решение.
Трёхзначное число из двух цифр неизбежно будет содержать повторения, поэтому можно воспользоваться формулой для числа размещений с повторениями, как в задаче 7b. Здесь количество элементов для выбора n = 2 цифры, количество возможных повторов одного элемента k = 3 раза, цифра в трёхзначном числе может повториться трижды, например, 777. Таким образом, искомое число вариантов 23 = 8. Но можно и проще, так как эта задача полностью аналогична задаче 8b. Также используем И-правило, выбирая одну из 2-ух цифр независимо для каждой из трёх позиций, 2·2·2 = 8. В свою очередь, в задаче 8b можно было воспользоваться формулой для числа размещений с повторениями: 33 = 27. Дело в том, что формула как раз выводится с применением И-правила и теми же рассуждениями, какие описаны в решении этих задач. |
Решение.
Классический случай размещений: выбираем из 3-ёх элементов без повторов и размещаем на 2-ух позициях - в разряд десятков и в разряд единиц. Число размещений определяем по формуле А32 = 3!/(3 - 2)! = 3!/1! = 2·3 = 6. |
| Задача 10a | Задача 10b |
| Сколько нечетных трёхзначных чисел можно составить из цифр 3, 4, 8, 6? (Цифры в записи числа не могут повторяться). | Сколько различных трёхзначных чисел можно составить из цифр 7, 6, 5, 0, если цифры в записи числа не могут повторяться? |
| Ответ: 6 | Ответ: 18 |
|
Решение.
Искомое число должно оканчиваться цифрой 3, так как 4, 6 и 8 делятся на 2 без остатка. Поэтому позиция единиц у нас уже занята, и остается разместить 3 цифры на 2-ух позициях - десятков и сотен. Число размещений из 3 по 2 определяем по формуле А32 = 3!/(3 - 2)! = 3!/1! = 2·3 = 6. |
Решение.
Сначала определим, сколько всего можно составить групп из 4-ёх заданных цифр по 3 с учётом порядка следования и без повторений. А43 = 4!/(4 - 3)! = 4!/1! = 1·2·3·4/1 = 24. Но не все эти группы будут трёхзначными числами. Те из них, которые начинаются с цифры 0, по существу, - двузначные числа. Сколько таких групп? Если на первом месте стоит 0, то на позициях десятков и единиц располагаются 2 цифры из оставшихся 3-ёх. Определяем число размещений из 3 по 2 А32 = 3!/(3 - 2)! = 3!/1! = 2·3 = 6. Вычитая из общего числа вариантов лишние, получим 24 - 6 = 18. |
| Задача 11a | Задача 11b |
| Сколько четных трёхзначных чисел можно составить из цифр 3, 4, 5, 6? (Цифры в записи числа не могут повторяться). | Сколько четных трёхзначных чисел можно составить из цифр 3, 4, 5, 6? (Цифры в записи числа могут повторяться). |
| Ответ: 12 | Ответ: 32 |
|
Решение.
Четными будут числа, оканчивающиеся на 4 ИЛИ на 6. Поэтому подсчитаем количество вариантов, заканчивающихся на одну из этих цифр, а затем воспользуемся правилом сложения (ИЛИ-правилом), чтобы определить общее число вариантов. Если число оканчивается 4-кой, то на позициях сотен и десятков могут находиться любые 2 цифры из оставшихся 3-ёх. Число размещений из 3 по 2 А32 = 3!/(3 - 2)! = 3!/1! = 2·3 = 6. Также получается, если число оканчивается 6-кой: А32 = 6. Общее число вариантов 6 + 6 = 12. |
Решение.
Так же, как в предыдущем случае рассмотрим отдельно числа, заканчивающиеся 4-кой и 6-кой, а затем воспользуемся правилом сложения вариантов. Пусть позиция единиц у нас занята цифрой 4. В этот раз в позиции десятков может стоять любая из четырёх заданных цифр (4 варианта) И в позиции сотен любая из этих же 4-ёх цифр (4 варианта), всего 4·4 = 16. Если число оканчивается на 6, теми же рассуждениями получаем еще 16 вариантов. Всего 16 + 16 = 32. |
| Задача 12a | |
| Сколько различных дробей можно составить с использованием цифр 2, 3, 4? (В числителе и знаменателе не может быть одна и та же цифра.) | |
| Ответ: 18 | |
|
Решение.
Заметим, что не только в числителе и знаменателе не может быть одна и та же цифра, но цифры вообще не могут повторяться, иначе задача не имела бы смысла. В число дробей входили бы, например, 2/3, 2/33, 2/333, 2/3333 и т.п. Таких вариантов бесконечное число. Далее заметим, что текст "с использованием цифр" может быть понят неоднозначно: с использованием всех трёх или с выбором из них. Здесь рассмотрим более общий случай - с выбором. Выборка не может состоять меньше, чем из двух цифр, чтобы хватило и на числитель, и на знаменатель. Дроби бывают правильные, в которых знаменатель больше числителя, например, 4/23, и неправильные, в которых числитель больше знаменателя, например, 23/4. Таким образом, возможны такие виды дробей */* ИЛИ **/* ИЛИ */**, где звёздочкой обозначено место для одной из заданных цифр. Подсчитаем число вариантов для каждого вида дроби отдельно, а затем сложим результаты в соответствии с ИЛИ-правилом. Случай */* определяется числом размещений из 3 по 2, так как используем не все заданные цифры и важен порядок следования (например, сравните 4/3 и 3/4). А32 = 3!/(3 - 2)! = 3!/1! = 2·3 = 6. Случай */** определяется числом перестановок из 3, так как для такой дроби нужно использовать все заданные цифры. Дроби будут различаться только расположением цифр по позициям. P3 = 3! = 1·2·3 = 6. Случай **/* аналогичен предыдущему, также определяется числом перестановок из 3. P3 = 6. Общее число вариантов 6 + 6 + 6 = 18. Если вы получили ответ 12, а не 18, обязательно разберитесь почему. Это иначе понятое условие задачи? Забыты неправильные дроби? Ошибка в комбинаторике? | |
Комментарии.
O формуле для числа сочетаний.
Как известно, деление может быть обозначено разными символами: __, /, :
Косую черту и двоеточие удобно использовать для записи формулы в одну строку, что здесь и сделано для экономии места в таблице. Горизонтальную черту используют для записи дроби. Если формулу для числа сочетаний записать дробью, то хорошо видно, как она сокращается.
Как известно, деление может быть обозначено разными символами: __, /, :
Косую черту и двоеточие удобно использовать для записи формулы в одну строку, что здесь и сделано для экономии места в таблице. Горизонтальную черту используют для записи дроби. Если формулу для числа сочетаний записать дробью, то хорошо видно, как она сокращается.
O формуле для числа размещений.
Формулу для числа размещений иногда записывают дробью с факториалами, а иногда строкой - группой сомножителей. Разумеется, оба варианта переходят друг в друга в результате преобразований. На мой взгляд, обе формулы хорошо запоминаются, первая - потому, что компактнее, вторая - потому, что хорошо произносится: "начинаем с n и записываем m сомножителей".
Формулу для числа размещений иногда записывают дробью с факториалами, а иногда строкой - группой сомножителей. Разумеется, оба варианта переходят друг в друга в результате преобразований. На мой взгляд, обе формулы хорошо запоминаются, первая - потому, что компактнее, вторая - потому, что хорошо произносится: "начинаем с n и записываем m сомножителей".
Выборки с повторениями.
В школьном курсе основное внимание уделяется классическим типам выборок. В комбинаторике также выведены формулы для выборок с повторениями, но в них нет необходимости для решения задач вашего уровня трудности. Достаточно просто разумных соображений и знания основных формул и правил. Привожу здесь формулы для выборок с повторениями только для того, чтобы вы знали о их существовании и при желании могли использовать для проверки своих ответов.
Здесь для сочетаний и размещений k - объем выборки, n - количество элементов множества, из которого выбираем.
Для перестановок n - количество переставляемых элементов, n1, n2, ... nk - число повторений. Например, в слове "темперамент" 11 букв (n = 11), буква "т" повторяется дважды (n1 = 2), буква "е" - трижды (n2 = 3) и буква "м" - дважды (n3 = 2). Число возможных перестановок букв в этом слове 11!/2!/3!/2!
В школьном курсе основное внимание уделяется классическим типам выборок. В комбинаторике также выведены формулы для выборок с повторениями, но в них нет необходимости для решения задач вашего уровня трудности. Достаточно просто разумных соображений и знания основных формул и правил. Привожу здесь формулы для выборок с повторениями только для того, чтобы вы знали о их существовании и при желании могли использовать для проверки своих ответов.
Здесь для сочетаний и размещений k - объем выборки, n - количество элементов множества, из которого выбираем.
Для перестановок n - количество переставляемых элементов, n1, n2, ... nk - число повторений. Например, в слове "темперамент" 11 букв (n = 11), буква "т" повторяется дважды (n1 = 2), буква "е" - трижды (n2 = 3) и буква "м" - дважды (n3 = 2). Число возможных перестановок букв в этом слове 11!/2!/3!/2!
Перейти на главную страницу сайта.
Понравились материалы сайта? Узнайте, как поддержать сайт и помочь его развитию.
Есть вопросы? пожелания? замечания?
Обращайтесь -
mathematichka@yandex.ru
Внимание, ©mathematichka. Прямое копирование материалов на других сайтах запрещено. Ставьте гиперссылку.
Материал с сайта