Разработка пропедевтического курса "Комбинаторика"

Решение. Перебором приходим к следующему ответу - существует три различных способа ребятам сесть в зале: 1) Дима и Саша - 7, Олег - 12; 2) Дима и Олег - 7, Саша - 12; 3) Олег и Саша - 7, Дима - 12.

Задача 2. а) У нас имеется три цифры 1, 2 и 3. Сколько двузначных чисел мы можем составить из этих цифр, если каждую цифру в числе можно использовать только один раз?

Решение. Учащиеся методом перебора (пока бессистемного) приходят к ответу: 12, 13, 23, 21, 31, 32 - итого 6 чисел.

б) А теперь давайте посмотрим, как изменится наш ответ, если сказано, что цифры в числах могут повторяться?

Решение. Прибавится еще три числа: 11, 22, 33 - итого 9 чисел.

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

На следующем этапе урока перед учителем стоит задача: мотивировать переход от хаотичного к систематическому перебору.

Разыгрывается следующая ситуация: Маша, Саша и Даша едут в электричке на дачу. Они сидят на одной скамейке (трое детей садятся у доски на стулья в любом порядке). Детям нужно было проехать 8 остановок. Чтобы не было скучно ехать, они решили на каждой остановке меняться местами. Ставится вопрос «Смогут ли дети каждый раз меняться местами так, чтобы их новое расположение оказывалось все время отличным от предыдущих?». Ученики предлагают варианты расположения детей, они проигрываются у доски и записываются. Пока перебор осуществляется случайным образом, хаотично. После того как найдены 6 расположений, ученики стараются еще составить другой, новый вариант. Все их попытки сделать это не приводят к успеху. Встает вопрос «Почему они не нашли седьмой вариант: не могут это сделать или его не существует и уже найдены все возможные расположения?». Чтобы ответить на него, учащимся предлагается рассмотреть составленные 6 вариантов, найти и записать пары вариантов, очень похожие друг на друга. Например, можно выделить такие тройки:

М. С. Д. С. Д. М. Д. М. С.

М. Д. С. С. М. Д. Д. С. М.

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

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

Следующая задача решатся аналогично.

Задача 3. На завтрак Вова может выбрать плюшку, бутерброд, пряник или кекс, а запить их может кофеем, соком или кефиром. Из скольких вариантов завтрака Вова может выбирать?

Решение: КП КБ КПр КК

СП СБ СПр СК

КфП КфБ КфПр КфК

Ответ. 12 вариантов.

Задачи на закрепление

Задача 4. Четыре подружки вечером по телефону созваниваются друг с другом. Сколько звонков было сделано, если каждая подружка поговорила с каждой по одному разу?

Ответ. 6 звонков.

Задача 5. Составьте все возможные двузначные числа из указанных цифр, используя в записи числа каждую из них не более одного раза:

а) 1, 6, 8; б) 0, 3, 4.

Решение. а) Выбираем поочерёдно:16, 18, 61, 68, 81, 86. Всего 6 различных чисел.

б) Выбрать первый 0 мы не можем (число должно быть двузначным), поэтому выбираем на первую позицию только вторую и третью цифры 30, 34, 40, 43. Всего четыре различных двузначных числа.

Ответ. а) 16, 18, 61, 68, 81, 86; б) 30, 34, 40, 43.

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

Домашнее задание

Задача 6. У Ирины пять подруг: Вера, Зоя, Марина, Полина и Светлана. Она решила двух из них пригласить в кино. Укажите все возможные варианты выбора подруг. Сколько таких вариантов?

Ответ. 10 вариантов.

Задача 7. Укажите все способы, какими можно разложить три яблока в две вазы (учтите при этом случаи, когда одна из ваз окажется пустой).

Ответ. 4 способа.

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

Ответ. 6 наборов.

Совет учителю. На первом месте перед учителем стоит задача по формированию навыков систематического (полного!) перебора. Начинать нужно с простых задач, где не так много элементов, важна сама суть перебора всех вариантов.

Урок 2

Тема урока: «Решение комбинаторных задач с помощью дерева возможных вариантов и с помощью составления таблицы»

Изучение новой темы

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

Рассмотрим сначала метод построения дерева возможных вариантов:

Задача 1. В алфавите племени УАУА имеются только две буквы - «а» и «у». Сколько различных слов по три буквы в каждом можно составить, используя алфавит этого племени?

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

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

Теперь, проходя по веточкам дерева, по порядку выписываем нужные нам сочетания букв - «слова»:

ааа; аау; ауа; ауу; уаа; уау; ууа; ууу.

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

Рассмотрим еще одну задачу, решаемую с помощью построения дерева возможных вариантов:

Задача 2. Несколько стран в качестве символа своего государства решили использовать флаг в виде 3-х горизонтальных полос одинаковых по ширине и цвету: синий, красный и белый. Сколько стран могут испытать такую символику при условии, что у каждой страны свой отличный от других флаг?

Решение. Будем искать решение с помощью дерева возможных вариантов.

Размещено на http://www.allbest.ru/

Ответ. 6 комбинаций.

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

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

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

последн первая	0	1	2	3	4
1	10	11	12	13	14
2	20	21	22	23	24
3	30	31	32	33	34
4	40	41	42	43	44

Ответ. 20 чисел.

Задача 4. Теперь добавим к предыдущей задаче дополнительное условие. Сколько четных двузначных чисел можно составить из цифр 0,1,2,3,4?

