Классы
Предметы

Решение более сложных задач по комбинаторике

Этот видеоурок доступен по абонементу
Подробнее об абонементе, платных и бесплатных уроках

У вас уже есть абонемент? Войти

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

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

Задача 1

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

Решение

Рассмотрим два случая:

1. В комиссии будет один математик.

Существует 2 способа выбрать 1 математика из 2. Из 10 экономистов нужно выбрать 9 человек; количество способов выбрать из 10 человек 9 – это . Следовательно, всего способов:

 

Однако можно посчитать иначе: выбирать не 9 экономистов из 10, а выбрать 1 экономиста из 10, который не попадет в комиссию, то есть:

 

2. В комиссии будет более одного математика, то есть 2.

Существует 1 способ выбрать 2 математиков из 2. Оставшиеся восемь человек комиссии должны быть экономистами. Количество способов выбрать 10 человек 8 – это . Следовательно, всего способов:

3. Складываем количество способов в первом и во втором случае:

 

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

Задача 2

Сколько есть способов составить ожерелье из 5 одинаковых красных бусинок и 2 одинаковых синих бусинок?

Решение

Ожерелье может быть замкнутым и незамкнутым.

1. Если ожерелье замкнутое, то между синими бусинками может находиться или 0, или 1, или 2 красных бусинок (если между синими находятся 3, 4 или 5 красных, то это тоже самое, что и 0, 1, 2, только с другой стороны) (см. Рис. 1). Следовательно, существует три варианта расположения 2 синих и 5 красных бусинок на замкнутом ожерелье.

Рис. 1. Иллюстрация к задаче

2. Если ожерелье незамкнутое (см. Рис. 2), тогда количество вариантов определяется также положением синих бусинок. Количество способов выбрать 2 места из 7 – это .

Рис. 2. Иллюстрация к задаче

Ответ: 1. Если ожерелье замкнутое, то существует три способа составить ожерелье; 2. Если ожерелье незамкнутое, то существует 21 способ составить ожерелье.

Задача 3

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

Рис. 3. Иллюстрация к задаче

Решение

Движение водителя задается последовательностью движений вправо (П) и вверх (В). Например: если водитель использует схему движения, показанную на рисунке 4, то он 10 раз (10 клеточек) едет вправо (П), а затем 5 раз (5 клеточек) вверх (В):

Рис. 4. Иллюстрация к задаче

Если водитель использует схему движения, показанную на рисунке 5, то он едет 1 раз вверх (В), 1 раз вправо (П), 1 раз В, 1 П, 1 В, 1 П, 1 В, 1 П, 1 В, 6 П:

Рис. 5. Иллюстрация к задаче

Таким образом, каждый маршрут водителя задается последовательностью из 15 символов В и П, при этом водитель каждый раз смещается на 10 единиц вправо и на 5 единиц вверх. Следовательно, из 15 символов 5 будут символами В, а 10 будут символами (П). Поэтому для решения задачи необходимо найти количество способов выбрать 5 мест из 15, в которых водитель поедет вверх. Это будет .

Ответ:  маршрутов.

Задача 4

Даны 2 слова: «интегрирование» и «суперкомпьютер». Вася посчитал, сколько получается слов из слова «интегрирование», если вычеркнуть в нем 2 произвольные буквы (получившиеся слова не обязательно осмысленные). Маша сделала то же самое для слова «суперкомпьютер». У кого слов получилось больше?

Решение

В данных словах одинаковое количество букв (по 14), поэтому вычеркнуть две буквы из каждого из них можно одинаковым количеством способов. Заметим, что при вычеркивании двух букв из слова «суперкомпьютер» все полученные слова будут различны, а при вычеркивании букв РИ и ИР из слова «интегрирование» получается одно и то же слово «интегрование». Поэтому, у Маши получится на одно слово больше.

Количество способов выбрать 2 буквы из 14 – это , именно столько слов будет у Маши, а у Васи будет  слов.

Ответ: больше слов получилось у Маши.

Задача 5

Сколько существует способов рассадить за круглый стол 5 юношей и 5 девушек так, чтобы они чередовались?

Решение

На рисунке 6 изображен стол, на котором для удобства пронумерованы места.

Рис. 6. Иллюстрация к задаче

Предположим, что на месте номер 1 сидит юноша. Тогда все юноши садятся через 1 от этого места (на нечетные места), а девушки – на четные. Количество способов усадить 5 юношей на 5 кресел (количество перестановок) – это , количество способов усадить 5 девушек на 5 кресел – это также . Значит, всего вариантов усадить юношей и девушек – это . Однако на месте номер 1 может сидеть девушка (на четных – юноши, на нечетных – девушки), тогда окончательный ответ будет в два раза больше, то есть .

 

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

Задача 6

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

Доказательство

Докажем от противного.

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

Рис. 7. Иллюстрация к задаче

Следовательно, отсутствует авиалиния  и еще 18 авиалиний, которые связывают другие города либо с городом , либо с городом , то есть всего отсутствует 19 авиалиний.

В стране 20 городов, следовательно, всего теоретически возможно провести  авиалиний.

Тогда если из 190 возможных авиалиний 19 отсутствуют, то присутствует всего:

 авиалиния

Однако это противоречит условию:

 

Следовательно, исходное предположение неверно, а из любого города можно попасть в любой.

 


Пример

Задача 7

Дано слово «логарифм». Сколько существует способов поменять местами буквы в этом слове так, чтобы в полученном буквосочетании согласные были упорядочены по алфавиту слева направо?

Решение

Например, нам подойдут следующие буквосочетания: ОАИГЛМРФ или ГОАЛИМРФ, или ГЛМАИРОФ. В каждом буквосочетании согласные идут в определенном порядке по алфавиту (ГЛМРФ), следовательно, общее количество вариантов таких буквосочетаний определяется только 3 гласными. Поэтому достаточно определить 3 места из 8 для гласных, после чего все буквы расставляются однозначно. А это будет  способов.

 

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

 

Список литературы

1. Мордкович А.Г. Алгебра и начала математического анализа 10-11 кл. В. 2 ч. Ч. 1: Учебник для общеобразоват. учреждений. – М.: Мнемозина, 2009.

2. Муравин Г.К., Муравина О.В. Алгебра и начала математического анализа. – М.: Дрофа. 

3. М.И. Шабунин, А.А. Прокофьев, Т.А. Олейник, Т.В. Соколова. Алгебра. Начала математического анализа. Профильный уровень: задачник для 10-11 классов. – М.: БИНОМ. Лаборатория знаний, 2009.

4. Мордкович А.Г. Алгебра и начала анализа 10-11 кл. В. 2 ч. Ч. 2: Задачник для общеобразоват. учреждений. – М.: Мнемозина, 2009.

 

Дополнительные рекомендованные ссылки на ресурсы сети Интернет

1.  Интернет-сайт «Математический тандем» (Источник)

2. Интернет-сайт YouTube (Источник)

3. Интернет-сайт «МатБюро» (Источник)

 

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

1. Глава 20, задания 56, 67, 82 (стр. 382–386) – М.И. Шабунин, А.А. Прокофьев, Т.А. Олейник, Т.В. Соколова. Алгебра. Начала математического анализа. (Источник).

2. У Васи дома живут 4 кота.

а) сколькими способами можно рассадить котов по углам комнаты?
б) сколькими способами можно отпустить гулять котов?
в) сколькими способами Вася может взять на руки двух котов (одного на левую, другого на правую)?

3. Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?

4. Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно выбрать двух человек одного пола?