сколькими способами можно указать на шахматной доске две клетки черную и белую
Сколькими способами можно указать на шахматной доске две клетки черную и белую
II. Размещения из n элементов по k
III. Сочетания из n элементов по k
Задачи занятия №3
Размещения
а) У туриста есть пять способов подняться на гору. Для каждого из этих способов существует по пять возможностей спуститься вниз. Соответственно, способов подняться на гору, а затем спуститься с нее, существует ровно 5·5 = 25.
б) В отличие от пункта а, теперь для каждого из пяти способов подняться на гору есть лишь по четыре возможности спуститься: по той же дороге, по которой турист поднимался, спускаться уже нельзя. Так что в этом случае есть 5·4 = 20 возможных маршрутов.
a) Выбрать капитана можно четырьмя способами. При каждом из четырех способов выбора капитана есть по три способа выбрать первого помощника из оставшихся пиратов. А при каждом способе выбора капитана и помощника выбрать боцмана можно двумя способами. Поэтому всего возможностей распределить должности будет 4·3·2=24.
b) Решение аналогично решению пункта а. 6·5·4=120.
с) Решение аналогично решению двух предыдущих пунктов. Вычислять произведение чисел 20·19·18·17 проще всего так: 20·19·18·17 = (20·18)·(18-1)·(18+1) = 360·(18²-1) = 360·(324-1) = 360·323 = 116280 (здесь мы пользовались формулой для разности квадратов). Последнее умножение в этой цепочке можно проделать в столбик, а можно продолжить преобразования и привести выражение к такому виду, чтобы все действия можно было выполнить в уме (попробуйте проделать это самостоятельно). Вычислить 18² можно при помощи формулы для квадрата суммы: 18² = (20-2)² = 20²-2·20·2+2² = 400-80+4 = 324.
Посчитаем это количество. Отметим, что в каждой ячейке нижней строки нашей таблицы может стоять любой номер от 1 до 6 (каждый из шаров может попасть в любую лузу). Поэтому число способов ее заполнить равно 6·6·…·6 = 6 15 (произведение состоит из 15 сомножителей).
Точное значение числа 6 15 находить не обязательно, но можно вычислить, что оно равно 470184984576. Попробуйте это сделать, используя умножение не более шести раз. Все действия выполняйте в уме или в столбик: калькулятором пользоваться запрещается!
Сначала выберем черное поле. Как известно, на шахматной доске 8·8=64 клетки, и ровно половина из них черные. Значит, выбрать черное поле можно 32 способами.
В каждой вертикали и в каждой горизонтали есть по четыре белые клетки. Значит, на одной вертикали или на одной горизонтали с любой выбранной черной клеткой лежат 8 белых клеток. Так как всего белых клеток на доске 32, то не лежащих на одной горизонтали или вертикали с нашей черной клеткой среди них будет 32-8 = 24. Тем самым есть 32 способа выбрать черную клетку, и для каждого из этих способов по 24 возможности выбрать белую клетку. Значит, всего возможностей выбрать пару разноцветных клеток, не лежащих на одной горизонтали или вертикали, будет 32·24 = 768.
Перестановки
a) Ясно, что искомые числа состоят из цифр 1, 2, 3, 4, 5, расставленных в разном порядке. Значит, количество таких чисел равно количеству способов упорядочить множество из пяти цифр. На первое место можно поставить любую цифру от 1 до 5. После того как первая цифра выбрана, вторую можно выбрать четырьмя способами. Когда выбраны первая и вторая цифры, третью можно выбрать тремя способами, и так далее. Значит, всего искомых чисел 5·4·3·2·1 = 5! = 120 (сравните с пунктом I «Теоретических сведений»).
b) Здесь, в отличие от пункта а, на первое место можно поставить не любую цифру: число не может начинаться с нуля. Поэтому на первом месте может стоять любая из четырех, а не пяти, цифр. Дальнейшие рассуждения полностью аналогичны предыдущим. Так что всего искомых чисел будет 4·4·3·2·1 = 96.
Задачи занятия №4
Сочетания без повторений
a) Выбрать пять человек из шести — все равно, что выбрать одного, которого в команду не возьмут. А выбрать одного человека из шести, очевидно, можно шестью способами.
b) Аналогично предыдущему, выбрать пять человек из семи — все равно, что выбрать двух. Первого человека можно выбрать 7 способами, а второго после этого — шестью. То есть если важно, кто первый, а кто второй, число способов это сделать равно 7·6 = 42. Но одну и ту же пару человек можно упорядочить двумя способами. Значит, число неупорядоченных пар, выбранных из семи человек, равно 42:2 = 21.
c) Набрать две команды по пять человек из десяти претендентов — все равно что набрать одну команду, а из остальных претендентов составить другую. Посчитаем число способов выбрать пять человек из 10. Если порядок важен, то есть 10·9·8·7·6 способов это сделать. Но существует 5! = 120 способов упорядочить 5 человек (вспомните задачу 3.10 а). Так что каждому способу выбрать 5 человек неупорядоченным образом соответствует 120 способов выбрать их упорядоченным образом. Значит, количество способов набрать команду из пяти человек в 120 раз меньше, чем 10·9·8·7·6. А это, как нетрудно посчитать, есть в точности 252.
Упорядоченные выборки, полученные из разных неупорядоченных выборок, различны (хотя бы потому, что состоят из различных элементов). Каждую упорядоченную выборку можно получить из какой-то неупорядоченной (а именно той, которая состоит из элементов интересующей нас упорядоченной). Тем самым доказано, что упорядоченных выборок из k элементов ровно в k! раз больше, чем неупорядоченных выборок того же объема. Это и доказывает первое равенство в приведенной формуле.
Сочетания с повторениям
Пусть пирожки разных типов разложены на пяти лотках. Когда мы покупаем пирожки, мы действуем так: сначала берем сколько-то пирожков с картошкой (может быть, ни одного), затем переходим к лотку с пирожками с капустой и берем сколько-то пирожков оттуда, и так далее до тех пор, пока не наберем восемь пирожков.
Последовательность наших действий при этом можно описать так. Запишем в ряд восемь единиц. Отсчитаем от начала столько единиц, сколько пирожков с картошкой мы взяли, и поставим после них вертикальную черту. В частности, если мы не взяли ни одного пирожка с картошкой, поставим черту перед первой единицей, а если мы их взяли сразу восемь, поставим ее после последней единицы. Далее проделаем то же самое по отношению к пирожкам с капустой, с мясом, с рисом и с яблоком. Если в какой-то момент мы наберем восемь пирожков, а до последнего лотка еще не дойдем, оставшиеся вертикальные черточки будем в нужном количестве ставить после последней единицы. Если, наоборот, мы ничего не возьмем с первых нескольких лотков, черточки будем ставить перед первой единицей.
Всего в нашей записи будет 8 единиц и четыре вертикальные черты, то есть 12 символов. Чтобы получить произвольную запись такого вида, нужно выбрать 8 позиций из 12, на которые мы поставим единицы, а на остальные позиции поставить вертикальные черточки. Тем самым количество возможных способов купить восемь пирожков равно C 8 12 = 495 (примените формулу из задачи 4.2).
Применим принцип, использованный в предыдущих задачах. Сначала распределим по лифтам пятиклассников, потом шестиклассников, затем семиклассников и наконец, восьмиклассников.
Присвоим лифтам номера от 1 до 5. Каждый способ распределить по лифтам пятиклассников будем записывать так: сначала пишем в ряд столько единиц, сколько пятитклассников посадим в первый лифт, затем ставим вертикальную черту и пишем еще столько единиц, сколько пятитклассников посадим во второй лифт, и так далее. Число таких записей равно числу способов распределить по лифтам пятиклассников и равно в точности C 4 14 (вспомните предыдущие задачи). Для шестиклассников аналогичным образом получим C 4 15 способов, для семиклассников C 4 12 и наконец, для восьмиклассников C 4 16 способов. Теперь все эти числа надо перемножить.
Разные задачи
При решении задачи 3.11 мы подсчитали, что число кодов, состоящих из не более чем четырех символов азбуки Морзе, равно 30. Среди этих кодов есть только два, которые используют более трех однотипных символов: это, соответсвенно, код из четырех точек и код из четырех тире. Все остальные коды нам подходят. Тем самым у нас уже есть 28 «хороших» кодов. Осталось придумать еще пять кодов, удовлетворяющих нашим требованиям. Например, таких: — — — · ·, · — — — ·, · — · — ·,— · — · —, — — — · · ·. Теперь у нас есть 33 «хороших» кода, и мы можем ими зашифровать весь русский алфавит.
Попробуйте самостоятельно сосчитать количество всех «хороших» кодов. Хватит ли их, чтобы зашифровать сначала русские буквы, а потом латинские? А цифры?
a) Число треугольников с вершинами в этих точках равно числу способов выбрать две точки на одной прямой и одну — на другой. При этом пару точек, лежащих на одной из прямых, нужно выбирать неупорядченным образом: при их перестановке треугольник не изменится. Если одну вершину выбирать на первой прямой, а еще две на второй, то получится 10·C 11 2 = 550 различных треугольников (10 способов выбрать вершину на первой прямой и C 10 2 = 55 способов выбрать две вершины на второй прямой). Аналогично найдем, что если на первой прямой брать две вершины, а на второй — только одну, получится 11·C 10 2 = 495 различных треугольников. Значит, всего треугольников с вершинами в отмеченных точках существует 550+495 = 1045.
b) Для построения четырехугольника надо выбрать по две точки на каждой прямой (иначе получится не четырехугольник, а треугольник или даже отрезок). При этом та точка, которая лежит левее на первой прямой, будет соединяться стороной с точкой, лежащей левее на второй прямой (и то же самое касается точек, которые лежат правее), иначе получится фигура, которую мы четырехугольником не считаем (попробуйте нарисовать такую фигуру). Поэтому пары точек на каждой прямой надо выбирать неупордоченным образом, а затем вершины соединять вышеуказанным способом. Всего есть C 10 2 = 45 способов выбрать пару точек на первой прямой и C 11 2 = 55 способов выбрать пару точек на второй прямой. Количество искомых четырехугольников равно произведению этих чисел, а именно 2475.
Выберем какого-нибудь человека из нашей компании (назовем его А). Тогда в компании либо есть трое, которые с ним знакомы, либо трое, которые с ним незнакомы. Этих троих назовем Б, В, Г.
Пусть сначала Б, В, Г знакомы с А. Если среди них есть двое знакомых друг с другом, то эти двое и А знакомы между собой, и утверждение задачи выполнено. Если же среди них нет знакомых, то они и есть те трое, которые друг с другом не знакомы, и утверждение вновь выполнено. Случай, когда Б, В и Г не знакомы с А, рассматривается точно так же, только слова «знакомы» и «не знакомы» меняются местами.
Разработка занятий по разделу Комбинаторика
Занятие 1. Правило произведения
• дать понятие «кортеж»;
• познакомить учащихся с правилом произведения в комбинаторике;
• закрепить данное правило при решении задач.
Любой номер, составленный из трех цифр, нельзя рассматривать как множество из трех элементов, так как:
1) в номерах цифры могут повторяться (например, 775), а в множествах элементы не повторяются;
2) в номерах важен порядок цифр (175 и 571 — совсем разные номера), а в множествах порядок элементов роли не играет.
Поэтому при изучении таких объектов, как номера или слова (в них буквы могут повторяться, а от перестановки букв слово меняется), вводится новое математическое понятие «кортеж».
Элементы кортежа могут повторяться, так как в определении не сказано, что элементы множеств X 1 , Х 2, …, X k не могут иметь одинаковых элементов.
ОПРЕДЕЛЕНИЕ. Два кортежа называют равными в том и только том случае, когда они имеют одинаковую длину, а на соответствующих местах стоят одни и те же элементы.
Примером кортежа длины 6 являются номера телефонов, они составлены из элементов множества X = <0, 1, 2, 3, 4, 5, 6, 7, 8, 9>. Слова русского языка (точнее, их запись) — кортежи различной длины, составленные из букв русского алфавита, а предложения — кортежи, составленные из русских слов.
Задача 1. Из города А в город В ведут пять дорог, а из города В в город С — три дороги. Сколько путей, проходящих через В, ведут из А в С?
Задача 2. Сколькими способами можно выбрать гласную и согласную буквы слова «полка»?
Задача 3. Имеется шесть перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну на правую руку так, чтобы эти перчатки были различных размеров?
Решение. Эту задачу тоже можно решить по правилу произведения. Перчатка на левую руку может быть выбрана шестью способами. После того, как она выбрана, перчатку на правую руку можно выбрать лишь пятью способами (размеры перчаток должны быть разными). Поэтому всего имеет 6 • 5 = 30 способов.
Решение. Эту задачу также можно решать по правилу произведения. На первое место Парис может
выбрать тремя способами, на второе — двумя способами (одна претендентка уже находится на первом месте), на третье место — одним способом. Поэтому всего имеем 3 • 2 • 1 = 6 способов.
Решение. На золотую медаль претендуют 12 команд, на серебряную — 11 команд (одна получит золотую медаль). По правилу произведения получаем 12∙11 = 132 способа.
Задачи для домашней работы
1. Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?
2 . На вершину горы ведут семь дорог. Сколькими способами турист может подняться на гору и потом спуститься с нее? Решите эту же задачу при дополнительном условии, что спуск и подъем происходят по разным дорогам.
3. Сколькими способами можно указать на шахматной доске два квадрата — белый и черный? Решите эту же задачу, если нет ограничений на цвет квадратов; если надо выбрать два белых квадрата.
1. Десять участников конференции обменялись рукопожатиями, пожав каждый каждому руку. Сколько всего рукопожатий было сделано?
2. Сколько различных шифров можно набрать в автоматической камере хранения, если шифр составляется с помощью любой из тридцати букв русского алфавита с последующим трехзначным числом?
3. Сколько имеется семизначных натуральных чисел, в которых все цифры, стоящие на нечетных местах, различные?
4. Сколько различных танцевальных пар (юноша, девушка) можно составить из пяти юношей и восьми девушек?
5. На районную олимпиаду школа должна набрать команду из трех участников: одного из трех лучших надо выбрать для участия в олимпиаде по химии, одного из четырех — по физике, одного из семи — по математике. Сколькими способами можно составить такую команду?
6. Сколько различных трехзначных чисел, не имеющих одинаковых цифр, можно записать с помощью цифр 1, 2 и 3? Сколькими способами можно составить расписание уроков на один день из шести разных учебных предметов?
7. Путешественник может попасть из пункта А в пункт С, проехав через пункт В. Между пунктами А и В имеется три автодороги. А между пунктами В и С — железнодорожное и речное сообщения. Сколько существует различных маршрутов между пунктами А и С?
8. В одной из стран автомобильные номера из четырех цифр (нуль не может стоять на первом месте) записываются на пластинках пяти различных цветов (каждый из пяти штатов этой страны имеет номера своего цвета). Сколько разных пластин с номерами может быть выдано автовладельцам в этой стране?
9. Десять участников конференции обменялись визитными карточками (каждый вручил свою карточку всем другим участникам). Сколько всего карточек было роздано?
10. Имеется восемь видов конвертов без марок и пять видов марок. Сколькими способами можно выбрать конверт и марку для отправки письма?
11. Из трех экземпляров учебника алгебры, семи экземпляров учебника геометрии и шести экземпляров учебника физики надо выбрать комплект, содержащий все три учебника по одному разу. Сколькими способами это можно сделать?
12. В корзине лежит 12 яблок и 10 апельсинов. Ваня выбирает либо яблоко, либо апельсин, после чего Надя выбирает из оставшихся фруктов и яблоко, и апельсин. Сколько возможно таких выборов? При каком выборе Вани у Нади больше возможностей выбора?
• проверить усвоение правила произведения;
• сформулировать определение размещений с повторениями и без повторений;
• закрепить на задачах число размещений с повторениями или без повторений.
Проверка домашней работы
Первые две задачи подобны тем, которые разбирались в классе. Рассмотрим решение задачи 3.
На шахматной доске 64 клетки: 32 белых квадрата, 32 черных квадрата. Поэтому по правилу произведения находим число способов выбора двух квадратов: одного белого и одного черного: 32 • 32 = 1024.
Если нет ограничений на цвет, то первый квадрат можно выбрать 64 способами, а второй квадрат — 63 способами (один квадрат уже выбран). Поэтому общее число способов равняется 64 • 63 = 4032.
Если надо выбрать два белых квадрата, то первый квадрат можно выбрать 32 способами, а второй квадрат — 31 способом. Поэтому общее число способов равно 32 • 31 = 992.
Размещения с повторениями
Из правила произведения сразу вытекает, что число размещений с повторениями из п элементов по k равно произведению k сомножителей, каждый из которых равен п:
Перед решением задач с учащимися необходимо по данной формуле вычислить несколько значений, чтобы при решении задач не возникало трудностей работы с самой формулой.
Задача 1. Для запирания автоматической камеры применяется секретный замок, который открывается лишь тогда, когда набрано «тайное слово». Это слово набирают с помощью пяти дисков, на каждом из которых изображено 12 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова и подбирающего его наудачу?
Решение. Из условия задачи видно, что порядок выбираемых букв существенен. Поэтому мы имеем дело с кортежем длиной 5 (пять дисков). Каждый элемент кортежа может быть выбран 12-ю способами (букв на каждом диске 12). Поэтому число комбинаций равно 12 5 = 248832. Следовательно, неудачных попыток может быть 248831.
Решение. Здесь порядок цифр существенен (2678 или 6278 — это разные числа). Поэтому имеем дело с кортежем длины 4 (четырехзначное число), каждый элемент которого можно выбрать пятью способами (цифр дано пять). Поэтому число различных комбинаций равно 4 5 = 1024.
Задача 3. На референдуме предложены четыре вопроса, на которые надо ответить «да» или «нет». Сколько есть возможностей заполнения бюллетеня (на все вопросы надо дать ответ)?
Решение. Получаем кортеж длины 4 (столько вопросов в бюллетене), каждый элемент может быть выбран двумя способами («да» или «нет»). Поэтому число различных возможностей равно 2 4 = 16.
Задача 4. Неудовлетворенные решением Париса Гера, Афина и Афродита обратились к трем мудрецам с просьбой назвать прекраснейшую из них. Каждый из мудрецов высказал свое мнение. Сколько могло возникнуть вариантов ответа на поставленный вопрос у этой тройки?
Решение. Здесь вновь кортеж длиной 3 (три мудреца), каждый элемент которого может быть выбран шестью способами. Поэтому число различных возможностей равно 6 3 = 216.
Задачи для домашней работы
1. Сколько букв русского алфавита можно закодировать, используя лишь комбинации точек и тире, содержащие только три знака?
2. Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневый переплеты. Сколькими способами он может это сделать?
Размещения без повторений
Упражнение. Вычислите: 4!; 6!.
Решение. 4! = 4 • 3 • 2 • 1 = 24;
При решении комбинаторных задач часто необходимо вычислить факториал, поэтому целесообразно вывешивать на доску следующую таблицу.
Задача 1. В высшей лиге первенства по футболу участвуют 16 команд. Разыгрывается три медали: золотая, серебряная и бронзовая. Перед началом первенства был объявлен конкурс знатоков, в котором требовалось указать распределение медалей. Сколько различных ответов можно дать на этот вопрос?
Решение. Здесь речь идет о кортежах длины 3. Но ни один элемент не может входить дважды (одна и та же команда не может получить и золотую, и серебряную медали). Значит, число различных ответов находим следующим образом:
Задача 2. Из спортивного клуба, насчитывающего 30 членов, надо составить команду из четырех человек для участия в эстафете на 100 + 200 + 400 + 800 (м). Сколькими способами это можно сделать?
Решение. Имеем кортежи длиной 4. Ни один элемент не может входить дважды (один бегун на один отрезок дистанции). Значит,
Решение. Имеем кортежи длиной 3 (у треугольника три вершины). Ни один элемент не может входить дважды. Значит,
Задачи для домашней работы
1. Сколько всего различных пятизначных чисел, не содержащих нуля?
2. В классе изучают девять предметов. Сколькими способами можно составить расписание на понедельник, если в этот день должно быть шесть разных уроков?
Ответы: 1. 15 120. 2. 720.
Размещения с повторениями
1. Сколькими способами можно разделить шесть различных конфет между тремя детьми?
2. Сколько существует пятизначных номеров, не содержащих цифру 8?
3. Сколькими способами можно разложить 12 различных деталей по трем ящикам?
4. Имеется набор из 16 карточек. На четырех из них написана буква «А», на четырех — буква «Б», на четырех — буква «В» и на четырех — буква «Г». Сколько различных комбинаций букв можно получить, выбирая из набора четыре карточки и располагая их в некотором порядке?
5. В некотором сказочном королевстве не было двух человек с одинаковым набором зубов. Каково может быть наибольшее число жителей этого королевства, если у человека 32 зуба?
Размещения без повторений
1. В классе 30 человек. Сколькими способами могут быть выбраны из них староста и казначей?
2. В чемпионате по футболу участвуют десять команд. Сколько существует различных возможностей занять командам первые три места?
3. В цехе работают восемь токарей. Сколькими способами можно поручить трем из них изготовление трех различных видов деталей (по одному виду на каждого)?
4. Из десяти различных книг выбирают четыре для посылки. Сколькими способами это можно сделать?
5. В профком избраны семь человек. Из них надо выбрать председателя, его заместителя и секретаря. Сколькими способами это можно сделать?
6. Сколькими способами можно опустить пять писем в 11 почтовых ящиков; если в каждый ящик опускают не более одного письма?
7. Сколькими различными способами можно распределить между шестью лицами две различные путевки в санаторий?
8. В турнире по шахматам каждый участник сыграл с каждым по одной партии, всего было сыграно 36 партий. Определите число участников турнира.
• проверить усвоение темы прошлого занятия через проверку домашнего задания;
• познакомить учащихся с перестановками без повторений и с повторениями;
• закрепить новую тему при решении задач.
В начале урока проверить решение задач, заданных на дом.
Решить следующую задачу.
Задача. На железнодорожной станции имеется п семафоров. Сколько может быть дано различных сигналов при помощи этих семафоров, если каждый семафор имеет три состояния: горит либо зеленый, либо желтый, либо красный свет.
Перестановка без повторений
ОПРЕДЕЛЕНИЕ. Два размещения без повторений из п элементов по п состоят из одних и тех же элементов, расположенных в различном порядке. Такие размещения называют перестановками из п элементов. Их число обозначают Р п :
Задача 1. Найдите число способов расстановки восьми ладей на шахматной доске, при которых они не бьют друг друга.
Решение. Каждый искомый способ задается перестановкой восьми чисел 1, 2, …,8. Эти числа указывают номера горизонталей занятых полей на первой, второй,…, восьмой вертикалях. Значит, таких перестановок 8!. Таким образом, ладьи можно расставить 8! = 40 320 способами.
Задача 3. За столом пять мест. Сколькими способами можно рассадить пятерых гостей?
Задача 4. У Лены есть восемь разных красок. Она хочет написать ими слова «Новый Год». Сколькими способами она может это сделать, если каждая буква должна быть раскрашена одним цветом и все восемь букв должны быть разными по цвету?
Решение. Присвоим каждой краске номер от 1 до 8. Тогда каждый искомый способ задается перестановкой восьми чисел 1, 2,…, 8. Значит, таких перестановок 8!. Поэтому она может написать «Новый Год» 8! = 40 320 способами.
Перестановки с повторениями
Задача 1. Сколько различных кортежей получится, если переставлять буквы слова «математика»?
Решение. Это слово имеет состав: м — 2, а — 3, т — 2, е — 1, и — 1, к — 1, то есть (2, 3, 2, 1, 1, 1), поэтому получим
Задача 2. У мамы два яблока и три груши. Каждый день в течение пяти дней она дает сыну по одному фрукту. Сколькими способами это может быть сделано?
Задача 3. Сколькими способами можно положить 28 различных открыток в четыре одинаковых конверта так, чтобы в каждом конверте было по семь открыток?
Решение. Пометим конверты цифрами 1, 2, 3 и 4. Тогда число различных раскладок равно
Задачи для домашней работы
1. Сколько различных слов можно получить, переставляя буквы слова «ингредиент»?
2. Сколькими способами можно посадить за круглый стол пять мужчин и пять женщин так, чтобы никакие два лица одного пола не сидели рядом?
3. Автомобильные номера состоят из четырех цифр и трех букв. Найдите число таких номеров, если используются 32 буквы русского алфавита.
Перестановки с повторениями
1. Сколькими различными способами можно усадить за стол трех мальчиков и трех девочек так, чтобы никакие две девочки не сидели рядом?
2. Задача-шутка. Как-то раз в воскресенье семеро друзей зашли в кафе. Хозяин кафе сказал, что если друзья в каждое следующее воскресенье будут садиться по-разному и перепробуют все способы посадки, то с этого момента он обещает кормить всех мороженым бесплатно. Удастся ли друзьям воспользоваться предложением хозяина кафе?
3. Сколькими способами можно разложить 28 различных предметов по четырем различным ящикам так, чтобы в каждом ящике, оказалось по семь предметов?
4. Для премирования победителей математической олимпиады выделено три экземпляра одной книги, четыре экземпляра другой и восемь экземпляров третьей. Сколькими способами могут быть распределены эти премии между 30 участниками олимпиады, если каждому вручается не более одной книги?
5. Сколькими способами можно переставлять буквы слова «огород», чтобы три буквы «о» не шли подряд?
Перестановки без , повторений
1. Сколькими способами можно разместить 12 человек за столом, на который поставлено 12 приборов?
2. Сколькими способами можно установить дежурство по одному человеку в день среди семи учащихся группы в течение семи дней?
3. Сколько пятизначных чисел, не содержащих одинаковых цифр, можно записать с помощью цифр 1, 2, 3, 4 и 5 так, чтобы:
а) последней была цифра 4;
б) первой была цифра 2, а второй 3?
4. Имеется 10 книг, среди которых:
а) восемь книг разных авторов и двухтомник одного автора, которого не было среди предыдущих семи;
б) семь книг разных авторов и трехтомник восьмого автора.
Сколькими способами можно расставить эти книги на полке так, чтобы книги одного автора не стояли рядом?
Занятие 5. Сочетания
• дать понятие сочетаний с повторениями и без повторений;
• закрепить тему при решении задач.
В начале урока разбираются задачи, заданные на дом.
Сочетания с повторениями
ОПРЕДЕЛЕНИЕ 1. Два кортежа называются эквивалентными, если они имеют одинаковый состав.
Решение. Здесь рассматриваются сочетания с повторениями из 4 (четыре вида пирожных) по 7 (столько пирожных покупают). Значит,
Ответ: 120 способов.
Решение. Здесь рассматриваются сочетания с повторениями из 10 по 12. Имеем
Сочетания без повторений
Решение. Здесь рассматриваются сочетания без повторения (одно число может быть по правилам игры выбрано не более одного раза) из 49 по 6.
Решение. Здесь рассматриваются сочетания без повторений.
Задача 3. Дама сдавала в багаж семь предметов. Все они оказались украденными, но два каких-либо (по ее выбору) ей согласились поискать. Сколько у нее есть возможностей выбрать два любимых предмета?
Задача 4. В прошлые века процветала генуэзская лотерея, сохранившаяся в некоторых странах и поныне. Участники этой лотереи покупали билеты, на которых стояло число от 1 до 90. Можно было купить и билеты, на которых было сразу 2, 3, 4 и 5 чисел. В день розыгрыша лотереи из мешка, содержащего жетоны с числами от 1 до 90, вынимали пять жетонов. Выигрывали те, у которых все номера на билетах были среди вынутых. Если участник лотереи покупал билет с одним числом, то он получал при выигрыше в 15 раз больше стоимости билета; если с двумя числами (амбо), то в 270 раз больше, если с тремя числами (терн) — в 5500 раз больше, если в четырьмя числами (катерн) — в 75 000 раз больше, а если с пятью числами (квин) — в 1 000 000 раз больше, чем стоил билет. Каково отношение «счастливых» билетов при игре, когда участник купил билет с одним числом?
Решение. Общее число исходов находится из формулы сочетаний без повторений:
Если участник купил билет с одним номером, то для выигрыша необходимо, чтобы один из вынутых номеров совпал с номером на билете. Остальные 4 номера могут быть благоприятными. Но эти 4 номера выбираются из оставшихся 89 номеров. Поэтому число благоприятных комбинаций выражается формулой
Отсюда следует, что отношение числа благоприятных комбинаций к общему числу комбинаций равно
Задачи для домашней работы
1. Сосчитайте, каково отношение «счастливых» билетов при игре, когда участник купил билет с двумя числами.
2. Сколькими способами можно составить набор из восьми пирожных, если имеется четыре сорта пирожных?
3. В классе имеется шесть сильных математиков. Сколькими способами из них можно составить команду на районную олимпиаду по математике, если от класса можно послать команду из четырех человек?
Ответы: 1. 2. 165. 3. 15.
Сочетания с повторениями
1. Сколько существует треугольников, длины сторон которых принимают одно из следующих значений: 4 см, 5 см, 6 см и 7 см?
2. Сколько можно построить различных прямоугольных параллелепипедов, длины ребер которых выражаются натуральными числами от 1 до 10?
Сочетания без повторений
1. Сколькими способами можно составить команду из четырех человек для соревнований по бегу, если имеется семь бегунов?
2. Сколькими способами можно выбрать пять делегатов из участников конференции, на которой присутствуют 15 человек?
3. Сколькими способами можно поставить восемь шашек на черные поля доски?
4. Сколькими способами можно поставить на черные поля 12 белых и 12 черных шашек?
5. У одного человека есть 11 книг по математике, у другого 15 книг. Сколькими способами они могут выбрать по три книги для обмена?
6. Сколькими способами можно распределить две одинаковые путевки между пятью лицами?
7. Сколькими способами можно присудить шести лицам три одинаковые премии?
8. В классе 30 учащихся. Сколькими способами можно:
а) назначать двух дежурных;
б) выбрать 28 человек для осеннего кросса.
Занятие 6. Решение задач
• закрепить навыки решения комбинаторных задач простейшего типа.
Решение. Каждая точка пересечения однозначно определяется парой проходящих через нее прямых. При этом порядок прямых роли не играет. Поэтому искомое число точек пересечения равно числу сочетаний из п по 2, то есть
Решение. Здесь идет речь о размещениях без повторений. Имеем
Рассуждать можно было по-другому. Нужно найти число кортежей длины 3 (на три должности выбирают). На первую должность выбираем из девяти человек, на вторую — из восьми человек, на третью — из семи человек. По правилу произведения получаем 9∙8∙7 = 504.
Решение. Здесь имеем дело с размещениями с повторениями из двух элементов (тире и точки) по 7 (длина кортежа). Поэтому искомое число находится следующим образом:
Решение. Получаем перестановки с повторениями. Их число будет равно
Решение. По правилу произведения находим, что искомое число равно 12 ∙ 9∙ 10 = 1080.
Задача 6. У профессора есть три любимых каверзных вопроса. В группе 20 студентов.
а) Профессор решил задавать каждому из студентов по одному из каверзных вопросов. Сколько есть возможностей провести опрос в группе?
б) Профессор решил наудачу по списку группы выбрать студента, чтобы задать ему первый вопрос, потом опять из всего списка выбрать второго студента, чтобы задать ему второй вопрос, потом так же выбрать третьего студента. Сколько у него возможностей провести опрос в этом случае?
в) Профессор решил спрашивать только троих студентов, каждому по одному вопросу (так, чтобы вопросы не повторялись). Сколько у него есть возможностей в этом случае?
Решение а) Здесь, кортеж длиной 20 (20 студентов), каждый элемент которого можно выбрать тремя способами (три вопроса). Значит, речь идет о размещениях с повторениями.
б) Кортеж длиной 3 (три вопроса), первый элемент можно выбрать 20-ю способами (20 студентов), второй элемент — 19-ю способами (осталось 19 неопрошенных студентов), третий — 18-ю способами. По правилу произведения определяем число возможностей: 20 ∙ 19 ∙ 18 = 6840.
Можно рассуждать по-другому. Речь идет о кортежах длиной 3 (три вопроса). Ни один элемент не может входить дважды. Следовательно, речь идет о размещениях без повторений.
в) Здесь профессор из 20 студентов выбирает троих. Следовательно, имеем сочетание без повторений.
Ответ: а) З 20 ; б) 6840; в) 1140.
Задачи для домашней работы
1. Имеется пять видов конвертов без марок и четыре вида с марками. Сколькими способами можно выбрать конверт с маркой для посылки письма?
2. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти различных цветов?
3. Сколькими способами можно составить четырехцветный флаг из горизонтальных полос, имея четыре различных цвета?
4. Из колоды, содержащей 52 карты, вынули десять карт. Сколькими различными способами это можно сделать?
Ответ: 1. 5 • 4 = 20. 2. = 60. 3. Р 4 = 4! = 24. 4
Занятие 7. Решение задач
Цель занятия: закрепление навыков решения простейших комбинаторных задач.
Решение. Белый квадрат можно выбрать 32 способами (произвольными). Черный квадрат — 24 способами (из 32 вычитаем 8, лежащих на одной горизонтали или вертикали с выбранным белым). По правилу произведения получаем искомое число 768.
Решение. Найдем, сколько троек из семи книг можно составить у первого человека:
Число троек из девяти книг у второго человека равно
По правилу произведения находим число обменов: 35∙84 = 2940.
Решение. Надо найти число кортежей длины 8, имеющих состав (2, 2, 2, 1, 1). Число таких перестановок с повторениями равно
Решение. Имеем размещения с повторениями из 6 элементов (в шесть луз) по 15 (15 шаров). Их число
Задача 5. Рота состоит из трех офицеров, шести сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из офицера, двух сержантов и 20 рядовых?
Решение. Имеем кортежи длиной 3 ( а, b , с ). Элемент а может быть выбран 3 способами (три офицера) элемент b (два сержанта из шести) можно выбрать способами, элемент с (20 солдат из 60) —
способами. По правилу произведения находим число выбора исходных кортежей: