![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Комбинаторные задачи с решением
Комбинаторика - раздел математики, занимающийся вопросом выбора и расположения элементов некоторого конечного множества в соответствии с заданными условиями. Рассмотрим примеры задач комбинаторики. Пример №1 Сколькими способами можно выбрать путь из начала координат 0(0,0) в точку В(6,4), если каждый шаг равен единице, но его можно совершать только вправо или вверх? Сколько таких путей проходит через точку А(2,3)? Решение. Весь путь занимает 10 шагов (четыре вверх и шесть вправо). Для планирования пути следует решить, какие именно по счету четыре шага следует сделать вверх, а остальные шесть — вправо. Выбор бесповторный и нас интересует только состав выбора. Поэтому в описанных условиях всего путей из точки О в точку В будет Рассуждая подобным образом легко видеть, что путей из точки О в точку А существует Ответ. 210; 50. Пример №2 Сколькими способами можно выбрать путь из начала координат 0(0,0) в точку Исходные данные к задаче 1.1. Пример №3 В городе с идеальной прямоугольной планировкой (сеть улиц в этом городе изображена на рис. 1.1) из пункта А выходят Решение. Каждый человек пройдет N улиц и окажется на одном из перекрестков На каждом перекрестке для каждого человека производится выбор из двух возможностей: идти в направлении В пункте
Ответ. Пример №4 Сколькими способами можно Решение. Поставим эти предметы в ряд. Между ними будет Ответ. Пример 1.4. Сколькими способами можно распределить 6 яблок, 8 груш и 10 слив между тремя детьми? Сколькими способами это можно сделать так, чтобы каждый ребенок получил по меньшей мере одно яблоко, одну сливу и одну грушу? Решение. Яблоки в соответствии с формулой (1.5) можно распределить Ответ. 83160; 7560. Пример №5 Сколько цифр в первой тысяче не содержат в своей записи цифры 5? Решение. Для записи любой из цифр 000, 001, 002,..., 999 необходимо трижды выбрать повторным способом одну из десяти цифр, поэтому и получается всего Ответ. 729. Пример №6 Сколько шестизначных чисел содержат в записи ровно три различных цифры? Решение. Заметим, что всего шестизначных чисел имеется Выбрать три ненулевых цифры можно
Учтем теперь возможность использования нуля. К нулю нужно добавить две цифры, что можно сделать Ответ. 58320. Пример №7 В саду есть цветы десяти наименований (розы, флоксы, ромашки и т. д.). а) Сколькими способами можно составить букет из пяти цветков (не принимая во внимание совместимость растений и художественные соображения)? б) Сколькими способами можно составить букет из пяти различных цветков? в) Сколькими способами можно составить букет из пяти цветков так, чтобы в букете непременно было хотя бы по одному цветку двух определенных наименований Решение. а) Если запрета на повторение цветков нет, то мы имеем дело с повторным выбором и нас интересует только состав. Поэтому по формуле (1.5) получаем б) Если цветы должны быть разными, то способ выбора бесповторный и букет можно составить в) Отберем по одному цветку каждого из двух названных наименований. Три остальных цветка можно выбрать из 10 возможных Ответ. а) 2002; б) 504; в) 220. Пример №8 Имеется Решение. Ясно, что яблоки можно разложить При ответе на второй вопрос учтем, что следует по одному яблоку сразу положить в каждую из корзин, а остальные Ответ. Пример №9 Требуется найти число натуральных делителей натурального числа Решение. Разложим где Заметим, что при разделении числа Так что разложение Ответ. Пример №10 Сколькими способами легкоатлет, собираясь на тренировку, может выбрать себе пару спортивной обуви, имея 5 пар кроссовок и 2 нары кед? Очевидно, что выбрать одну из имеющихся пар обуви, кроссовки или кеды, можно 5 + 2 = 7 способами.
Обобщая, приходим к комбинаторному правилу сложения:
Это правило справедливо также для трех и более элементов. Пример №11 В меню школьной столовой предлагается на выбор 4 вида пирожков и 3 вида сока. Сколько разных вариантов выбора завтрака, состоящего из одного пирожка и одного стакана сока, имеется у учащегося этой школы? Пирожок можно выбрать 4 способами и к каждому пирожку выбрать сок 3 способами (рис. 76). Следовательно, учащийся имеет Обобщая, приходим к комбинаторному правилу умножения:
Это правило справедливо также для трех и более элементов. Пример №12 Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, если в числе: 1) цифры не повторяются; 2) цифры могут повторяться? Решение: 1) Первую цифру можем выбрать 4 способами (рис.77). Так как после выбора первой цифры их останется три (ведь цифры в нашем случае повторяться не могут), то вторую цифру можем выбрать 3 способами.И наконец, третью цифру можем выбрать из оставшихся двух - то есть 2 способами. Следовательно, количество искомых трехзначных у чисел будет равно 2) Применим комбинаторное правило умножения. Так как цифры в числе могут повторяться, то каждую из цифр искомого числа можно выбрать 4 способами (рис. 78), и тогда таких чисел будет Ответ. 1) 24 числа; 2) 64 числа. Отметим, что решить подобные задачи без применения комбинаторного правила умножения можно только путем перебора всех возможных вариантов чисел, удовлетворяющих условию задачи. Но такой способ решения является слишком долгим и громоздким. Пример №13 Сколько четных пятизначных чисел можно составить из цифр 5, 6, 7, 8, 9, если цифры в числе не повторяются? Решение: Четное пятизначное число можно получить, если последней его цифрой будет 6 или 8. Чисел, у которых последней является цифра 6, будет а тех, у которых последней является цифра 8, - также 24. По комбинаторному правилу сложения всего четных чисел будет Ответ. 48. Пример №14 Азбука племени АБАБ содержит всего две буквы - «а» и «б». Сколько слов в языке этого племени состоит: 1) из двух букв; 2) из трех букв?
Решение: 1) аа, ба, аб, бб (всего четыре слова); 2) ааа, ааб, аба, абб, ббб, бба, баб, баа (всего восемь слов). Заметим, что найденное количество слов соответствует комбинаторному правилу умножения. Так как на каждое место есть два «претендента» - «а» и «б», то слов, состоящих из двух букв, будет Пример №15 В футбольной команде из 11 игроков надо выбрать капитана и его заместителя. Сколькими способами это можно сделать? Решение: Капитаном можно выбрать любого из 11 игроков, а его заместителем - любого из 10 оставшихся игроков. Таким образом (по правилу умножения), имеем Пример №16 В Стране Чудес 10 городов и каждые два из них соединяет авиалиния. Сколько авиалиний в этой стране? Решение. Так как каждая авиалиния соединяет два города, то одним из них может быть любой из 10 городов, а другим - любой из 9 оставшихся. Следовательно, количество авиалиний равно Комбинаторные задачи неразрывно связаны с задачами теории вероятностей, еще одного раздела математики. В ХIII-ХII в. до н. э. встречаются упоминания о вопросах, близких к комбинаторным. Некоторые комбинаторные задачи решали и в Древней Греции. В частности, Аристоксен из Тарента (IV в. до н. э.), ученик Аристотеля, перечислил различные комбинации длинных и коротких слогов в стихотворных размерах. А Папп Александрийский в IV в. н. э. рассматривал число пар и троек, которые можно получить из трех элементов, допуская их повторения. Некоторые элементы комбинаторики были известны и в Индии во II в. до н. э. Индийцы умели вычислять числа, известные нам как коэффициенты формулы бинома Ньютона. Позднее, в VIII в. н. э., арабы нашли и саму эту формулу, и ее коэффициенты, которые сейчас вычисляют с помощью комбинаторных формул или «треугольника Паскаля». Свой нынешний вид упомянутые комбинаторные формулы приобрели благодаря средневековому ученому Леви бен Гершону (XIV в.) и французскому математику П. Эригону (XVII в.). В III в. н. э. сирийский философ Порфирий для классификации понятий составил специальную схему, получившую название «древо Порфирия». Сейчас подобные деревья используются для решения определенных задач комбинаторики в разнообразных областях знаний. Некоторые ранее неизвестные комбинаторные задачи рассмотрел Леонардо Пизанский (Фибоначчи) в своей знаменитой «Книге абака» (1202 г.), в частности, о нахождении наименьшего набора различных гирь, позволяющего взвесить груз с любой целочисленной массой, не превышающей заданного числа. Со времен греческих математиков были известны две последовательности, каждый член которых получали по определенному правилу из предыдущих, - арифметическая и геометрическая прогрессии. А Фибоначчи впервые в одной из задач выразил член последовательности через два предыдущих, используя формулу, которую назвали рекуррентной. В дальнейшем метод рекуррентных формул стал одним из мощнейших для решения комбинаторных задач.
Как ни странно, развитию комбинаторики в значительной степени способствовали азартные игры, которые были очень популярны в XVI в. В частности, вопросами определения разнообразных комбинаций в игре в кости в то время занимались такие известные итальянские математики, как Д. Кардано, H. Тарталья и др. А наиболее полно изучил этот вопрос в XVII в. Галилео Галилей. Современные комбинаторные задачи высокого уровня сложности связаны с объектами в других отраслях математики: определителями, конечными геометриями, группами, математической логикой и т. п.
|
|||||||||
Последнее изменение этой страницы: 2022-01-22; просмотров: 1393; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.118.28.200 (0.04 с.) |