Решение. Посмотрим, что изменится в таблице? Первую цифру в числе можно выбрать столькими же способами, что и в первой задаче (все, кроме нуля). За четность числа отвечает только последняя цифра. А именно: это может быть либо нуль, либо четное число, выбираем из имеющихся в условии, нам подходящие, это: 0,2 и 4. Далее аналогично предыдущей задаче, составляем таблицу и подсчитываем количество получившихся чисел.

Ответ. 12 чисел.

Задача 5. В одной деревне по сложившейся традиции мужчин называют каким-либо из следующих имен: Иван, Петр, Василий и Михаил. Проживают в этой деревне 15 мужчин. Может ли оказаться так, что в деревне нет мужчин с одинаковым именем отчеством?

Решение. Как и в предыдущих задачах составляем таблицу.

отчество имя	Иванович	Петрович	Васильевич	Михайлович
Иван	ИИ	ИП	ИВ	ИМ
Петр	ПИ	ПП	ПВ	ПМ
Василий	ВИ	ВП	ВВ	ВМ
Михаил	МИ	МП	МВ	ММ

Затем подсчитываем, сколько всего может в этой деревни быть различных имен. По таблице видно, что 16. Так как в деревне проживает всего 15 мужчин. То вполне возможно, что у них разные имена.

Ответ. Да, такое может быть.

Задачи на закрепление

Задача 6. В спортивном лагере «Орлёнок» собирались проводить первенство по футболу. Незадолго до начала соревнований к начальнику лагеря пришел вожатый и сказал: «Иван Владимирович! У нас на складе есть шорты и майки только трёх цветов: белого, красного, синего. А команд у нас восемь. Как быть?» «Да совсем просто! - ответил тот.- Ведь необязательно, чтобы майки и шорты были одного цвета. Можно одну команду одеть в синие майки и красные шорты, а другую в красные майки и синие шорты». А хватит ли таких комбинаций на восемь команд?

Ответ. Да, хватит.

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

Ответ. БГ, БК, БС, БП, РГ, РК, РС, РП, - получили восемь разных обедов из двух блюд.

Домашнее задание

Задача 8. На фабрике есть стержни для ручек четырех цветов: красного, синего, зеленого и черного. Сколько различных трехцветных ручек можно при этом собрать?

Ответ. 4 ручки.

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

Ответ. 12 вариантов.

Задача 10. Шерлоку Холмсу нужно открыть сейф, для этого он должен отгадать код. Он знает, что код - это трехзначное число, составленное из цифр 1, 2, 3, 4 и большее числа 400. Какие числа должен проверить Шерлок Холмс, чтобы найти код?

Ответ. 444, 433, 422, 411, 432, 423, 431, 413, 421, 412.

6 класс

Урок 1

Тема урока: «Решение задач с помощью различных методов перебора. Правило умножения»

Изучение новой темы

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

Задача 1. Группа туристов планирует осуществить поход по маршруту Антоново - Борисово - Власово - Грибово. Из Антоново в Борисово можно сплавиться по реке или дойти пешком. Из Борисово во Власово можно пройти пешком или доехать на велосипедах. Из Власово в Грибово можно доплыть по реке, доехать на велосипедах или пройти пешком. Сколько всего вариантов похода могут выбрать туристы?

Ответ. 12 вариантов.

Задача 2. При встрече 8 приятелей обменялись рукопожатиями. Сколько всего было сделано рукопожатий?

Ответ. 28 рукопожатий.

Задача 3. Сколькими способами можно выложить в ряд красный, желтый и зеленый шарики? А если к ним добавить синий шарик? И еще добавить белый?

На первый вопрос учащиеся легко ответят с помощью перебора - 6 способов.

Второй вопрос тоже не должен вызвать затруднений, хотя вариантов уже значительно больше - 24 способа.

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

Во всех предложенных задачах для подсчёта числа комбинаций мы использовали простой способ подсчёта - прямое перечисление (опираясь на «дерево возможных вариантов», таблицу). Но способ перебора возможных вариантов далеко не всегда применим, как, например, в нашей задаче, получается очень большое число всех возможных комбинаций.

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

Правило умножения: Если объект можно выбрать способами, а объект - способами, то пару можно выбрать способами.

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

,

Ответ. 120 способов.

Задача 4. В меню столовой имеется 3 различных первых блюда, 4 различных вторых блюда и 3 напитка. Сколькими способами в этой столовой можно выбрать обед, состоящий из трех блюд?

Решение. Выбор обеда равносилен выбору набора из трех элементов (первое, второе, напиток). По правилу произведения таких наборов будет .

Ответ. Обед можно выбрать 36 способами.

Задачи на закрепление

Задача 5. Сколько всего двузначных чисел? У скольких двузначных чисел все цифры четные? А если все цифры нечетные?

Ответ. Всего 90 чисел, 20 из четных цифр, 25 из нечетных.

Задача 6. Стадион имеет четыре входа: А, В, С и D. Укажите все возможные способы, какими посетитель может войти через один вход, а выйти через другой. Сколько таких способов?

Ответ. 12 способов.

Задача 7. В шахматном турнире участвуют 9 человек. Каждый из них сыграл с каждым по одной партии. Сколько всего партий было сыграно?

Ответ. 36 партий.

Домашнее задание

