Комбинаторные задачи
олимпиадные задания по алгебре (5 класс) на тему

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

Задача

Сколькими способами можно выбрать гласную и согласную буквы слова «полка»?

Решение: в этом слове две гласные буквы (о, а) и три согласные (п, л, к). Каждый искомый выбор задается картежом (а(1), а(2)), где а(1) – гласная буква, а(2) – согласная. Так как а(1) можно выбрать двумя способами, а а(2) тремя способами, то кортеж (а(1), а(2)) можно по правилу произведения выбрать 2*3=6 способами. Ответ: 6 способов.

Задача

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

 Решение: Для каждого случая составим таблицу вариантов:N = 3*3 =9  N = 3*4 = 12 Ответ: 1) N = 9; 2) N = 12.

Правило произведения.

Задача

 Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?

Решение: Решим задачу с помощью полного графа с четырьмя вершинами А,Б,В,Г. Обозначенными первыми буквами имени каждого из мальчиков. В полном графе проводятся всевозможные ребра. В данном случае отрезки ребер обозначают органные шахматные партии. Из рисунка видно, что граф имеет 6 ребер, значит, и партий было сыграно 6. Ответ: 6 партий.

Задача

Антон, Борис, Василий купили 3 билета на 1,2,3 места первого ряда на футбольный мачт. Сколькими способами они могут занять имеющиеся места?

Решение: на 1-е место может сесть любой из трех друзей, на 2 любой их двух оставшихся, а на 3 последний. Сказанное изобразим с помощью дерева, помещая в вершины графа первые буквы А,Б и В: 1 место 2 место 3 место упорядочная тройка друзей. Ответ: 6.

 Задача  

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

 Решение: Каждый путь школою видов задается картежом (а(1), а(2)), где а(1) – один из путей, соединяющих В и С. Так как по условию а(1) можно выбрать 5 способами, а(2) – 3способами, то картеж (а(1), а (2)) можно по правилу произведения составить 5*3 = 15 способами. Ответ: 15 путей.

 Задача

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

Решение: Эту задачу тоже можно решить по правилу произведения. Перчатка на левую руку может быть выбрана 6 способами. После того как она выбрана, перчатку на правую руку можно выбрать лишь 5 способами. (Размеры перчаток  должны быть разными). Поэтому всего имеет 6*5=  30 способов. Ответ: 30 способов.

 Задача

сколькими способами могут быть распределены золотая и серебренная медали по итогам первенства по футболу, если число команд 12.  Решение: На золотую медаль претендуют 12 команд, на серебренную 11 команд. (одна получит золотую медаль). По правилу произведения получаем 12 * 11 = 132 способа. Ответ: 132 способа.

Задачи, на перебор вариантов происходящих событий.

Задача 

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

1 способ: Перечислим возможные варианты.

2 способ: Дерево возможностей

3 способ: Правило умножения заключается в том, что для того, чтобы найти число всех возможных исходов независимого проведения двух испытаний А и В, следует перемножить число всех исходов испытания А и число всех исходов испытания В, т.е. в нашей задаче имеется 3 элемента: первое, можно выбрать 3 раза, второе – 3 раза и третье – 2раза, получаем: 3х3х2=18.Ответ: 18.

Задача

Мисс Марпл, расследуя убийство, заметила отъезжающее от дома мистера Дэвидсона такси. Она запомнила первую цифру «2». В городке номера машин были трехзначные и состояли из цифр 1, 2, 3, 4 и 5. скольких водителей, в худшем случае, ей придется опросить, чтобы найти настоящего убийцу?

Используя правило умножения, получаем: 5*5=25.Ответ: 25 водителей.

Задача

Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 5, 7, используя в записи числа каждую из них не более одного раза?

Реш. Первую цифру трехзначного числа можно выбрать четырьмя способами, т.к. после выбора остается три, то вторую цифру можно выбрать из оставшихся цифр уже тремя способами. Наконец, третью цифру можно выбрать двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 4 * 3 * 2=24.Ответ: 24.

