Решение комбинаторных задач

Решение комбинаторных задач

Выполнила: ученица 9Б класса МБОУ «СОШ № 47» Советского р-на города Казани Николаева Светлана Андреевна 2017-2018 учебный год

Комбинаторика

• Это раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана с другими областями математики — алгеброй, геометрией, теорией вероятностей и применяется в различных областях знаний (например, в генетике, информатике, статистической физике).

• Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

В кружок бального танца записались Петя, Коля, Витя, Олег, Таня, Оля, Наташа, Света. Какие танцевальные пары девочки и мальчика могут образоваться?

Решение :

1) Таня - Петя, 2) Таня - Коля, 3) Таня - Витя, 4) Таня - Олег, 5) Оля - Петя, 6) Оля - Коля, 7) Оля - Витя, 8) Оля - Олег , 9) Наташа - Петя, 10) Наташа - Коля, 11) Наташа - Витя, 12) Наташа - Олег, 13) Света - Петя, 14) Света - Коля, 15) Света - Витя, 16) Света - Олег.

У мамы m яблок и n груш. Каждый день в течение пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?

Решение.

• Имеем набор {я, я, г, г, г}. Всего перестановок пятиэлементного множества
• 5, но мы не должны учитывать перестановки, в которых объекты одного типа меняются
• местами несколько раз, поэтому нужно поделить на возможное число таких перестановок:
• 2 · 3. Получаем в итоге
• 5/2*3=3*4*5/2*3=10 Ответ: 10 способов.

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

Решение.

Пронумеруем места в купе (с № 1 по № 4) и будем «выдавать» каждому из трех членов семьи номер места. Из 4 элементов (номе­ров мест) будут делаться выборки по 3 элемента, при этом важен не только состав выборки, но и порядок расположения в ней элемен­тов (кто именно и на каком месте поедет). Число способов равно числу размещений из 4 по 3:

Можно рассуждать, непосредственно применяя правило произ­ведения: для первого члена семьи можно выбрать любое из 4 мест, для второго - любое из 3 оставшихся, для третьего - любое из двух оставшихся, всего 4*3*2 = 24 способа рассадить семью в купе.

Ответ: 24 способа.

Сколькими способами можно расставить на полке 8 различных книг?

Решение.

8! = 1*2*3*4*5 6*7*8= 40320. Ответ:40320

Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числе повторяться не могут.

Решение.

Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок учитывается и не все элементы одновременно выбираются. Значит, это соединение – размещение из 7 элементов по 3. Воспользуемся формулой для числа размещений: A7^3 = 7(7 – 1)(7 – 2) = 7 · 6 · 5 = 210 чисел.

• Ответ: 210.

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

Решение. 1) если выбрали одно имя то количество способов его выбрать = 300

2) если два имени:

300!/(2!*(300-2)!)=44850 (комбинация из 300 по 2)

3) если 3 имени

300!/(3!*(300-3)!)=4455100 (комбинация из 300 по 3)

300+44850+4455100=4500250 способов

Ответ: 4500250 способов

Сколько существует семизначных телефонных номеров, в которых все цифры разные, а номер не может начинаться с нуля?

Решение.

На первый взгляд эта задача такая же, как и предыдущая, но сложность в том, что надо не учитывать те соединения, которые начинаются с нуля. Значит необходимо из существующих 10-ти цифр составить все семизначные номера телефонов, а потом от полученного числа отнять количество номеров, начинающихся с нуля. Формула будет иметь вид:

A107 – A96 = 10 · 9 · 8 · 7 · 6 · 5 · 4 – 9 · 8 · 7 · 6 · 5 · 4 = 544 320

В урне лежат 10 жетонов с числами 1,2,3, ..., 10. Из нее, не выбирая, вынимают 3 жетона. Во скольких случаях сумма написанных на них чисел не меньше 9

• Решение. Неблагоприятные исходы: (1,2,3), (1,2,4), (1,2,5), (1,3,4) (в этих случаях сумма чисел меньше 9). Всего исходов . Значит, всего благоприятных исходов С3\10. С3\10 – 4=120 – 4=116

Ответ: в 116 случаях