Задача 8. Сколько различных путей, не проходящих дважды через одну дорогу, ведет из A в D?

АD

Ответ. 32 способа.

Задача 9. Сколько всего пятизначных чисел существует?

Ответ. 90000 чисел.

Урок 2

Тема урока: «Правило сложения»

Изучение новой темы

Рассмотрим следующую задачу.

Задача 1. В меню столовой имеется 3 различных первых блюда, 4 различных вторых и 3 напитка. У Иры было мало денег, и она решила, что купит либо первое, либо второе блюдо, чтобы пообедать. Сколькими способами Ира может купить себе «обед»?

Решение. Так как Ира выбирает блюда либо из множества первых блюд, либо из множества вторых блюд, т.е. она выбирает из объединения этих множеств. Поскольку эти два множества не имеют общих элементов, то возможностей выбора у Иры 3+4=7. Условие про напитки здесь не понадобилось.

Ответ. Ира может купить себе обед 7 способами.

На примере данной задачи сформулируем правило суммы:

Если объект из первого множества можно выбрать способами, а объект из второго множества - способами, то выбор «либо , либо » можно осуществить способами.

Задача 2. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?

Решение. По условию задачи яблоко можно выбрать пятью способами, апельсин - четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу суммы, можно осуществить 5+4=9 способами.

Ответ. 9 способов.

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

Задача 3. Сколько трехзначных чисел можно составить, используя цифры 7, 4 и 5?

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

Ответ. 27 способов.

Правила суммы и произведения - это общие правила решения комбинаторных задач.

Задачи на закрепление

Задача 4. Номер автомашины состоит из трех букв русского алфавита (используется 30 букв) и трех цифр: сначала идет буква, затем три цифры, а затем еще две буквы. Сколько существует различных номеров автомашин?

Ответ. 27000000 номеров.

Задача 5. На глобусе проведены 17 параллелей и 24 меридиана. На сколько частей разделена поверхность глобуса? Меридиан -- это дуга, соединяющая Северный полюс с Южным. Параллель -- это окружность, параллельная экватору (экватор тоже является параллелью).

Ответ. 432 части.

Домашнее задание

Задача 6. Каждую клетку квадратной таблицы 2Ч2 можно покрасить в черный или белый цвет. Сколько существует различных раскрасок этой таблицы?

Ответ. 16 раскрасок.

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

Ответ. 110 способов.

Задача 8. Сколькими способами можно сделать трёхцветный флаг с горизонтальными полосами одинаковой ширины, если имеется материя шести различных цветов?

Ответ. 120 способов.

7 класс

Урок 1

Тема урока: «Комбинаторные задачи. Перестановки. Факториал числа»

Задачи на повторение

Задача 1. В некотором алфавите 10 букв. Сколько 3 _ буквенных “слов” в нем можно составить? Пусть из этих букв 7 гласных и 3 согласных. Сколько можно составить различных слов по модели “согласная _ гласная _ согласная”?

Ответ. 1000слов; 147 слов.

Задача 2. Комбинация из трех букв на автомобильном номере состоит из тех русских, для которых есть похожие латинские, а именно из A, B, E, K, M, H, O, P, C, T, Y, X. Сколько всего таких комбинаций?

А сколько всего автомобильных номеров одного типа (три буквы _ три цифры) можно ввести в области?

Ответ: 1728 комбинаций букв; 1728000 номеров.

Новая тема

Рассмотрим задачу.

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

Даны 3 объекта, нужно составить из них все возможные комбинации, переставляя их между собой. Такие комбинации называются перестановками из элементов.

Итак, перестановкой из элементов называется каждое расположение этих элементов в определённом порядке (т.е. перестановки отличаются друг от друга только порядком расположения элементов)

Для трех элементов мы получим 6 перестановок, т.е.

,

А если объектов 4? , то

А если объектов 5? , то

А если ? То

Это произведение выражает количество перестановок из элементов и обозначают .

,

Произведение всех натуральных чисел от 1 до n, т.е.

обозначают n! (читают эн факториал)

Некоторые значения n! приведем с следующей таблице:

по определению!

Следовательно, число перестановок предметов равно

Рассмотрим следующие задачи.

Задача 3. Сколькими способами можно расставить 8 участниц финального забега на 8 беговых дорожках?

Решение. Число способов равно числу перестановок из 8 элементов. По формуле числа перестановок находим, что . Значит, существует 40 320 способов расстановки участниц забега на 8 беговых дорожках.

Ответ. 40320 способов.

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

Решение. Из цифр 0, 2, 4, 6 можно получить перестановок. Из них надо исключить те перестановки, которые начинаются с 0, так как натуральное число не может начинаться с цифры 0. Число таких перестановок равно . Значит, искомое число четырехзначных чисел равно .

Ответ. 18 чисел.

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

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

Ответ. 17280 способов.

Задачи на закрепление

Задача 6. Сколько среди четырехзначных чисел, составленных из цифр 3, 5, 7, 9 (без их повторения), таких, которые: а) начинаются с цифры 3; б) кратны 15?

Ответ. а) 6 чисел; б) 6 чисел.

Задача 7. Семь мальчиков, в число которых входят Олег и Игорь, становятся в ряд. Найдите число возможных комбинаций, если:

а) Олег должен находиться в конце ряда;

б) Олег должен находиться в начале ряда, а Игорь -- в конце ряда;

