Комбинаторные задачи с решением

Комбинаторика - раздел математики, занимающийся вопросом выбора и расположения элементов некоторого конечного множества в соответствии с заданными условиями.

Рассмотрим примеры задач комбинаторики.

Пример №1

Сколькими способами можно выбрать путь из начала координат 0(0,0) в точку В(6,4), если каждый шаг равен единице, но его можно совершать только вправо или вверх? Сколько таких путей проходит через точку А(2,3)?

Решение. Весь путь занимает 10 шагов (четыре вверх и шесть вправо). Для планирования пути следует решить, какие именно по счету четыре шага следует сделать вверх, а остальные шесть — вправо. Выбор бесповторный и нас интересует только состав выбора. Поэтому в описанных условиях всего путей из точки О в точку В будет

Рассуждая подобным образом легко видеть, что путей из точки О в точку А существует а путь из точки А в точку В можно выбрать способами. По комбинаторному принципу всего путей через точку А существует 10 • 5 = 50.

Ответ. 210; 50.

Пример №2

Сколькими способами можно выбрать путь из начала координат 0(0,0) в точку если каждый шаг равен 1, но его можно совершать только вправо или вверх? Сколько таких путей проходит через точку (См. пример 1.1 и исходные данные.)

Исходные данные к задаче 1.1.

Пример №3

В городе с идеальной прямоугольной планировкой (сеть улиц в этом городе изображена на рис. 1.1) из пункта А выходят человек. Половина из них идет по направлению половина — по направлению Дойдя до первого перекрестка, каждая группа разделяется так, что половина ее идет по направлению половина — по направлению Такое же разделение происходит на каждом перекрестке. Требуется перечислить перекрестки, на которых окажутся люди после прохождения N улиц (отрезков на рис. 1.1), и сколько людей окажется на каждом из этих перекрестков.

Решение. Каждый человек пройдет N улиц и окажется на одном из перекрестков Координаты перекрестков указаны в предположении, что точка А служит началом координат.

На каждом перекрестке для каждого человека производится выбор из двух возможностей: идти в направлении или в направлении Поэтому всего возможных путей будет . Из этого следует, что каждый путь пройдет только один человек.

В пункте окажется столько человек, сколько различных путей ведет в этот пункт из точки А. Чтобы попасть в пункт необходимо из N улиц выбрать бесповторным способом к улиц в направлении . Это можно сделать способами.

Ответ.

Пример №4

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

Решение. Поставим эти предметы в ряд. Между ними будет промежуток. В любые из этих промежутков поставим разделяющие перегородки. Тогда все предметы разделятся на непустых частей. Первую часть передадим первому лицу, вторую — второму и т.д. Выбрать же промежуток из промежутка можно способами. Заметим, что вообще предметов распределить между лицами можно способами.

Ответ.

Пример 1.4.

Сколькими способами можно распределить 6 яблок, 8 груш и 10 слив между тремя детьми? Сколькими способами это можно сделать так, чтобы каждый ребенок получил по меньшей мере одно яблоко, одну сливу и одну грушу?

Решение. Яблоки в соответствии с формулой (1.5) можно распределить способами, груши — , а сливы способами. По комбинаторному принципу всего способов Если необходимо, чтобы каждый ребенок получил по меньшей мере одно яблоко, одну грушу и одну сливу, то в соответствии с формулой предыдущего примера имеем способов.

Ответ. 83160; 7560.

Пример №5

Сколько цифр в первой тысяче не содержат в своей записи цифры 5?

Решение. Для записи любой из цифр 000, 001, 002,..., 999 необходимо трижды выбрать повторным способом одну из десяти цифр, поэтому и получается всего чисел. Если цифру 5 исключить, то выбор можно производить только из девяти цифр: 0, 1,2, 3, 4, 6, 7, 8, 9. Поэтому всего получится чисел в первой тысяче, в записи которых нет цифры 5.

Ответ. 729.

Пример №6

Сколько шестизначных чисел содержат в записи ровно три различных цифры?

Решение. Заметим, что всего шестизначных чисел имеется , так как первая цифра может быть любой (исключая нуль), а остальные пять могут быть выбраны способами.

