Урок 41. Примеры комбинаторных задач
Комбинаторные задачи – это задачи, в которых необходимо составить комбинации каких-либо элементов из заданного набора по определённым условиям и (или) подсчитать количество получившихся комбинаций.
Комбинаторика – раздел математики, который занимается решением комбинаторных задач.
При решении комбинаторных задач можно воспользоваться:
• методом перебора;
• деревом возможных вариантов;
• комбинаторным правилом умножения.
Рассмотрим эти способы на примерах.
Задача 1
В магазине детских игрушек Маше понравились четыре мягких игрушки: мишка, енот, лиса и белка. Мама разрешила взять только две из них. Сколько существует вариантов выбора игрушек у Маши?
Решение
Переберём все возможные варианты выбора двух игрушек.
Сначала составим все варианты, в которых одной из игрушек будет мишка. Получим три варианта:
мишка и енот
мишка и лиса
мишка и белка
Теперь составим все варианты, в которых не будет мишки, но будет енот. Получим ещё два варианта:
енот и лиса
енот и белка
Наконец составим все варианты, в которых не будет ни мишки, ни енота, но будет лиса. Такой вариант остался только один:
лиса и белка
Других вариантов выбора игрушек не осталось. Значит, у Маши всего 6 вариантов выбора игрушек.
Мы решили задачу методом перебора.
Задача 2
Петя, Коля и Вася решили съесть мороженое. У мальчиков было одно клубничное, одно шоколадное, одно малиновое и одно вишнёвое мороженое. Сколько вариантов выбора мороженого было у мальчиков?
Решение
Решим эту задачу с помощью дерева возможных вариантов. Обозначим клубничное мороженое буковой «к», шоколадное – «ш», малиновое – «м», вишнёвое – «в».
Поскольку мы учтём все возможные варианты, то нам всё равно, в каком порядке мальчики будут выбирать мороженое. Сначала проиллюстрируем все возможные варианты выбора Пети:
Теперь для каждого из вариантов выбора Пети проиллюстрируем все возможные варианты выбора Коли:
И наконец, для каждого из вариантов выбора Пети и Коли проиллюстрируем все возможные варианты выбора Васи:
Мы перебрали все возможные варианты. Полученная схема и называется деревом возможных вариантов. Осталось определить количество этих вариантов. Для этого нужно посчитать количество вариантов в последней строке. Получилось 24 варианта.
Мы решили задачу с помощью дерева возможных вариантов.
Эту же задачу можно решить, не изображая схему.
Задача 2
Петя, Коля и Вася решили съесть мороженое. У мальчиков было одно клубничное, одно шоколадное, одно малиновое и одно вишнёвое мороженое. Сколько вариантов выбора мороженого было у мальчиков?
Решение
Будем рассуждать следующим образом. Поскольку мы учтём все возможные варианты, то нам всё равно, в каком порядке мальчики будут выбирать мороженое.
Пусть Петя выбирает мороженое первым. У него есть 4 варианта выбора.
Если Коля выбирает вторым, то у него останется 3 варианта для каждого выбора Пети. То есть всего вариантов выбора Пети и Коли будет 4 • 3.
У Васи останется по 2 варианта для каждого из выборов Пети и Коли. Значит, всего вариантов будет 4 • 3 • 2 = 24.
Мы решили задачу с помощью комбинаторного правила умножения. Сформулируем его для общего случая.
Пусть из некоторого набора элементов нужно выбрать последовательно k элементов. И пусть первый элемент можно выбрать n1 способами, затем второй – n2 способами из оставшихся, и т. д. Тогда количество способов, которыми могут быть выбраны все k элементов, равно n1 • n2 • … • nk.
Задача 3
Марина, Вера и Лена решили купить по воздушному шару. У продавца было 7 шаров разных цветов: зелёный, красный, розовый, жёлтый, оранжевый, фиолетовый и синий. Сколько вариантов выбора шаров есть у девочек, учитывая, что Марина не любит зелёный цвет и не купила бы себе такой воздушный шар?
Решение
Для решения задачи воспользуемся комбинаторным правилом умножения.
Поскольку у Марины есть предпочтения по цвету шара, начнём выбор с неё. У Марины всего 6 вариантов выбора шара. Вера может выбрать любой из оставшихся шаров, т. е. у неё тоже 6 вариантов выбора шара. Тогда у Лены остаётся 5 вариантов выбора.
Используя комбинаторное правило умножения получаем, что всего вариантов выбора шаров у девочек было 6 • 6 • 5 = 180.
Источник
Комбинаторные задачи
Комбинаторика (от латинского слова combinare, означающего №соединять», «сочетать») — это область математики, которая изучает способы выбора, расположения, сочетания различных объектов. Решение задач в данном разделе математики требует рассмотрения и подсчёта всех возможных комбинаций (отсюда название комбинаторные задачи). Решая эти задачи, обычно надо отвечать на вопрос «Сколькими способами. » или «Сколько вариантов. «
Задача: Нам даны фигуры: треугольник, овал и прямоугольник . Необходимо построить пирамидку, состоящую из трех разных фигур. Сколькими способами это можно сделать?
Метод перебора
Данный метод удобен при небольшом числе вариантов. Решение в данном случае происходит путём перебора всех возможных вариантов. При этом очень важно выбрать правильный вариант перебора — логику перебора.
Воспользуемся методом перебора: Пусть в основании пирамидки находится прямоугольник, тогда возможны варианты построения: прямоугольник — овал — треугольник и прямоугольник — треугольник — овал.
Теперь в основании положим овал, тогда возможны варианты построения: овал — прямоугольник — треугольник и овал — треугольник — прямоугольник.
Теперь в основании положим треугольник, тогда возможны варианты построения: треугольник — прямоугольник — овал и треугольник — овал — прямоугольник.
Итак, мы получили шесть возможных вариантов:
Ответ: 6 способов.
При решении данной задачи мы изображали фигуры, но для упрощения решения можно использовать кодирование. Данный прием позволяет заметить фигуры, например, первыми буквами их названия, то есть овал обозначаем буквой О, треугольник — Т, прямоугольник — П. Тогда решение будет выглядеть так:
Дерево возможных вариантов
Данный метод заключается в построении схемы, которая и называется деревом возможных вариантов. Данная схема действительно похожа на перевернутое дерево, «корень» которого обозначается «*». Построим данную схему для нашей задачи: Для этого от «корня» проведем три «ветки» — отрезки, на концах которых подпишем варианты фигур, которые мы можем взять за основание. Далее от каждой фигуры проводим такое количество «веток», которое будет соответствовать числу вариантов фигур на втором месте, в нашем случае по две «ветки» от каждой фигуры. Затем от каждой фигуры, стоящей на втором месте, проводим такое число «веток», которое будет соответствовать числу вариантов фигур на третьем месте, в нашем случае по одной «ветке» от каждой фигуры. Тогда имеем следующее дерево возможных вариантов:
Метод отрезков
Данный метод используется только для составления всевозможных пар. Например, рассмотрим прямую, на которой обозначены точки A, B, C, D, F:
Необходимо ответить на вопрос: » Сколько отрезков изображено на рисунке?». Мы знаем, что отрезок обозначается двумя буквами, значит, для ответа на вопрос необходимо перебрать всевозможные пары букв. Это можно сделать при помощи следующей схемы: Отметим точки так, чтобы никакие 3 не лежали на одной прямой:
Соединим данные точки отрезками между собой. Число отрезков будет числом вариантов, то есть числом отрезков, изображенных на рисунке:
Итак, мы получили 10 отрезков, соединяющих точки.
Ответ: На рисунке 10 отрезков.
Источник
Решение комбинаторных задач
Презентация по теме «Решение комбинаторных задач» для самостоятельного изучения темы.
Просмотр содержимого документа
«Решение комбинаторных задач»
Решение комбинаторных задач
Комбинаторные задачи – это задачи, в которых требуется из элементов составить различные наборы, подсчитать количество всевозможных комбинаций элементов, составленных по определённому правилу.
Методы решения комбинаторных задач
1. Метод перебора вариантов
2. Дерево возможных вариантов
Метод перебора вариантов
Полный перебор вариантов без составления таблиц и схем
Какие двузначные числа можно составить из цифр 1, 2, 3, 4, 5?
Перебираем всевозможные варианты: 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.
В финальном забеге на 100 м участвуют Смирнов, Петров и Орлов. Назовите возможные варианты распределения призовых мест.
Задача 1: Вариант1: 1) Смирнов, 2) Петров, 3) Орлов. Вариант2: 1) Смирнов, 2) Орлов, 3) Петров. Вариант3: 1) Орлов, 2) Смирнов, 3) Петров. Вариант4: 1) Орлов, 2) Петров, 3) Смирнов. Вариант5: 1) Петров, 2) Орлов, 3) Смирнов. Вариант6: 1) Петров, 2) Смирнов, 3) Орлов .
Дерево возможных вариантов
способ решения разнообразных задач, касающихся перебора вариантов происходящих событий.
Какие трехзначные числа можно составить из цифр 0, 3, 8?
Построим дерево возможных вариантов, учитывая, что 0 не может быть первой цифрой в числе.
Сколько существует флагов составленных из трех горизонтальных полос одинаковой ширины и различных цветов: белого, синего, красного и зеленого? Есть ли среди них Государственный флаг Российской Федерации?
Задача 2: всего существует 24 флага, среди них есть Государственный флаг Российской Федерации.
Запишите все возможные варианты расписания пяти уроков на день из предметов: математика, русский язык, история, английский язык, физкультура, причем математика должна быть вторым уроком.
Задача 3: обозначив М — математика, Р — русский язык, И — история, А — английский язык, Ф — физкультура и построив дерево возможных вариантов, получим всего 24 варианта .
Решить комбинаторные задачи можно с помощью таблиц. Они, как и дерево возможных вариантов, наглядно представляют решение таких задач.
Задача 1. Сколько нечетных двузначных чисел можно составить из цифр 1, 3, 4, 6, 7, 8, 9?
Решение. Составим таблицу: слева первый столбец — первые цифры искомых чисел, вверху первая строка — вторые цифры.
Первая цифра может быть любая, а вторая только нечетная (1, 3, 7, 9)
Источник