в) Олег и Игорь должны стоять рядом.

Ответ. а) 720; б) 120; в) 1 440 комбинаций.

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

Задача 8. Сколько шестизначных чисел, в записи которых каждая цифра используется только один раз, можно составить из цифр: 0, 2, 5, 6, 7,8?

Решение. Дано 6 цифр 0, 2, 5, 6, 7, 8, из них нужно составить различные шестизначные числа. Отличие от предыдущей задачи состоит в том, что 0 не может стоять на первом месте.

Можно напрямую применить правило произведения на первое место можно выбрать любую из 5 цифр (кроме нуля); на второе-любую из пяти оставшихся цифр ( 4 «нулевые» и теперь считаем ноль); на третье место- любую из 4 оставшихся после двух первых выборов цифр, и т. д. Общее количество вариантов равно:

Можно применить метод исключения лишних вариантов. 6 цифр можно переставить = 6!=720 различными способами. Среди этих способов будут и такие, в которых на первом месте стоит ноль, что не допустимо. Подсчитаем количество этих недопустимых вариантов. Если на первом месте стоит ноль (он фиксирован), то на последующих пяти местах могут стоять в произвольном порядке «ненулевые» цифры 2, 5, 6, 7, 8. Количество разных способов, которыми можно разместить 5 цифр на пяти местах, равно =5!=120, т. е. количество перестановок чисел, начинающихся с нуля, равно120.

Искомое количество различных шестизначных чисел в этом случае равно: = 720 - 120 = 600.

Ответ: 600 чисел.

Домашнее задание.

Задача 9. Сколькими способами 9 человек могут, встать в очередь в театральную кассу?

Ответ. 362 880 способов.

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

б) 0, 2, 5, 6, 7, 8?

Ответ. 600 чисел.

Задача 11. Сколько чисел можно составить из цифр 1, 2, 3, 4 (без их повторения), таких, которые больше 3000?

Ответ. 12 чисел.

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

Ответ. 240 способов.

Урок 2

Тема урока: «Комбинаторные задачи. Размещения»

Новая тема

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

Сколько трехзначных чисел можно составить из цифр 1,3,5, используя в записи числа каждую из них не более одного раза? (3!=6)

Рассмотрим такую задачу.

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

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

Итак, размещением из n элементов по k (k ? n) называется любое множество, состоящее из k элементов, взятых в определённом порядке из данных n элементов.

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

Число размещений вычисляется по формуле:

Заметим, что при к=n, размещения становятся перестановками.

Рассмотрим следующие задачи.

Задача 1. Учащиеся 8 класса изучают 9 предметов. Сколькими способами можно составить расписание уроков на один день, так чтобы в этот день было 6 различных уроков?

Решение. Нам надо выбрать из 9 предметов 6 и каким-то образом их упорядочить. Т.е. в этой задаче имеем дело с 6-размещениями из 9 элементов. Считаем их количество по формуле

Ответ. Расписание на день можно составить 60480 способами.

Задача 2. Учащиеся 2 класса изучают 9 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета?

Решение. Любое расписание на один день, составленное из 4 различных предметов, отличается от другого либо набором предметов, либо порядком их следования. Значит, в этом примере речь идет о размещениях из 9 элементов по 4. Получили:

Ответ: 3024 способами.

Задачи на закрепление

Задача 3. В конкурсе принимают участие 20 человек. Сколькими способами можно присудить первую, вторую и третью премии?

Ответ. 6840 способов.

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

Ответ. 657720 способов.

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

Ответ: 840 способов.

Задача 6. Сколькими способами могут сесть в автомобиль 5 человек, каждый из которых может быть водителем? А если водительские права имеют только двое?

Ответ. 120 способов; 48 способов.

Задача 7. Сколькими способами можно представить число 28 в виде произведения а) двух множителей; б) трех множителей, если разложения, отличающиеся порядком множителей, считаются одинаковыми?

Ответ. 6 способов; 18 способов.

Домашнее задание

Задача 8. На странице альбома 6 свободных мест для фотографий. Сколькими способами можно вложить в свободные места:

а) 2 фотографии; б) 4 фотографии?

Ответ. 30 способов; 360 способов.

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

Ответ. 544 320 телефонных номеров.

Задача 10. Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр: а) 1, 3, 5, 7, 9; б) 0, 2, 4, 6, 8?

Ответ. а) 120 чисел; б) 96 чисел.

Спецкурс

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

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

Занятие 1

Задача 1. Сколько существует целых чисел от 0 до 999999, в десятичной записи которых нет двух стоящих рядом одинаковых цифр?

Решение. В данных пределах у нас существуют однозначные, двузначные, трехзначные, четырех-, пяти- и шестизначные числа. Будем рассматривать их количество по отдельности.

Однозначные: таких чисел 10, от 0 до 9 включительно.

Двузначные: на первое место мы можем выбрать цифру девятью способами (двузначное число не может начинаться с нуля); на второе место можно поставить любую цифру, кроме той, которая стоит на первом месте, таких цифр 9. Получается, по правилу умножения, что двузначное число мы можем составить 9 9 = 81 способами.

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

Остальные числа составляются аналогично.

Четырехзначные: .

Пятизначные: .

Шестизначные: .

В итоге, количество всех чисел от 0 до 999999 мы можем узнать, сложив все получившиеся числа вместе:

