в взводе 101 солдат разного роста сколькими способами можно выстроить этот взвод так

Решение: Задача 2

Главная > Решение

4) Сочетания (без повторений).

Определение. Сочетаниями называются соединения, содержащие по n элементов из числа m данных элементов и различающихся друг от друга по крайней мере одним элементом.

Сочетания являются частным случаем размещений. Сочетания – это размещения, которые различаются друг от друга по крайней мере одним элементом. Перестановка элементов в одном из сочетаний то же самое сочетание.

Число сочетаний из m элементов по n обозначается символом .

Для того чтобы найти способ вычисления числа сочетаний из m элементов по n элементов, запишем все размещения из четырех элементов по 3 так, чтобы в первой строке стояли все различные сочетания, а каждый столбец представлял одно и то же сочетание:

АБВ, АБД, АВД, БВД – это различные сочетания, их количество .

Таких строк столько, сколько можно перестановок из трех элементов, т.е.

Итак, ; .

Можно предложить учащимся следующие задание: записать все размещения из трех элементов по 2 так, чтобы в первой строке стояли различные сочетания, а каждый столбец представлял одно и то же сочетание. Выполнив это, они придут к формуле:

, т.е. .

Анализируя два числовых равенства:

и ,

Учащихся можем подвести к формуле:

.

Задача 3.4.1. На тренировках занимаются 12 баскетболистов. Сколько может быть организовано тренером разных стартовых пятерок?

Решение: .

Задача 3.4.2. Сколько экзаменационных комиссий, состоящих из 7 членов можно образовать из 14 преподавателей?

Решение: .

Задача 3.4.3. В чемпионате страны по футболу (высшая лига) участвует 18 команд, причем каждые две команды встречаются между собой дважды. Сколько матчей играется в течение сезона?

Решение: В первом круге состоятся матча. Столько же матчей будет сыграно и во втором круге – всего 306 встреч.

Задача 3.4.4. В классе 30 учащихся. Сколькими способами можно выделить двух человек на дежурство, если: один из них должен быть старшим; старшего быть не должно?

Решение: ; .

Задача 3.4.5. Для полета на Марс необходимо укомплектовать следующий экипаж космического корабля: командир, его первый помощник, второй помощник, два бортинженера (обязанности которых одинаковы) и один врач. Командная тройка может быть отобрана из числа 25 готовящихся к полету летчиков, два бортинженера – из числа 20 специалистов, в совершенстве знающих устройство космического корабля, и врач – из числа 8 медиков. Сколькими способами можно укомплектовать команду космического корабля?

Весь экипаж может быть укомплектован: способами.

Задача 3.4.6. Во взводе три сержанта и 30 солдат. Сколькими способами можно выделить одного сержанта и трех солдат для патрулирования?

Решение: Чтобы закрепить навыки вычисления числа сочетаний, можно решить следующие задачи.

; ; ; ; ; .

Вычислить: ; ; ; ; ; ; .

Отсюда получаем равенство: , , , , ,

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

Перед тем как рассматривать свойства числа сочетаний, закодируем сочетания из четырех элементов (А, Б, В, Г) по три следующим образом:

1 означает, что буква взята для данного сочетания;

0 означает, что буква не взята для данного сочетания.

Так, слово 1100 соответствует сочетанию АБВ, 1101 – сочетанию АБГ, 1011 – сочетанию АВГ, 0111 – сочетанию БВГ.

Чтобы найти все сочетания из четырех элементов по три, надо найти все слова из четырех букв (цифр), в которых три раза стоит 1 и один раз 0.

Задача 3.4.7. Из четырех элементов (А, Б, В, Г) составим все сочетания по два и закодируем по тому же принципу, который изложен выше.

1100, 1010, 1001, 0110, 0101, 0011

Итак, число сочетаний из четырех элементов по два совпадают с числом слов из четырех букв (цифр), в которых два раза стоит 1 и два раза 0.

Источник

В взводе 101 солдат разного роста сколькими способами можно выстроить этот взвод так

В роте два взвода, в первом взводе солдат меньше, чем во втором, но больше чем 46, а вместе солдат меньше чем 111. Командир знает, что роту можно построить по несколько человек в ряд так, что в каждом ряду будет одинаковое число солдат, большее 8, и при этом ни в каком ряду не будет солдат из двух разных взводов.

а) Сколько солдат в первом взводе и сколько во втором? Приведите хотя бы один пример.