Выбрать три ненулевых цифры можно способами. Из выбранных трех цифр можно составить шестизначных чисел, из двух — , а из одной — шестизначное число. По формуле (1.7) получаем, что существует шестизначных чисел, в записи которых есть только три заданные цифры. Поэтому общее число шестизначных чисел, в записи которых имеются три отличные от нуля цифры, равно

Учтем теперь возможность использования нуля. К нулю нужно добавить две цифры, что можно сделать способами. Если, например, были выбраны цифры 0, 2, 5, то первой цифрой должна быть 2 или 5. К этой первой цифре в соответствии с формулой (1.7) можно добавить комбинаций остальных пяти цифр. Тогда всего шестизначных чисел, состоящих из 0, 2, 5 будет Всего же шестизначных чисел, записанных тремя цифрами, среди которых встречается нуль, ровно Всего чисел, удовлетворяющих условиям задачи, имеется

Ответ. 58320.

Пример №7

В саду есть цветы десяти наименований (розы, флоксы, ромашки и т. д.).

а) Сколькими способами можно составить букет из пяти цветков (не принимая во внимание совместимость растений и художественные соображения)?

б) Сколькими способами можно составить букет из пяти различных цветков?

в) Сколькими способами можно составить букет из пяти цветков так, чтобы в букете непременно было хотя бы по одному цветку двух определенных наименований

Решение. а) Если запрета на повторение цветков нет, то мы имеем дело с повторным выбором и нас интересует только состав. Поэтому по формуле (1.5) получаем способа.

б) Если цветы должны быть разными, то способ выбора бесповторный и букет можно составить способами.

в) Отберем по одному цветку каждого из двух названных наименований. Три остальных цветка можно выбрать из 10 возможных способами.

Ответ. а) 2002; б) 504; в) 220.

Пример №8

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

Решение. Ясно, что яблоки можно разложить способом (в первую корзину можно не положить яблок совсем, положить одно яблоко, два яблока, …, все яблоки). Те же рассуждения в отношении груш и персиков дают соответственно комбинаций. По комбинаторному принципу всего будет способов.

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

Ответ.

Пример №9

Требуется найти число натуральных делителей натурального числа .

Решение. Разложим на простые множители:

где – различные простые числа. (Например, )

Заметим, что при разделении числа на любые два множителя и простые сомножители распределятся между и . Если сомножитель, в число входит то разложение (1.8) примет вид:

Так что разложение на два сомножителя сводится к разделению каждого из чисел на две части, а это можно сделать способами.

Ответ. .

Пример №10

Сколькими способами легкоатлет, собираясь на тренировку, может выбрать себе пару спортивной обуви, имея 5 пар кроссовок и 2 нары кед?

Очевидно, что выбрать одну из имеющихся пар обуви, кроссовки или кеды, можно 5 + 2 = 7 способами.

Обобщая, приходим к комбинаторному правилу сложения:

• если некоторый элемент можно выбрать способами, а элемент (независимо от выбора элемента ) — способами, то выбрать или можно способами.

Это правило справедливо также для трех и более элементов.

Пример №11

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

Пирожок можно выбрать 4 способами и к каждому пирожку выбрать сок 3 способами (рис. 76). Следовательно, учащийся имеет вариантов выбора завтрака.

Обобщая, приходим к комбинаторному правилу умножения:

• если некоторый элемент можно выбрать , способами и после каждого такого выбора (независимо от выбора элемента ) другой элемент можно выбрать способами, то пару объектов и можно выбрать способами.

Это правило справедливо также для трех и более элементов.

Пример №12

Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, если в числе: 1) цифры не повторяются; 2) цифры могут повторяться?

Решение:

1) Первую цифру можем выбрать 4 способами (рис.77). Так как после выбора первой цифры их останется три (ведь цифры в нашем случае повторяться не могут), то вторую цифру можем выбрать 3 способами.И наконец, третью цифру можем выбрать из оставшихся двух - то есть 2 способами. Следовательно, количество искомых трехзначных у чисел будет равно .

2) Применим комбинаторное правило умножения. Так как цифры в числе могут повторяться, то каждую из цифр искомого числа можно выбрать 4 способами (рис. 78), и тогда таких чисел будет .

Ответ. 1) 24 числа; 2) 64 числа.