10 + 81 + 729 + 6561 + 59049 + 531441 = 597871 число.

Ответ. 597871 число.

Задача 2. Сколькими способами можно разбить 14 человек на пары?

Решение. Возьмем одного человека, сколькими способами мы можем выбрать ему пару? 13 способами.

Рассуждаем далее, после выбора первой пары осталось 12 человек. Аналогично, берем любого человека, сколькими способами мы можем выбрать пару ему? 11 способами.

И так далее, по правилу произведения получили, что всего способов разбить 14 человек на пары:

.

Ответ. 135135 способов.

Задача 3. Сколькими способами из полной колоды (52 карты) можно выбрать 4 карты разных мастей и достоинств?

Решение. Колода в 52 карты состоит из 4 мастей по 13 карт в каждой. 13 карт одной масти, в свою очередь, различаются, по так называемому достоинству карты. Так вот, выбираем сначала карту какой-нибудь одной масти, например, бубны. Так как в колоде 13 карт бубновой масти, то и выбрать ее мы можем 13 способами.

Далее, берем вторую масть, например, крести. Карт крестовой масти в колоде так же 13, но мы не можем, по условию задачи, выбрать карту тем же достоинством, что и бубновую. Поэтому, получается, что способов вытянуть крестовую карту у нас остается 12.

Аналогично, карту третьей масти мы можем вытянуть 11 способами, а четвертой - 10 способами.

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

способами.

Ответ. 17160 способов.

Задача 4. Найдите сумму всех трехзначных чисел, которые можно записать с помощью цифр 1, 2, 3, 4 (цифры могут повторяться).

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

Сначала посмотрим сколько раз в разряде, ну допустим, единиц встречается цифра 1. По сути, нам нужно закрепить 1 на последнем месте в трехзначном числе и подсчитать, сколько существует двузначных чисел, состоящих из цифр 1, 2, 3 и 4, при условии, что цифры могут повторяться. Такую задачу легко решить с помощью таблицы:

единицы десятки	1	2	3	4
1	11	12	13	41
2	21	22	23	42
3	31	32	33	43
4	41	42	43	44

Из таблицы видно, что существует 16 таких чисел.

Нетрудно догадаться, что если мы закрепим на месте единиц 2, 3 или 4, то количество чисел тоже будет равно 16. Так же дело обстоит, если мы будем закреплять числа в разряде десяток или сотен.

Рассмотрим разряд единиц, с остальными разрядами будет точно так же:

Получили, что с «1» - 16 чисел; с «2» - 16; «3» - 16 и с «4» - 16, их сумма:

В разряде десяток действуем аналогично, только, так как мы работаем с десятками, нужно умножить полученное число на 10, получили:

160 10 = 1600.

В разряде сотен: 16000.

Таким образом, сумма всех трехзначных чисел, записанных с помощью цифр 12,3 и 4 равна:

160 + 1600 + 16000 = 17760

Ответ. 17760.

Занятие 2

Задача 1. Фабрика игрушек выпускает проволочные кубики, в вершинах которых расположены маленькие разноцветные шарики. По ГОСТу в каждом кубике должны быть использованы шарики всех восьми цветов (белого и семи цветов радуги). Сколько разных моделей кубиков может выпускать фабрика?

Решение. У кубика 8 вершин и 6 граней. Зафиксируем его, т.е. поставим на одну из граней. Поместить 8 разных шариков в его вершины можно 8! способами. Но кубик можно поворачивать: каждую из шести его граней можно сделать нижней - это 6 способов расстановки, в свою очередь, когда кубик стоит на одной из граней, его можно и повернуть 4 способами. Поэтому, по правилу произведения, каждому кубику соответствует 6·4 = 24 способа раскраски. Тогда получается, что общее число моделей равно .

Ответ. 1680 моделей.

Задача 2. За круглым столом были приготовлены 12 мест для жюри с указанием имени на каждом месте. Николай Николаевич, пришедший первым, по рассеянности сел не на своё, а на следующее по часовой стрелке место. Каждый член жюри, подходивший к столу после этого, занимал своё место или, если оно уже было занято, шёл вокруг стола по часовой стрелке и садился на первое свободное место. Возникшее расположение членов жюри зависит от того, в каком порядке они подходили к столу. Сколько может возникнуть различных способов рассадки жюри?

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

Первым из невезучих (не считая Николая Николаевича) к столу должен был подойти тот, чье место занято Николаем Николаевичем, иначе он занял бы свое место. Он занял место следующего (по часовой стрелке) невезучего члена жюри. Вторым из невезучих должен был подойти тот, чьё место занято первым невезучим (по той же причине), и т.д. Итак, каждый невезучий садится на следующее "невезучее" место за его собственным.

Таким образом, способ рассадки однозначно задаётся способом разбиения жюри на везучих и невезучих.

Николай Николаевич и тот, чьё место он занял, в любом случае являются невезучими. Любой набор членов жюри, не содержащий этих двоих, может быть множеством везучих. Реализовать такой способ рассадки можно, например, так: вслед за Николаем Николаевичем входят все, кого мы выбрали везучими (в любом порядке), а затем все остальные в порядке их рассадки за столом по часовой стрелке. Поэтому количество способов рассадки равно количеству подмножеств множества из 10 человек, то есть 2¹⁰ = 1024.

Ответ. 1024 способа.