На загородную прогулку поехали 92 человека. Бутерброды с колбасой взяли 47 человек, с сыром – 38 человек, с ветчиной – 42 человека, и с сыром и с колбасой – 28 человек; и с колбасой и с ветчиной – 31 человек, и с сыром и с ветчиной – 26 человек. Все три вида бутербродов взяли 25 человек, а несколько человек вместо бутербродов захватили с собой пирожки. Сколько человек взяли с собой пирожки?

Решение.

Решение задачи становится очевидно, если описать условие с помощью диаграммы Венна (в виде пересекающихся кругов, изображающих множества), приняв следующие обозначения:

• А - множество туристов, которые взяли с собой бутерброды с колбасой;
• В - множество туристов, которые взяли с собой бутерброды с сыром;
• С - множество туристов, которые взяли с собой бутерброды с ветчиной.
• Начертим диаграмму…
• На этой диаграмме видно:
• а) Количество туристов, взявших с собой бутерброды всех трех видов (25).
• б) Количество туристов, взявших с собой бутерброды каких-либо двух видов (с учетом туристов, взявших с собой бутерброды всех трех видов) – соответственно 3, 1 и 6 человек (чтобы общее число этих людей в соответствии с условием было равно 28, 26 и 31 человек).
• в) Количество туристов, взявших с собой бутерброды какого-либо одного вида (с учетом туристов, перечисленных в пунктах а и б) – соответственно 13, 9 и 10 человек (чтобы общее число этих людей в соответствии с условием было равно 47, 38 и 42 человека).
• Тогда общее число любителей бутербродов составит 25 + 3 + 1 + 6 + 13 + 9 + 10 = 67 человек, Следовательно, пирожки взяли с собой 92 – 67 = 25 человек.

Ответ:25 человек .

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

Решение.

• На левую руку можно выбрать любую из 6 перчаток на левые руки. На правую – любую из пяти перчаток на правую руку. Значит, всего способов 6 * 5=30.

Ответ: 30 способов

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

Решение. Собираем все варианты в таблицу.

• Булочка (Б)Ватрушка (В)Пирожок (П)Сок (С)Чай (Ч)
• В таблице 2 строки и 3 столбца, которые образуют 6 клеток. Так как выбор еды и напитка происходит независимо, то в каждой клетке будет стоит один из возможных вариантов завтрака. Значит, всего вариантов столько, сколько клеток в таблице, то есть 6. Напиток можно выбрать двумя способами (сок или чай), а еду тремя способам.

2 ∙ 3 = 6 столовая предлагает 6 вариантов завтрака.

Ответ : 6 способов

Из города А в город В ведут пять дорог, а из города В в город С — три дороги. Сколько путей, проходящих через В, ведут из А в С?

Решение.

• Представим задачу в виде графа. Очевидно, что какой бы путь не выбрал объект, продвигаясь из пункта А в пункт В, по достижении пункта В он может выбрать любой из трех путей, позволяющих ему добраться из В в С.

Следовательно, путей, ведущих из А в С и проходящих через В, существует 5 * 3 = 15. Ответ : 15 способ

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

Решение.

• Разместим четверых желающих пассажиров лицом к паровозу (на 5 местах). Это можно сделать А способами, разместим троих желающих пассажиров спиной к паровозу. Это можно А сделать способами, Осталось 3 «безразличных» пассажира и для них 3 места. Их можно разместить 3 способами. Значит, всего способов размещения А*А=43200.

Ответ: 43200 способов

В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить в нем 12 открыток? Сколькими способами можно купить 8 открыток? Сколькими способами можно купить 8 различных открыток?

Решение.

число сочетаний из 10 по 8

С=(10!)/((8!)*(10-8!))=45 способов

Ответ:45 спсобов

В магазине «Все для чая» есть еще 4 чайные ложки. Сколькими способами можно купить комплект из чашки, блюдца и ложки?

Решение:

Выберем любой из 15 комплектов предыдущей задачи. Его можно дополнить ложкой четырьмя различными способами. Поэтому общее число возможных комплектов равно 60 (60 = 15 • 4 = 5 • 3 • 4). Ответ : 60 способов