Задача 

Сколько четных двузначных чисел можно составить из цифр 0, 2, 3, 6, 7, 9? Используя правило умножения, получаем: 5*3=15 Ответ: 15

Задача 

Свете на день рождения подарили 4 плюшевых игрушки, 2 мяча и 5 кукол. Мама положила все игрушки в большую коробку. Сколькими способами Света сможет достать из коробки 1 плюшевую игрушку, 1 мяч и 1 куклу?Используя правило умножения, получаем: 2*4*5=40.Ответ:40.

Задачи на перестановки.

Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке. Число перестановок из n элементов обозначается символом Рn (Р из n элементов). Например.

Задача 

в книжном шкафу на полке стоят 3 книги, как  эти книги можно переставить?

Р3= 3*2*1= 6 = 3!

Задача 

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

Р5 = 5! = 5*4*3*2*1 = 120.

Задача

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

Число способов равно числу перестановок из 8 элементов. По формуле числа перестановок находим, что Р8=8! = 1*2*3*4*5*6*7*8 = 40320.

Задача

Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0,2,4,6?

Решение: из цифр 0,2,4,6 можно получить Р4 перестановок. Из этого числа надо исключить те перестановки, которые начинаются с 0, т.к. натуральное число не может начинаться с цифры 0. Число таких перестановок равно Р3. значит, искомое число четырехзначных чисел равно Р4-Р3 = 4!-3! = 24 – 6= 18.

Задачи на размещения.

Размещением из n элементов по k (k меньше или равно n) называется любое множество, состоящее из любых k элементов, взятых в определенном порядке из данных n элементов. Обозначение:   ( читают: «А из n по k).

 Например : Пусть имеется три шара и две пустых ячейки. В пустые ячейки можно разместить по два шара.

  Решение: из трех элементов по два будут наборы (1,2), (2,1), (1,3), (3,1), (2,3), (3,2).Размещения считаются различными, если они отличаются самими элементами или порядком их расположения. Например: (1,2), (2,1), (1,3), (3,1) в нашем примере.Число размещений можно найти не выписывая сами размещения. Будем рассуждать так: первый элемент можно выбрать тремя способами, т.к. им может быть любой из трех, для каждого выбранного первого элемента можно двумя способами выбрать второй.В результате получаем:  = 3*2 = 6.

Задача 

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

 Решение:  = 8*7*6*5 = 1680.

Задача

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

Решение: А105=10*9*8*7*6 = 30240 способов.

Задача

В 9 классе 15 предметов. Завучу школы нужно составить расписание на субботу, если в этот день 5 уроков. Сколько различных вариантов расписания можно составить, если все уроки различны?

Решение: из 15 предметов 5 любых можно выбрать А155= 15*14*13*12*11= 360360.

Задача

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

 Решение: А83=8*7*6 = 336.

Задачи на сочетания.

Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов. Обозначение:  (читают С из n по k).

Задача 

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

Решение: из трех элементов (1;2;3) по два будут наборы (1,2),(1,3),(2,3). В отличии от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания различны, если отличаются друг от друга хотя бы одним элементом. Например: (1,2),(1,3). В нашем примере, в каждом сочетании выполнимы все перестановки. Число таких перестановок равно Р2. В результате получим все возможные комбинации из 3 элементов по 2, которые отличаются либо самими элементами, либо порядком элементов, т.е.  все размещения из 3 элементов по 2. всего мы получим размещений. Значит если количество размещений разделить на количество перестановок, получим количество сочетаний из трех элементов по два.  Отсюда .

Задача

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

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

Задача

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

Решение: В этой задаче нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5. В каждом сочетании выполнимы 5 перестановок т.е.Р5= 1*2*3*4*5, в результате получим все возможные комбинации из 20 элементов по 5: А205=20*19*18*17*16.