Задача 3.Найдите сумму всех семизначных чисел, которые можно получить всевозможными перестановками цифр 1, ..., 7.

Решение. Найдем сначала сумму цифр разряда единиц. Каждая цифра от 1 до 7 входит (в качестве цифры единиц) в 6! чисел, значит, эта сумма равна 6!·(1 + 2 + ... + 7) = 28·6!. То же верно и для остальных разрядов.

Ответ. 28·6!·1111111.

Задача 4. Рассматривается доска 8Ч8, клетки которой пока не окрашены. Сколькими способами можно раскрасить доску в чёрный и белый цвета так, чтобы чёрных клеток было 31 и никакие две чёрные клетки не имели общей стороны? (Два способа раскраски считаются различными, если найдется клетка, которая при одном из этих способах раскраски белая, а при другом - чёрная.)

Решение. Разобьём доску на 16 квадратиков 2Ч2. Ясно, что один из квадратиков - особый, в нем только одна чёрная клетка, а в остальных пятнадцати - по две, причём в противоположных углах. Раскраска неособого квадратика однозначно продолжается на соседний (по стороне) неособый квадратик и, тем самым, на все неособые квадратики. Без особого квадратика получается шахматная (или противоположная ей по раскраске) доска с дыркой. Если дырка находится в левом верхнем, как на рисунке, или правом нижнем углу шахматной доски, то закрасить в ней одну клетку чёрным можно тремя способами, а в остальных случаях - только двумя. Итак, из шахматной доски можно получить 16·2 + 2 = 34 раскраски, а из противоположной ей - столько же.

Ответ: 68 способами.

8 класс

Урок 1

Тема урока: «Комбинаторные задачи. Перестановки. Размещения»

Новая тема

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

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

?

Умножим и разделим данное выражение на , получим

?

Итак, получили, что число размещений множества из элементов по элементов равно:

?

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

Решение. Искомое число трехполосных флагов:

?

Ответ. 60 флагов.

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

?

Таким образом, получили, что число всех различных перестановок вычисляется по формуле:

?

Задача 2. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?

Решение. Искомое число расстановки 8 ладей

?

Ответ. 40320 способов.

Задачи на закрепление

Задача 3. Семнадцать девушек водят хоровод. Сколькими различными способами они могут встать в круг?

Решение. Зафиксируем одно из мест в круге. Всегда можно повернуть круг так, чтобы на этом месте оказалась первая девушка. Остальные 16 девушек могут расположиться по оставшимся 16 местам, а это и есть перестановка 16 элементов:

Ответ. 16! Способам

Задача 4. а) Сколькими способами 28 учеников могут выстроиться в очередь в столовую? б) Как изменится это число, если Петю Иванова и Колю Васина нельзя ставить друг за другом?

Решение. а)

б) Временно уберем из очереди Колю. Оставшихся учеников можно расставить 27! способами, но два из них - перед Петей и после него - запрещены, т.е. у Коли остается только 26 способов встать в очередь.

Ответ. а) 28!; б) 26·27!

Задача 5. Слово - любая конечная последовательность букв русского алфавита. Выясните, сколько различных слов можно составить из слов:

а) "ВЕКТОР"; б) "ЛИНИЯ"; в) "БИССЕКТРИСА".

Решение. а) Так как все буквы слова различны, то всего можно получить 6! =720 слов.

б) В этом слове две буквы И, а все остальные буквы разные. Временно будем считать разными и буквы И, обозначив их через И₁ и И₂. При этом предположении получится 5! = 120 разных слов. Однако те слова, которые получаются друг из друга перестановкой букв И₁ и И₂, на самом деле одинаковы. Таким образом, полученные 120 слов, разбиваются на пары одинаковых. Поэтому разных слов всего 120: 2 = 60.

в) В этом слове три буквы С и две буквы И. Считая все буквы различными, получаем 11! слов. Отождествляя слова, отличающиеся лишь перестановкой букв И, но не С, получаем слов. Отождествляя теперь слова, отличающиеся перестановкой букв С, получаем окончательный результат .

Ответ. а) 720; б) 60; в) 3326400 слов.

Домашнее задание

Задача 6. Анаграммой называется произвольное слово, полученное из данного слова перестановкой букв. Сколько анаграмм можно составить из слов: а)"точка"; б)"прямая"; в)"перешеек"; г)"биссектриса"; д)"абракадабра"; е)"комбинаторика"?

Ответ. а) 5! = 120; б) 6!: 2 = 360; в) 8!: 4! = 1680; г) 11!: (2!·3!) = 3326400; д) 11!: (5!·2·2) = 83160; е) 13!: 2⁴ анаграмм.

Задача 7. Сколько существует различных возможностей рассадить 5 юношей и 5 девушек за круглый стол с 10 креслами так, чтобы они чередовались?

Ответ. 2·5!5! = 28800 возможностей.

Урок 2

Тема урока: «Комбинаторные задачи. Сочетания»

Новая тема

Посмотрим в чем сходство и различие следующих задач:

· Сколькими способами можно выбрать из класса в 20 человек разведчика, связиста и сапера для игры «Зарница».

· Сколькими способами можно выбрать трех учеников для игры «Зарница»?

В обеих задачах нужно выбрать 3 человек из 20, только в первой задаче нам важно, кто именно из троих выбранных учащихся, будет разведчиком, кто связистом, а кто сапером, а во второй - нет. То есть во второй задаче нам не важно расположение элементов.

