Воскресенье, 19:45 
Заказ документов

 

 

Произвести заказ документа или задать вопрос можно здесь, оформление 10 минут после ответа оператора!
Главная » »
Главная » Файлы » Дистанционные курсы для педагогов и учащихся » Элементы комбинаторики, статистики и теории вероятностей

Некоторые приемы, используемые при решении комбинаторных задач.
07.02.2013, 16:31
Лекция: Правило умножения
В повседневной жизни часто приходится выбирать различные варианты принятия решения. Чтобы не упустить ни один из них, надо осуществить перебор всех возможных комбинаций или подсчитать их число. Такие задачи получили название комбинаторных задач, а раздел математики, в котором они рассматриваются, назвали комбинаторикой.
Начнем знакомство с новыми понятиями с простой задачи, но решим ее тремя различными способами.
Задача. На завтрак в школьной столовой любой ученик может выбрать булочку, ватрушку, кекс или пирожок, а запить их он может соком, чаем или компотом. Сколько вариантов завтрака предлагается в школьной столовой?

Решение.
Собираем все варианты в таблицу
булочка ватрушка кекс пирожок
сок Сок, булочка Сок, ватрушка Сок, кекс Сок, пирожок
чай Чай булочка Чай, ватрушка Чай, кекс Чай, пирожок
компот Компот, булочка Компот, ватрушка Компот, кекс Компот, пирожок
В таблице 3 строки и 4 столбца, которые образуют 12 клеток. Так как выбор еды и напитка происходит независимо, то в каждой клетке будет стоять один из возможных вариантов завтрака. С другой стороны, любой вариант завтрака записан в одной из клеток. Значит, всего вариантов столько, сколько клеток в таблице, то есть 12.
Ответ: столовая предлагает 12 вариантов завтрака.

Задача. Сколько двузначных чисел можно составить из цифр 1, 3 и 5?
Решение. Способ I (простой перебор). Будем выписывать числа в порядке возрастания, а чтобы не пропустить и не повторить ни одно из чисел, составим таблицу:

11 13 15
31 33 35
51 53 55

Первая цифра числа — номер строки, вторая цифра — номер столбца. Искомых чисел будет столько, сколько клеток в таблице, то есть 3 · 3 = 9.
Ответ: 9.
Способ II (использование дерева возможных вариантов).

Всего 3 · 3 = 9 различных двузначных чисел.
Ответ: 9.
Комментарий. Этот способ нагляден, как всякая картинка, и позволяет все учесть, ничего не пропустив.
Способ III. Ответ на вопрос, поставленный в задаче, можно получить, не выписывая сами числа. Будем рассуждать так.
Первую цифру можно выбрать тремя способами. Вторую цифру также можно выбрать тремя способами. Всего 3 · 3 = 9 различных двузначных чисел.
Ответ: 9.
Комментарий. Этот способ позволяет в один шаг решать самые разнообразные задачи.
Третий способ решения данной задачи называется комбинаторным правилом умножения.
Если элемент x можно выбрать m способами, а элемент y можно выбрать n способами, то упорядоченную пару элементов (x; y) можно выбрать m · n способами.
Когда выбираются более двух элементов, тогда их упорядоченный набор можно выбрать, перемножая количества способов выбора каждого элемента.
У каждого из этих способов есть свои преимущества и свои недостатки.
Теперь мы попробуем следующие задачи решать по этому правилу.
Задача : Антон, Борис и Василий купили 3 билета на футбольный матч на 1, 2, и 3-е места первого ряда. Сколькими способами они могут занять имеющиеся три места?
Решение. 1 место 2 место 3 место
Каждое место может занять каждый из троих: 3 * 3 = 9. Но нужно вычесть тройки ААА, БББ, ВВВ. Всего получится 6 способов.
Задача : Сколько двузначных чисел можно составить из цифр 1, 2, 4, 6, 8?
Решение. У интересующих нас двузначных чисел на первом месте может находиться любая из заданных цифр, кроме 0. Если на первое место мы поставим цифру 2, то на втором месте может находиться любая из заданных цифр. Получится пять двузначных чисел: 2.,22, 24, 26, 28. Точно так же будет пять двузначных чисел с первой цифрой 4, пять двузначных чисел с первой цифрой 6 и пять двузначных чисел с первой цифрой 8.
Ответ: всего получится 20 чисел.
Построим дерево возможных вариантов для решения этой задачи.
20, 22, 24, 26, 28, 60, 62, 64, 66, 68,
40, 42, 44, 46, 48, 80, 82, 84, 86, 88.

Задача :Несколько стран решили использовать для своего государственного флага символику в виде трех горизонтальных полос одинаковой ширины разных цветов – белого, синего, красного. Сколько стран могут использовать такую символику при условии, что у каждой страны – свой флаг?
Решение. Предположим, что первая полоса – белая. Тогда вторая полоса может быть синей или красной, а третья полоса соответственно, красной или синей. Получилось два варианта: белая, синяя, красная или белая, красная, синяя.
Пусть теперь первая полоса синего цвета, тогда опять получим два варианта: белая, красная, синяя или синяя, красная, белая.
Пусть первая полоса красного цвета, тогда еще два варианта: красная, белая, синяя или красная, синяя, белая.
Всего получилось 6 возможных вариантов. Такой флаг могут использовать 6 стран.
Флаг России
Итак, при решении этой задачи мы искали способ перебора возможных вариантов. Во многих случаях оказывается полезным прием построения картинки – схемы перебора вариантов. Это, во – первых, наглядно , во- вторых, позволяет нам все учесть, ничего не пропустить.
Эту схему еще называют деревом возможных вариантов.
Категория: Элементы комбинаторики, статистики и теории вероятностей | Добавил: тан71
Просмотров: 1882 | Загрузок: 5 | Рейтинг: 5.0/1
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Copyright 2010 © БОЛЬШАЯ ПЕРЕМЕНА