Пракикум «Решение задач по комбинаторике»
Комбинаторика – это раздел математики, посвящённый решению задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами. Комбинаторика изучает комбинации и перестановки предметов, расположение элементов, обладающее заданными свойствами. Обычный вопрос в комбинаторных задачах: сколькими способами….
К комбинаторным задачам относятся также задачи построения магических квадратов, задачи расшифровки и кодирования.
Рождение комбинаторики как раздела математики связано с трудами великих французских математиков 17 века Блеза Паскаля (1623–1662) и Пьера Ферма (1601–1665) по теории азартных игр. Эти труды содержали принципы определения числа комбинаций элементов конечного множества. С 50-х годов 20 века интерес к комбинаторике возрождается в связи с бурным развитием кибернетики.
Основные правила комбинаторики – это правило суммы и правило произведения.
Если некоторый элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то выбор «либо А, либо В» можно сделать n + m способами.
Например, Если на тарелке лежат 5 яблок и 6 груш, то один плод можно выбрать 5 + 6 = 11 способами.
Если элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то пару А и В можно выбрать n • m способами.
Например, если есть 2 разных конверта и 3 разные марки, то выбрать конверт и марку можно 6 способами (2 • 3 = 6).
Правило произведения верно и в том случае, когда рассматривают элементы нескольких множеств.
Например, если есть 2 разных конверта, 3 разные марки и 4 разные открытки, то выбрать конверт, марку и открытку можно 24 способами (2 • 3 • 4 = 24).
Произведение всех натуральных чисел от 1 до n включительно называется n – факториалом и обозначается символом n!
Например, 5! = 1 • 2 • 3 • 4 • 5 = 120.
Принято считать 0! равным 1.
Число перестановок из n равна n!
Например, если есть 3 шарика – красный, синий и зелёный, то выложить их в ряд можно 6 способами (3 • 2 • 1 = 3! = 6).
Иногда комбинаторная задача решается с помощью построения дерева возможных вариантов.
Например, решим предыдущую задачу о 3-х шарах построением дерева.
Практикум по решению задач по комбинаторике.
ЗАДАЧИ и решения
1. В вазе 6 яблок, 5 груш и 4 сливы. Сколько вариантов выбора одного плода?
6 + 5 + 4 = 15
Ответ: 15 вариантов.
2. Сколько существует вариантов покупки одной розы, если продают 3 алые, 2 алые и 4 жёлтые розы?
3. Из города А в город В ведут пять дорог, а из города В в город С ведут три дороги. Сколько путей, проходящих через В, ведут из А в С?
4. Сколькими способами можно составить пару из одной гласной и одной согласной букв слова «платок»?
гласные: а, о – 2 шт.
согласные: п, л, т, к – 4 шт.2 • 4 = 8
Ответ: 8 способами.
5. Сколько танцевальных пар можно составить из 8 юношей и 6 девушек?
6. В столовой есть 4 первых блюда и 7 вторых. Сколько различных вариантов обеда из двух блюд можно заказать?
Ответ: 28 вариантов.
7. Сколько различных двузначных чисел можно составить, используя цифры 1, 4 и 7, если цифры могут повторяться?
1 цифра – 3 способа
2 цифра – 3 способа
3 цифра – 3 способа3 • 3 = 9
Ответ: 9 различных двузначных чисел.
8. Сколько различных трёхзначных чисел можно составить, используя цифры 3 и 5, если цифры могут повторяться?
1 цифра – 2 способа
2 цифра – 2 способа
3 цифра – 2 способа2 • 2 • 2 = 8
Ответ: 8 различных чисел.
9. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3, если цифры могут повторяться?
1 цифра – 3 способа
2 цифра – 4 способа3 • 4 = 12
Ответ: 12 различных чисел.
10. Сколько существует трёхзначных чисел, у которых все цифры чётные?
Чётные цифры – 0, 2, 4, 6, 8.
1 цифра – 4 способа
2 цифра – 5 способов
3 цифра – 5 способов4 • 5 • 5 = 100
Ответ: существует 100 чисел.
11. Сколько существует четных трёхзначных чисел?
1 цифра – 9 способов (1, 2, 3, 4, 5, 6, 7, 8, 9)
2 цифра – 10 способов (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
3 цифра – 5 способов (0, 2, 4, 6, 8)9 • 10 • 5 = 450
Ответ: существует 450 чисел.
12.Сколько различных трёхзначных чисел можно составить из трёх различных цифр 4, 5, 6?
1 цифра – 3 способа
2 цифра – 2 способа
3 цифра – 1 способ3 • 2 • 1 = 6
Ответ: 6 различных чисел.
13. Сколькими способами можно обозначить вершины треугольника, используя буквы А, В, С, D?
1 вершина – 4 способа
2 вершина – 3 способа
3 вершина – 2 способа4 • 3 • 2 = 24
Ответ: 24 способа.
14. Сколько различных трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5,при условии, что ни одна цифра не повторяется?
1 цифра – 5 способов
2 цифра – 4 способа
3 цифра – 3 способа5 • 4 • 3 = 60
Ответ: 60 различных чисел.
15. Сколько различных трёхзначных чисел, меньших 400, можно составить из цифр 1, 3, 5, 7, 9, если любая из этих цифр может быть использована только один раз?
1 цифра – 2 способа
2 цифра – 4 способа
3 цифра – 3 способа2 • 4 • 3 = 24
Ответ: 24 различных числа.
16. Сколькими способами можно составить флаг, состоящий из трёх горизонтальных полос различных цветов, если имеется материал шести цветов?
1 полоса – 6 способов
2 полоса – 5 способов
3 полоса – 4 способа6 • 5 • 4 = 120
Ответ: 120 способов.
17. Из класса выбирают 8 человек, имеющих лучшие результаты по бегу. Сколькими способами можно составить из них команду из трёх человек для участия в эстафете?
1 человек – 8 способов
2 человек – 7 способов
3 человек – 6 способов8 • 7 • 6 = 336
Ответ: 336 способов.
18. В четверг в первом классе должно быть четыре урока: письмо, чтение, математика и физкультура. Сколько различных вариантов расписания можно составить на этот день?
1 урок – 4 способа
2 урок – 3 способа
3 урок – 2 способа
4 урок – 1 способ4 • 3 • 2 • 1 = 24
Ответ: 24 варианта.
19. В пятом классе изучаются 8 предметов. Сколько различных вариантов расписания можно составить на понедельник, если в этот день должно быть 5 уроков и все уроки разные?
1 урок – 8 вариантов
2 урок – 7 вариантов
3 урок – 6 вариантов
4 урок – 5 вариантов
5 урок – 4 варианта8 • 7 • 6 • 5 • 4 = 6720
Ответ: 6720 вариантов.
20. Шифр для сейфа составляется из пяти различных цифр. Сколько различных вариантов составления шифра?
1 цифра – 5 способов
2 цифра – 4 способа
3 цифра – 3 способа
4 цифра – 2 способа
5 цифра – 1 способ5 • 4 • 3 • 2 • 1 = 120
Ответ: 120 вариантов.
21. Сколькими способами можно разместить 6 человек за столом, на котором поставлено 6 приборов?
6 • 5 • 4 • 3 • 2 • 1 = 720
Ответ: 720 способов.
22. Сколько вариантов семизначных телефонных номеров можно составить, если исключить из них номера, начинающиеся с нуля и 9?
1 цифра – 8 способов
2 цифра – 10 способов
3 цифра – 10 способов
4 цифра – 10 способов
5 цифра – 10 способов
6 цифра – 10 способов
7 цифра – 10 способов8 • 10 • 10 • 10 • 10 • 10 • 10 = 8.000.000
Ответ: 8.000.000 вариантов.
23. Телефонная станция обслуживает абонентов, у которых номера телефонов состоят из 7 цифр и начинаются с 394. На сколько абонентов рассчитана эта станция?
№ телефона 394
10 • 10 • 10 • 10 = 10.000
Ответ: 10.000 абонентов.
24. Имеется 6 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну перчатку на правую руку так, чтобы эти перчатки были различных размеров?
Левые перчатки – 6 способов
Правые перчатки – 5 способов (6 перчатка того же размера, что и левая)6 • 5 = 30
Ответ: 30 способов.
25 . Из цифр 1, 2, 3, 4, 5 составляют пятизначные числа, в которых все цифры разные. Сколько таких чётных чисел?
5 цифра – 2 способа (две чётные цифры)
4 цифра – 4 способа
3 цифра – 3 способа
2 цифра – 2 способа
1 цифра – 1 способ2 • 4 • 3 • 2 • 1 = 48
Ответ: 48 чётных чисел.
26. Сколько существует четырёхзначных чисел, составленных из нечётных цифр и делящихся на 5?
Нечётные цифр – 1, 3, 5, 7, 9.
Из них делятся на 5 – 5.
4 цифра – 1 способ (цифра 5)
3 цифра – 4 способа
2 цифра – 3 способа
1 цифра – 2 способа1 • 4 • 3 • 2 = 24
Ответ: 24 числа.
27. Сколько существует пятизначных чисел, у которых третья цифра – 7, последняя цифра – чётная?
1 цифра – 9 способов (все, кроме 0)
2 цифра – 10 способов
3 цифра – 1 способ (цифра 7)
4 цифра – 10 способов
5 цифра – 5 способов (0, 2, 4, 6, 8)9 • 10 • 1 • 10 • 5 = 4500
Ответ: 4500 чисел.
28. Сколько существует шестизначных чисел, у которых вторая цифра – 2, четвёртая – 4, шестая – 6, а все остальные – нечётные?
1 цифра – 5 вариантов (из 1, 3, 5, 7, 9)
2 цифра – 1 вариант (цифра 2)
3 цифра – 5 вариантов
4 цифра – 1 вариант (цифра 4)
5 цифра – 5 вариантов
6 цифра – 1 вариант (цифра 6)5 • 1 • 5 • 1 • 5 • 1 = 125
Ответ: 125 чисел.
29.Сколько различных чисел, меньших миллиона, можно записать с помощью цифр 8 и 9?
Однозначных – 2
Двузначных – 2 • 2 = 4
Трёхзначных – 2 • 2 • 2 = 8
Четырёхзначных – 2 • 2 • 2 • 2 =16
Пятизначных – 2 • 2 • 2 • 2 • 2 = 32
Шестизначных – 2 • 2 • 2 • 2 2 • 2 = 64
Всего: 2 + 4 + 8 + 16 + 32 + 64 = 126
Ответ: 126 чисел.
30. В футбольной команде 11 человек. Нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?
Капитан – 11 способов
Заместитель – 10 способов11 • 10 = 110
Ответ: 110 способов.
31.В классе учатся 30 человек. Сколькими способами из них можно выбрать старосту и ответственного за проездные билеты?
Староста – 30 способов
Ответ. за билеты – 29 способов30 • 29 = 870
Ответ: 870 способов.
32. В походе участвуют 12 мальчиков, 10 девочек и 2 учителя. Сколько вариантов групп дежурных из трёх человек (1 мальчик, 1 девочка, 1 учитель) можно составить?
12 • 10 • 2 = 240
Ответ: 240 способов.
33. Сколько комбинаций из четырёх букв русского алфавита (в алфавите всего 33 буквы) можно составить при условии, что 2 соседние буквы будут разными?
1 буква – 33 способа
2 буква – 32 способа
3 буква – 32 способа
4 буква – 32 способа33 • 32 • 32 • 32 = 1.081.344
Ответ: 1.081.344 комбинаций.
Сколько четырехзначных чисел можно записать с помощью цифр 4; 5; 6; 7?
Конечно это задача больше из разряда логики и наверно нежно просто понять, сколько количество раз мы можем в четырехзначном числе использовать одну и туже цифру.
Если берем такие цифры, как 4;5;6 и 7, то в десятитысячном числе каждое первая цифра может встречаться только шесть раз, собственно вторая, третья и четвертая цифры тоже будут встречаться только по шесть раз
Например с первой цифрой «4» , числа будут такие:
4567;4576;4657;4675; 4756;4765 = шесть четырёхзначных чисел.
Иными словами с каждой цифрой, стоящей первой в четырехзначном числе мы получаем по шесть чисел.
Ответ: из четырех цифр, можно составить 24 четырехзначных числа, при условии, что каждая из этих цифр используется только один раз.
Нахождение цифр четырёхзначного числа
исходник мой неверен в чем моя ошибка? Напишите программу для нахождения цифр четырёхзначного числа. Формат входных данных На вход программе подаётся положительное четырёхзначное целое число. Формат выходных данных Программа должна вывести текст в соответствии с условием задачи. Sample Input 1: 3281 Sample Output 1: Цифра в позиции тысяч равна 3 Цифра в позиции сотен равна 2 Цифра в позиции десятков равна 8 Цифра в позиции единиц равна 1
a = int(input()) n1 = a //100000 n2 = a //1000 n3 = a //100 n4 = a % 3280 print('Цифра в позиции тысяч равна', n3) print('Цифра в позиции сотен равна', n2) print('Цифра в позиции десятков равна', n3) print('Цифра в позиции единиц равна', n4) Отслеживать
25.2k 4 4 золотых знака 20 20 серебряных знаков 36 36 бронзовых знаков
Элементы комбинаторики
№ 1. Имеем 4 разных конверта без марок и 3 разные марки. Сколькими способами можно выбрать конверт и марку для отправления письма?
34 = 12 (способов)
Ответ: 12 способов.
№ 2. В коробке находится 10 белых и 6 черных шаров.
1) Сколькими способами из коробки можно вынуть один шар любого цвета?
2) Сколькими способами из коробки можно вынуть два разноцветных шара?
№ 3. В корзине лежат 12 яблок и 9 апельсинов (все разные). Петя выбирает или яблоко, или апельсин, после него из оставшихся фруктов Надя выбирает яблоко и апельсин. Сколько возможно таких выборов? При каком выборе Пети у Нади больше возможностей выбора?
Если Петя берёт 1 яблоко, то у Нади больше возможностей для выбора.
Ответ: 401. Петя берёт 1 яблоко.
№ 4. Ученику необходимо сдать 4 экзамена на протяжении 8 дней. Сколькими способами может быть составлено расписание его экзаменов?
№ 5. Сколькими способами может расположиться семья из трех человек в четырехместном купе, если других пассажиров в купе нет?
№ 6. Из 30 участников собрания необходимо выбрать председателя и секретаря. Сколькими способами это можно сделать?
№ 7. Сколькими способами могут занять первое, второе и третье места 8 участниц финального забега на дистанции 100 м?
№ 8. Сколькими способами можно изготовить трехцветный флаг с горизонтальными полосами, если есть материал 7 разных цветов?
= = = = 5 = 210 (способов).
№ 9. Сколькими способами организаторы конкурса могут определить, кто из 15 его участников будет выступать первым, вторым и третьим?
= = =13 = 2780 (способов).
№ 10. На плоскости отметили 5 точек. Их необходимо обозначить латинскими буквами. Сколькими способами это можно сделать, если в латинском алфавите 26 букв?
№ 11. Сколько четырехзначных чисел можно составить из цифр 1, 3, 5, 7, 9,если цифры в числе не повторяются?
= = = 2 = 120 (способов).
№ 12*. Сколько четырехзначных чисел можно составить из цифр 0, 2, 4, 6, 8,если цифры в числе не повторяются?
№ 13. Сколько существует семизначных телефонных номеров, в которых все цифры разные и первая цифра отлична от нуля?
№ 14. Сколько разных трехзначных чисел (без повторения цифр) можно составить из цифр 1, 2, 3, 4, 5 так, чтобы полученные числа были: 1) четными; 2) кратными 5?
№ 15*. Решите уравнение: 1) =20; 2) = 6.
х 2 -3х -4х + 12 – 6 = 0
х 2 – 7х + 6 = 0 х1 = 6, х2 = 1 (исключить).
№ 1. Сколькими способами 4 мужчины могут расположиться на четырехместной скамейке?
Решение: Р4 = 4! = 1 = 24 (способа)
№ 2. Курьер должен разнести пакеты в 7 разных учреждений. Сколько маршрутов он может выбрать?
№ 3. Сколько существует выражений, тождественно равных произведению abcde, которые получаются из него перестановкой множителей?
Решение: Р5 = 5! =1 (выражений)
№4. Ольга помнит, что телефон подруги оканчивается тремя цифрами 5, 7, 8 но забыла, в каком порядке эти цифры расположены. Укажите наибольшее число вариантов, которые ей придется перебрать, чтобы дозвониться подруге.
Решение:Р3 = 3! = 1(вариантов)
№ 5. Сколько шестизначных чисел (без повторения цифр) можно составить из цифр:
1) 1, 2, 5, 6, 7, 8; 2) 0, 2, 5, 6, 7, 8?
Ответ: 1) 720; 2) 600.
№ 6. Сколько среди четырехзначных чисел, составленных из цифр 3, 5, 7, 9 (без повторения цифр), есть такие, которые: 1) начинаются с цифры 3; 2) кратны 5?
№ 7. Найдите сумму цифр всех четырехзначных чисел, которые можно составить из цифр 1, 3, 5, 7 (без повторения цифр в числе).
№ 8. В расписании на понедельник шесть уроков: алгебра, геометрия, иностранный язык, история, физкультура, химия. Сколькими способами можно составить расписание уроков на этот день так, чтобы два урока математики стояли подряд?
№ 9*. Сколькими способами можно расставить на полке 12 книг, из которых 5 книг — это сборники стихотворений, чтобы сборники стихотворений стояли рядом в случайном порядке?
№ 10. Найдите, сколькими способами 5 мальчиков и 5 девочек могут занять в театре в одном ряду места с 1 по 10. Сколькими способами они могут это сделать, если мальчики будут сидеть на нечетных местах, а девочки — на четных?
Р10 = 10! =1 — расположения 5 мальчиков и 5 девочек в любом месте и в любом ряду.
Если мальчики будут сидеть на нечетных местах, а девочки — на четных, то таких способов будет равно: Р55 = 5!5! = 1
Ответ: 3628800; 14400.
№ 1. В классе 7-м учащихся успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?
№ 2. В магазине “Филателия” продается 8 разных наборов марок, посвященных спортивной тематике. Сколькими способами можно выбрать из них 3 набора?
Решение: = = = = 56 (способов).
№ 3. Ученикам дали список из 10 книг, которые рекомендуется прочитать во время каникул. Сколькими способами ученик может выбрать из них 6 книг?
№ 4. На полке стоит 12 книг: англо-русский словарь и 11 художественных произведений на английском языке. Сколькими способами читатель может выбрать 3 книги, если: 1) словарь ему нужен обязательно; 2) словарь ему не нужен?
Решение: из 3 книг, которые надо выбрать – нужны 1 словарь и 2 художественные = Р1 = 1! = 1 (способ) 2 художественные из 11 художественных можно выбрать = = = = 55 (способов).
Тогда 1 словарь и 2 художественные книги можно выбрать
Если не нужен словарь, то
№ 5. В классе учатся 16 мальчиков и 12 девочек. Для уборки территории необходимо выделить четырех мальчиков и трех девочек. Сколькими способами это можно сделать?
Решите упражнения 6–26, используя известные вам формулы и правила комбинаторики.
№ 6. Во время встречи 16 человек пожали друг другу руки. Сколько всего сделано рукопожатий?
№ 7. Группа учащихся из 30 человек решила обменяться фотографиями.
Сколько всего фотографий необходимо было для этого?
№ 8. Сколько перестановок можно сделать из букв слова “Харьков”?
Решение: Р7 – Р6 = 7! – 6! = 6!(7-1) = 6! = 1
№ 9. Бригадир должен откомандировать на работу бригаду из 5 человек.
Сколько бригад по 5 человек в каждой можно организовать из 12 человек?
№ 10. Сколькими разными способами собрание из 40 человек может выбрать из числа своих членов председателя собрания, его заместителя и секретаря?
№ 11. Сколько прямых линий можно провести через 8 точек, из которых никакие три не лежат на одной прямой?
Решение: = = = = 28 (прямых линий)
№ 12. Сколько разных пятизначных чисел можно записать с помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 без их повторения?
Решение: = = = 2(разных пятизначных числа)
№ 13. Определите число всех диагоналей правильного: 1) пятиугольника; 2) восьмиугольника; 3) двенадцатиугольника; 4) пятнадцатиугольника.
Решение: общая формула вычисления диагоналей у n- угольника
- n=5, то = 10 (диагоналей)
- n=12, то = 66 (диагоналей)
- n=8, то = 28 (диагоналей)
- n=15, то = 105(диагоналей)
Ответ: 10; 66; 28; 105.
№ 14. Сколько разных трехцветных флагов можно сшить, комбинируя синий, красный и белый цвета?
Решение: Р3 = 3! = 1 = 6 (флагов).
№ 15. Сколько разных плоскостей можно провести через 10 точек, если ни какие три из них не лежат на одной прямой и никакие четыре точки не лежат в одной плоскости?
Решение: = = = 360 (разных плоскостей)
№ 16*. Сколько разных пятизначных чисел можно записать с помощью цифр 0, 2, 4, 6, 8 без их повторения?
Решение: Р5 – Р4 = 5! – 4! = 4! (5-1) = 4! 4 = 1 3 = 96 (разных пятизначных чисел)
№ 17. Среди перестановок из цифр 1, 2, 3, 4, 5 сколько таких, которые не начинаются цифрой 5? числом 12? числом 123?
Решение: 4! = 1 3 — перестановок начинаются цифрой 5.
3! = 1 3 6 — перестановок начинаются цифрой 12.
2! = 1 перестановок начинаются с цифрами 123.
№ 18. Среди сочетаний из 10 букв a, b, c, . по 4 сколько таких, которые не содержат буквы а? букв a и b?
= = 63 (сочетаний не содержат букву a)
= = 140 (сочетаний не содержат букву a и b)
№ 19. Среди размещений из 12 букв a, b, c, . по 5 сколько таких, которые не содержат буквы а? букв a и b?
Решение: — = — = – = =7 = 83160 (размещений)
– = – = – = =720(132 – 1) = 94320 (размещений)
Ответ: 83160; 94320.
№ 20. Сколько необходимо взять элементов, чтобы число размещений из них по 4 было в 12 раз больше, чем число размещений из них по 2?
Решение: = 12 ОДЗ: х N;
х 2 -2х -3х +6 = 12
х 2 -5х — 6 = 0 =6, =-1