Комбинации, которые составлены из данных элементов по элементов и отличаются хотя бы одним элементом, называются сочетаниями из различных элементов по элементов.

В сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из элементов по элементов в каждом обозначается (от начальной буквы французского слова “combinasion”, что значит “сочетание”).

Формула числа сочетаний получается из уже доказанной нами формулы числа размещений.

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

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

отсюда получили, что

?

Свойства чисел

Для числа сочетаний выполняются следующие свойства.

1.

2.

3.

Задача 1. Четыре человека сыграли друг с другом по одной партии в шахматы. Сколько было сыграно партий?

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

?

Ответ. 6 партий.

Рассмотрим несколько задач.

Задача 2. Из набора, состоящего из 15 красок, надо выбрать 3 краски для окрашивания шкатулки. Сколькими способами можно сделать этот выбор?

Ответ. 455 способов.

Задача 3. В классе учатся 12 мальчиков и 10 девочек. Для уборки территории около школы требуется выделить трех мальчиков и двух девочек. Сколькими способами это можно сделать?

Решение: Выбрать трех мальчиков из 12 можно способами, а двух девочек из 10 можно выбрать способами. Сделать выбор учащихся можно:

способами.

Ответ. 9900 способов.

Задачи на закрепление

Задача 4. Из лаборатории, в которой работают заведующий и 10 сотрудников, надо отправить 5 человек в командировку. Сколькими способами это можно сделать, если:

а) заведующий лабораторией должен ехать в командировку;

б) заведующий лабораторией должен остаться?

Ответ. а) 210 способов; б) 252 способа.

Задача 5. Бригада, занимающаяся ремонтом школы, состоит из 12 маляров и 5 плотников. Из них для ремонта физкультурного зала надо выделить 4 маляра и 2 плотника. Сколькими способами можно это сделать?

Ответ. способов.

Задача 6. Сколькими способами в команде из 4 человек можно выбрать а) капитана и заместителя; б) двоих дежурных?

Ответ. а) 12способов; б) 6 способов.

Домашнее задание.

Задача 7. Сколькими способами можно выбрать из 5 человек а) по одному человеку для участия в соревнованиях по волейболу, баскетболу, плаванию; б) 3-х участников для участия в зимней спартакиаде?

Ответ. а) 20 способов; б) 10 способов.

Задача 8. На плоскости отмечено восемь точек, никакие три из которых не лежат на одной прямой. Сколько прямых можно провести через эти точки?

Ответ. прямых.

Задача 9. В библиотеке читателю предложили на выбор из новых поступлений 10 книг и 4 журнала. Сколькими способами он может выбрать из них 3 книги и 2 журнала?

Ответ. 720 способов.

Урок 3

Тема урока: «Перестановки, размещения и сочетания»

Сегодня у нас будет урок обобщения. Будем решать задачи на применение формул размещения, перестановки и сочетания элементов. Вашей задачей будет правильно определить вид комбинаций и воспользоваться соответствующей формулой при решении задачи.

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

Решение задач

Определить, на какое понятие задача: перестановка, размещение или сочетание и решите задачу.

Задача 1. Сколько существует перестановок букв слова «конус», в которых буквы «к», «о», «н» стоят рядом в указанном порядке?

Решение. Буквы «к», «о», «н» стоят рядом в указанном порядке, поэтому конструкцию «кон» можно считать одной буквой. Значит нужно найти количество перестановок из трех элементов: = 3! = 6

Ответ: 6 перестановок.

Задача 2.Сколько можно составить из цифр 1, 2, 3, 4, 5 (без их повторения) различных трехзначных чисел, которые являются:

а) четными; б) кратными 5?

Решение. Выбираем 3 цифры из 5 данных, причем:

а) последней цифрой должна быть 2 или 4. Количество вариантов:

(фиксирована 2) + (фиксирована 4) = 243= 24 числа.

б) последней цифрой должна быть 5. Количество вариантов:

(фиксирована 5) = 4 3 = 12 чисел.

Ответ. а) 24 числа; б) 12 чисел.

Задача 3. На полке стоит 12 книг: англо-русский словарь и 11 художественных произведений на английском языке. Сколькими способами читатель может выбрать 3 книги, если:

а) словарь нужен ему обязательно;

б) словарь ему не нужен?

Решение. Выбираем 3 книги из 12. Порядок не имеет значения.

а) Словарь выбирается; нужно выбрать еще 2 книги из 11:

55 способов.

б) Словарь не выбирается; выбираем 3 книги из 11:

165 способов.

Ответ. а) 55 способов; б) 165 способов.

Задача 4. Сколькими способами можно расставить на полке 12 книг, из которых 5 книг -- это сборники стихов, так, чтобы сборники стихов стояли рядом в произвольном порядке?

Решение. Из 12 элементов 5 элементов можно «склеить» = 5!= 120 различными способами.

Число различных перестановок из 8 элементов (7 элементов + «склейка») равно =8!=40 320.

Общее число способов расставить12 книг, из которых 5 книг должны стоять рядом, равно 120 40 320=4 838 400.

Ответ. 4 838 400 способов.

Задача 5. В классе учатся 16 мальчиков и 12 девочек. Для уборки территории требуется 4 мальчика и 3 девочки. Сколькими способами это можно сделать?

Решение:

Нужно сделать два выбора: 4 мальчиков из 16 (всего способов) и 3 девочек из 12 (всего способов). Порядок выбора значения не имеет (все идущие на уборку равноправны). Каждый вариант выбора мальчиков может сочетаться с каждым выбором девочек, поэтому по правилу произведения общее число способов выбору равно:

Ответ. 400400 способов.

Задача 6. Бригада, занимающаяся ремонтом школы, состоит из 12 маляров и 5 плотников. Из них для ремонта физкультурного зала надо выделить 4 маляра и 2 плотника. Сколькими способами можно это сделать?

Ответ. способов.

Задача 7. Сколькими способами 5 мальчиков и 5 девочек могут занять в театре в одном ряду места с 1-го по 10-е, если мальчики будут сидеть на нечетных местах, а девочки -- на четных?

Ответ. 14 400 способов.

Задача 8. Сколькими способами четыре пассажира: Алексеев, Смирнов, Федоров и Харитонов - могут разместиться в девяти вагонах поезда, если Алексеев и Смирнов хотят ехать в одном вагоне, а Федоров и Харитонов - в других вагонах, причем различных?

Ответ. 504 способа.

Урок 4

Контрольная работа

Вариант 1

2. Сколькими способами 7 человек могут занять очередь в железнодорожную кассу?

3. На совещании присутствовали 15 представителей разных компаний. Все они обменялись визитками. Сколько визиток было использовано?

4. Вычислить (6! - 4!): 5!

5. Из класса, в котором учится 23 человек, необходимо послать на школьную конференцию четырех представителей. Сколько вариантов такого выбора?

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

7. Сколько существует пятизначных телефонных номеров, составленных из цифр 0,1, 2, 3, 5, 7, 9 если в номере нет повторяющихся цифр и:

- номер не может начинаться с 0?

- на первом и последнем месте стоят цифры 1 и 9?

- цифры 5 и 7 стоят рядом?

8. Составьте выражение для решения задачи. В спец. роте 75 солдат, пять офицеров и восемь сержантов. Необходимо выделить на охрану объектов восемь солдат, двоих сержантов и одного офицера. Сколько существует вариантов создать наряд?

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

Вариант 2

1. Сколькими вариантов расписания уроков возможно составить, если в этот день будут уроки: математика, физика, информатика, литература, физкультура, биология, география?

2. В классе 25 человек. На выпускном вечере они обменялись своими фотографиями. Сколько фотокарточек было использовано?

3. Вычислить (7! - 5!): 6!

4. Из бригады, состоящей из 21 человека, необходимо послать на профсоюзную конференцию трех человек. Сколько вариантов такого выбора?

5. Сколькими способами можно разделить группу дежурных из 17 учащихся, так чтобы шесть человек направить в столовую, а остальных - следить за порядком в коридорах?

6. Сколько существует пятизначных кодов, составленных из цифр 0,1, 2, 3 и букв А, В, С, если в коде нет повторяющихся знаков и:

- код не может начинаться с 0?

- на первом и последнем месте стоят буквы А и С?

- цифры 1 и 3 стоят рядом?

7. Составьте выражение для решения задачи. В спец. роте 68 солдат, шесть офицеров и семь сержантов. Необходимо выделить на охрану объектов 11солдат, трех сержантов и двух офицеров. Сколько существует вариантов создать наряд?

8. В шахматном клубе университета занимались девять шахматистов 1 разряда и шесть шахматистов 2 разряда. Для участия в соревнованиях необходимо выставить команду из трех человек 1-ого разряда на 1-ю, 2-ю, и 3-ю доску и двух человек 2-го разряда на 4-ю и 5-ю доску. Сколько существует вариантов составить команду?

Спецкурс

Занятие 1

Задача 1. На прямой отмечено 10 точек, а на параллельной ей прямой - 11 точек. Сколько существует а) треугольников; б) четырехугольников с вершинами в этих точках?

Решение. а) Две вершины треугольника должны лежать на одной прямой, а одна - на другой: треугольников;

б) Две вершины четырехугольника лежат на одной стороне, а оставшиеся две на другой: четырехугольников.

Ответ. а)1045 треугольников; б)2475 четырехугольников.

Задача 2. Сколькими способами можно разбить 10 человек на две баскетбольные команды по 5 человек в каждой?

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

Ответ. 126 способами.

Задача 3. Сколькими способами можно выложить в ряд 5 красных, 5 синих и 5 зеленых шаров так, чтобы никакие два синих шара не лежали рядом?

Решение. Сначала разложим красные и зеленые шары. Для этого надо выбрать 5 мест из 10 для красных шаров. Между ними (а также слева и справа) остается 11 мест, куда можно ставить синие шары. Из этих мест надо выбрать 5.

Ответ: способами.

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

Решение. Чтобы задать параллелограмм, надо выбрать по две прямые из каждого ряда параллельных. Надо учесть, что в ряду m + 2 прямые: добавляются стороны исходного параллелограмма.

Ответ:

Задача 5. Имеется куб размером 10Ч10Ч10, состоящий из маленьких единичных кубиков. В центре O одного из угловых кубиков сидит кузнечик. Он может прыгать в центр кубика, имеющего общую грань с тем, в котором кузнечик находится в данный момент; причем так, чтобы расстояние до точки O увеличивалось. Сколькими способами кузнечик может допрыгать до кубика, противоположного исходному?