Отметим, что решить подобные задачи без применения комбинаторного правила умножения можно только путем перебора всех возможных вариантов чисел, удовлетворяющих условию задачи. Но такой способ решения является слишком долгим и громоздким.

Пример №13

Сколько четных пятизначных чисел можно составить из цифр 5, 6, 7, 8, 9, если цифры в числе не повторяются?

Решение:

Четное пятизначное число можно получить, если последней его цифрой будет 6 или 8. Чисел, у которых последней является цифра 6, будет (рис. 79),

а тех, у которых последней является цифра 8, - также 24. По комбинаторному правилу сложения всего четных чисел будет .

Ответ. 48.

Пример №14

Азбука племени АБАБ содержит всего две буквы - «а» и «б». Сколько слов в языке этого племени состоит: 1) из двух букв; 2) из трех букв?

Решение:

1) аа, ба, аб, бб (всего четыре слова); 2) ааа, ааб, аба, абб, ббб, бба, баб, баа (всего восемь слов).

Заметим, что найденное количество слов соответствует комбинаторному правилу умножения. Так как на каждое место есть два «претендента» - «а» и «б», то слов, состоящих из двух букв, будет , а из трех букв - .

Пример №15

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

Решение:

Капитаном можно выбрать любого из 11 игроков, а его заместителем - любого из 10 оставшихся игроков. Таким образом (по правилу умножения), имеем разных способов.

Пример №16

В Стране Чудес 10 городов и каждые два из них соединяет авиалиния. Сколько авиалиний в этой стране?

Решение. Так как каждая авиалиния соединяет два города, то одним из них может быть любой из 10 городов, а другим - любой из 9 оставшихся. Следовательно, количество авиалиний равно . Но при этом каждую из авиалиний мы учли дважды. Поэтому всего их будет .

Комбинаторные задачи неразрывно связаны с задачами теории вероятностей, еще одного раздела математики.

В ХIII-ХII в. до н. э. встречаются упоминания о вопросах, близких к комбинаторным. Некоторые комбинаторные задачи решали и в Древней Греции. В частности, Аристоксен из Тарента (IV в. до н. э.), ученик Аристотеля, перечислил различные комбинации длинных и коротких слогов в стихотворных размерах. А Папп Александрийский в IV в. н. э. рассматривал число пар и троек, которые можно получить из трех элементов, допуская их повторения. Некоторые элементы комбинаторики были известны и в Индии во II в. до н. э. Индийцы умели вычислять числа, известные нам как коэффициенты формулы бинома Ньютона. Позднее, в VIII в. н. э., арабы нашли и саму эту формулу, и ее коэффициенты, которые сейчас вычисляют с помощью комбинаторных формул или «треугольника Паскаля».

Свой нынешний вид упомянутые комбинаторные формулы приобрели благодаря средневековому ученому Леви бен Гершону (XIV в.) и французскому математику П. Эригону (XVII в.).

В III в. н. э. сирийский философ Порфирий для классификации понятий составил специальную схему, получившую название «древо Порфирия». Сейчас подобные деревья используются для решения определенных задач комбинаторики в разнообразных областях знаний. Некоторые ранее неизвестные комбинаторные задачи рассмотрел Леонардо Пизанский (Фибоначчи) в своей знаменитой «Книге абака» (1202 г.), в частности, о нахождении наименьшего набора различных гирь, позволяющего взвесить груз с любой целочисленной массой, не превышающей заданного числа. Со времен греческих математиков были известны две последовательности, каждый член которых получали по определенному правилу из предыдущих, - арифметическая и геометрическая прогрессии. А Фибоначчи впервые в одной из задач выразил член последовательности через два предыдущих, используя формулу, которую назвали рекуррентной. В дальнейшем метод рекуррентных формул стал одним из мощнейших для решения комбинаторных задач.

Как ни странно, развитию комбинаторики в значительной степени способствовали азартные игры, которые были очень популярны в XVI в. В частности, вопросами определения разнообразных комбинаций в игре в кости в то время занимались такие известные итальянские математики, как Д. Кардано, H. Тарталья и др. А наиболее полно изучил этот вопрос в XVII в. Галилео Галилей.

Современные комбинаторные задачи высокого уровня сложности связаны с объектами в других отраслях математики: определителями, конечными геометриями, группами, математической логикой и т. п.