б) Можно ли построить роту указанным способом по 13 солдат в одном ряду?

в) Сколько в роте может быть солдат?

Пусть в первом взводе k солдат, во втором l солдат. Тогда числа k и l имеют общий делитель, больший 8, и при этом:

а) Например, 50 и 60 солдат. Вместе 110, их можно построить в колонну по 10 человек в ряду так, что 5 рядов будет заполнено солдатами только из первого взвода, а 6 рядов — только из второго.

б) Предположим, что общий делитель 13. Тогда, учитывая, что , получаем, что k = 52. Наименьшее возможное значение l равно 52 +13= 65, но вместе получается 117 человек, что противоречит условию.

в) Число l − k больше нуля и делится на общий делитель чисел k и l, поэтому что вместе с условием k + l ≤ 110 приводит к неравенству 2k ≤ 101, то есть k ≤ 50. При этом k + d ≤ l ≤ 110 − k, где d — наименьший общий делитель, превосходящий 8.

Если k = 48, то d = 12, l = 60, а в роте 108 солдат.

Если k = 49, то 98 ≤ l ≤ 110 − 49 =61. Противоречие.

Если k = 50, то d = 10, l = 60, а в роте 110 солдат.

Ответ: а) Например, 50 и 60; б) нет; в) 108 и 110.

Источник

Ищем педагогов в команду «Инфоурок»

Урок- математический турнир по теме:

« Решение комбинаторных задач»

Отработка практических умений и навыков решения комбинаторных задач.

Развитие внимания, логического мышления.

Формирование активной жизненной позиции учащихся и умения работать в группе.

Объединение учащихся в 4 группы.

Подготовка раздаточного материала:

Схемы выбора формул и выбора правил для решения комбинаторных задач,

набор цветных карточек,

Таблица с игровым полем.

Таблица с формулами соединений.

Актуализация знаний учащихся по теме « Комбинаторика»

Какие задачи называются комбинаторными? ( задачи выбора и размещения элементов конечного множества).

Что изучает комбинаторика? ( это раздел математики, который изучает методы решения комбинаторных задач).

Что такое соединения? (это конечные множества, в которых существенным является либо порядок элементов, либо их состав, либо то и другое одновременно).

Какие виды соединений мы изучаем? ( Перестановки, размещения, сочетания).

Определение размещения.( Упорядоченное подмножество из m элементов данного множества, содержащего n элементов ( m n ) называется размещением из n элементов и обозначается A = n *( n – 1 ) …( n – m + 1 )

Определение сочетания. ( Любое подмножество из m элементов данного множества, содержащего n элементов, называется сочетанием из n по m

C =

C =

Чем отличаются размещение и сочетание?

B A — важен порядок элементов

B С — порядок выбора элементов не имеет значения.

Ребята, вы объединены в 4 группы. Сегодня между группами состоится математический турнир.

Задача группы – заполнить карточками своего цвета как можно больше секций игрового поля. Карточку имеет право прикрепить та группа, которая первой решит задание. О выполнении задания группа сообщает поднятием сигнального флажка.

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

Все решения должны быть записаны в тетради каждого ученика. Объяснять решение должны выходить по очереди все члены группы.

Задания турнира с решениями и ответами:

В спортивной команде 25 человек. Сколькими способами можно выбрать олимпийскую команду в составе трех человек?

C == 2300

Сколькими способами можно рассадить четырех учеников на 25 местах?

A = 25 · 24 · 23 · 22= 303600

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

Сколькими способами можно выбрать 2 карандаша и 3 ручки из 6 разных карандашей и 8 разных ручек?

C · C = ·= 840

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

А = 5 · 4 ·3 = 60

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

C = 378

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

Число должно оканчиваться 5, значит, осталось 5 цифр:

Сколько существует двухзначных чисел, в которых цифра десятков и цифра единиц разные и нечетные?

Нечетные цифры: 1, 3, 5, 7, 9 ( всего 5)

A =5 · 4 = 20

Ученику нужно сдать 4 экзамена за 8 дней. Сколькими способами это можно сделать, если последний экзамен – в восьмой день?

A ·4 = 7 · 6 ·5·4 = 840

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

C · C · C= · · 1 = 90

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

A= 151200

Сколькими способами из 9 учебных предметов можно составить расписание учебного дня из 6 различных предметов?

A= 9 ·8 ·7 ·6 ·5 ·4 = 60480

Во взводе 5 сержантов и 30 солдат. Сколькими способами можно составить наряд из одного сержанта и трех солдат?

C · C = 5 · = 20300

Сколькими способами можно группу из 15 человек разделить на 2 группы так, чтобы в одной группе было 4 человека, а в другой- одиннадцать?

C = C = = 1365

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

A — председателя и секретаря

C — 2-х членов комиссии

A· C = = 58140

45 человек обмениваются рукопожатиями. Сколько рукопожатий было сделано?

C = = 990

На школьном вечере в танцевальном конкурсе участвуют 12 девушек и 15 юношей. Сколькими способами можно выбрать из них 4 танцевальные пары?

C· A = C· A = 16216200

Из 10 разных цветов нужно составить букет так, чтобы в нем было не меньше двух цветков. Сколькими способами можно составить такой букет?

2 – C — C = 1024 – 1 – 10 = 1013

Источник

В взводе 101 солдат разного роста сколькими способами можно выстроить этот взвод так

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

если некоторый выбор может быть сделан различными способами, а для каждого из этих способов некоторый второй выбор может быть сделан различными способами, то число способов для осуществления последовательности двух этих выборов равно произведению

Фактически при решении всех задач мы пользовались этим общим правилом, и нужно было только определить число различных возможностей в том или ином случае. Это число менялось в зависимости от условий задачи.

Другое общее правило имеет следующий вид:

если некоторый выбор может быть сделан различными способами, а другой выбор различными способами (отличными от предыдущих), то общее число способов, которыми можно осуществить какой-нибудь один из этих выборов, равен сумме

Это правило также применялось нами в предыдущем параграфе (см. пример 8).

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

Пример 1. Во взводе 5 сержантов и 50 солдат. Сколькими способами можно составить наряд из одного сержанта и трех солдат?

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

Для определения числа возможностей выбора трех солдат нам придется снова воспользоваться первым правилом, как мы это уже и делали все время, не формулируя его явно. Нам придется при этом действовать в два приема.

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

стей; после того как один солдат уже вызван, для выбора второго остается 49 возможностей, а для выбора третьего — лишь 48. Таким образом, применяя правило умножения, находим, что всего для выбора трех солдат в определенном порядке число возможностей равно произведению На этом и заканчивается первая часть решения, но отнюдь не все решение.

В предыдущем абзаце совсем не зря выделены слова «в определенном порядке». Полученное произведение не равно числу возможностей выбора трех солдат, а больше этого числа, причем выделенные слова как раз и объясняют, почему. Дело в том, что мы можем получить один и тот же наряд, вызывая солдат в различном порядке. Поэтому необходимо подсчитать, какое число раз может получиться один и тот же наряд, и разделить полученное выше произведение на это число.

Остается, следовательно, определить, в каком числе случаев будет получаться один и тот же наряд. Это можно подсчитать, решая в каком-то смысле обратную задачу: каким числом способов можно расставить в шеренгу трех солдат уже выбранного наряда. Очевидно, что это число равно требуемому. Но это число легко под считать, пользуясь обычным приемом: чтобы поставить какого-либо солдата на первое место, есть три различные возможности, на второе место остается два солдата и на третье — только один Поэтому общее число возможных перестановок трех солдат в шеренге равно

Итак, каждый наряд из трех солдат можно расставить в шеренгу 3! различными способами, а, значит, в произведении показывающем число возможностей при выборе трех человек в определенном порядке, каждый наряд считается ровно 3! раз. Поэтому общее число различных способов, которыми можно назначить в наряд трех солдат из пятидесяти, равно

Число различных нарядов из одного сержанта и трех солдат равно теперь

Пример 2. Сколько членов, содержащих две буквы, получится после раскрытия скобок в выражении

Решение. После раскрытия всех скобок мы получим сумму некоторого числа слагаемых (нетрудно подсчитать, что общее число слагаемых равно , но для решения поставленной задачи это не существенно), каждое из которых состоит из шести множителей. Различные множители, входящие в одно и то же произведение, берутся из различных скобок. При этом для каждого множителя есть две различные возможности — он может быть либо буквой, либо единицей.

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

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

Пример 3. Подсчитаем, сколько в рассмотренном в предыдущем примере произведении слагаемых, содержащих четыре буквы.

Решение этой задачи аналогично решению предыдущей. Тем же методом можно подсчитать, что выбор четырех букв в определенном порядке может быть сделан различными способами. С другой стороны, каждая четверка считается здесь несколько раз, именно столько, каким числом способов можно ее упорядочить. Число способов упорядочить четверку букв равно произведению Поэтому число слагаемых, содержащих четыре буквы, равно

Этот ответ совпадает с ответом, полученным в предыдущем примере. Про это можно было бы догадаться заранее и, следовательно, обойтись без всяких вычислений, сославшись на предыдущий результат. В самом деле, легко понять, что комбинаций пар букв столько же, сколько комбинаций четверок: каждой паре букв соответствует одна-единственная определенная четверка, которая остается, когда мы удалим выбранную пару. Разным парам соответствуют разные четверки и, наоборот, разным четверкам соответствуют разные пары. Поэтому число различных пар и различных четверок букв одинаково.

Пример 4. В классе мест. Каким числом способов можно рассадить в нем учеников

Решение. Если в этой задаче и есть что-либо новое по сравнению с предыдущими, то только то, что в ней нет конкретных числовых данных. Способ решения задачи от этого, естественно, не изменяется.

Представим себе, что ученики входят в класс по одному. Тогда для первого из них имеется возможностей выбрать место. После того как первый выбрал какое-то место, для второго остается возможностей. Далее, для третьего будет различных возможностей и т. д. Искомое число способов рассадить всех учеников выразится произведением

Найдем последний сомножитель этого произведения. Его можно определить по-разному, например так: каждый сомножитель на единицу меньше предыдущего и получается вычитанием из числа, на единицу меньшего, чем номер сомножителя. Поэтому сомножитель с номером получается вычитанием из числа , то есть равен

Можно рассуждать и иначе: после того как все ученики рассядутся, в классе должно остаться свободных мест. Перед входом последнего ученика свободных мест было на 1 больше, то есть . Таково же число возможностей для выбора мест последним учеником, то есть последний сомножитель в произведении.

Итак, искомое число различных способов рассадить учеников на местах равно произведению последовательных целых чисел от до включительно:

Пример 5. В комнате имеется пять лампочек. Сколько существует различных способов освещения?

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

своей простоте, потребует сравнительно длинных рассуждений и вычислений.

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

Теперь присоединим к первой лампочке вторую. Она тоже может находиться в одном из двух состояний: гореть, либо не гореть. Так как каждое состояние второй лампочки можно комбинировать с любым состоянием первой, то для двух лампочек число различных состояний, то есть различных способов освещения, равно

Дальнейшие рассуждения теперь уже совершенно очевидны. Каждая из лампочек может находиться в двух состояниях. Поэтому, присоединяя новую лампочку к уже рассмотренным предыдущим, мы увеличиваем число возможных способов освещения вдвое. Следовательно, при трех лампочках будет 23 различных способов освещения, при четырех — 24 и, наконец, при пяти лампочках способа освещения.

Пример 6. Чему равен коэффициент при и при в выражении после раскрытия скобок.

Решение. Внимательный читатель сразу заметит, что этот пример очень похож на только что разобранный выше пример 4. Еще большую похвалу заслужит тот, кто заметит связь этого примера с примером 7 из предыдущего параграфа.

Выражение можно рассматривать как произведение 88 скобок; из каждой нужно выбрать в качестве множителя одно из слагаемых: либо а, либо Если мы ищем коэффициент при то нужно определить, каким числом способов можно выбрать из 88 букв а и ровно шесть букв а. Но именно этот вопрос мы решали в примере 7 предыдущего параграфа, когда нужно было определить число различных аккордов из 6 нот.

Благодаря замеченной общности задач мы могли бы воспользоваться уже готовым результатом; но мы повторим совсем коротко приведенные там рассуждения в новых терминах, относящихся уже к данной задаче.

Шесть букв а можно разместить на 88 возможных местах числом способов, равным произведению

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

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

Число возможных способов переставлять между собой шесть букв на шести местах, как мы уже видели, равно 6! Поэтому число различных способов выбрать шесть букв а из 88, а значит, и коэффициент при члене в разложении равно

Легко догадаться, что коэффициент при равен тому же числу. Соответствующее рассуждение уже приводилось в примере 4: способов выбрать по 82 буквы а из 88 равно столько же, сколько способов выбрать по 6, так как каждой группе по 6 букв соответствует определенная группа по 82 буквы, состоящая из оставшихся 82 мест. Но мы можем и не обращаться к этому рассуждению, рассматривая для члена не выбор букв а, наоборот, выбор шести букв Отсюда снова вытекает, что коэффициенты при одинаковы.

Источник