Конспект урока по Алгебре «КОМБИНАТОРНЫЕ ЗАДАЧИ» 9-10 класс

Пример. Из 10 роз и 8 георгинов нужно составить букет так, чтобы в нем было 2 розы и 3 георги­на. Сколькими способами это можно сделать?

Решение: выберем сначала из 10 роз 2 розы. Это можно осуществить способами. Мы исполь­зуем сочетания, а не размещения, потому что порядок, в котором выбираются цветы, значения не имеет. Независимо от выбора роз 3 георгина из 8 можно взять способами. Тогда, по правилу произведения, 2 розы и 3 георгина можно выбрать способами:

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

Пример. Сколькими способами можно расставить 8 томов энциклопедии на книжной полке так, чтобы первый и второй тома:
а) стояли рядом;
б) не стояли рядом?
Решение:

а) подсчитаем сначала число вариантов расстановки, когда первый и второй тома стоят рядом. Их можно считать за одну книгу. Тогда получается Р₇ = 7! перестановок. Но первый и второй тома можно соединить двумя спо­собами: слева первый, справа второй том и наоборот. За счет этого количество вариантов уд­ваивается и всего их будет 2·7! = 10080.

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

Итак, 8! — 10080 = 30240. Ответ: а)10080; б) 30240.

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

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

3.2. Перестановки с повторениями

состоящая из n элементов, причем, элемент а повторяется m₁ раз, элемент b – m₂ раз, и т.д., элемент с – m_k раз и m₁ + m₂ +…+ m_k = n. Перестановки в такой выборке, где есть одинаковые элементы, называются перестановками с повторениями и число перестановок с повторениями обозначается P_n(m₁, m₂,….,m_k). Из приведенных выше рассуждений следует формула:

Пример. У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течение девяти дней она выдает сыну по одному фрукту. Сколько может быть вариантов такой выдачи?

Решение: обозначая фрукты по первым буквам названия, составим несколько вариантов вы­дачи: ЯЯГГГАААА, ААГГЯГААЯ, ГГГААЯЯАА. Эти выборки имеют один и тот же состав и отличаются только перестановкой элементов, поэтому применяем формулу числа перестановок с повторениями: . Ответ: 1260 вариантов.

Определение: размещениями с повторениями из n по m называются упорядоченные m-эле­ментные выборки, в которых элементы могут повторяться.

Число размещений с повторениями из n по m обозначается . В отличие от обычных размеще­ний, где mn, в размещениях с повторениями m и n могут быть любыми. Получим формулу числа размещений с повторениями (m-элементная выборка из n элементов). Применяя правило произведения, по­лучим: .   

Пример. Вдоль дороги стоят 6 светофоров. Сколько может быть различных комбинаций их сигналов, если каждый светофор имеет 3 состояния: «красный», «желтый», «зеленый»?

Сделаем проверку и выпишем все варианты покупки: ББББББ, БББББЧ, ББББЧЧ, БББЧЧЧ, ББЧЧЧЧ, БЧЧЧЧЧ, ЧЧЧЧЧЧ. Их действительно 7. Ответ: 7 вариантов.

3.5. Схема определения вида комбинации

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

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

Решение: обозначив игрушки первыми буквами названия, составим несколько комбинаций: КЧЧЧЧЧЧЧК, ЧЧЧКЧКЧЧЧ, ККЧЧЧЧЧЧЧ, … Повторяются ли элементы в выборке? Да. Меня­ется ли состав? Нет, ведь каждая выборка состоит из семи букв «Ч» и двух букв «К». Следова­тельно, это перестановки с повторениями: . Ответ: 36 способами.

Задача №2. Имеются в неограниченном количестве палочки длиной 5,6,7,8,9,10 сантиметров. Сколько различных треугольников можно из них составить?

Решение: составим несколько выборок: (5,5,5); (6,7,8); (8,9,9)… Элементы повторяются, состав меняется, порядок не существенен. Согласно схеме, применяем формулу сочетаний с повторе­ниями из 6 по 3: . Однако, здесь есть небольшой подвох: треугольника со сторонами 5,5,10 не существует, так что их будет 55. Ответ: 55 треугольников.

4. ПРИМЕРЫ БОЛЕЕ СЛОЖНЫХ ЗАДАЧ КОМБИНАТОРИКИ

Задача 1. Выпуклый многоугольник имеет 90 диагоналей. Сколько у него сторон?

Решение: обозначим количество сторон многоугольника через n, вершин у него тоже будет n. Соединим вершины попарно отрезками, которых будет . Среди этих отрезков будет n сто­рон, остальные — диагонали. Составим уравнение по условию задачи: . Отсюда получа­ется квадратное уравнение: , корни которого n₁=15, n₂= — 12. По смыслу задачи подходит . Ответ: 15 сторон.

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

Решение: если участников — n человек, партий будет сыграно штук. Составим уравнение: , решив которое, найдем: . Ответ: 21 шахматист.

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

Решение: в данном случае можно найти количество способов в предположении, что из города А мы выехали по первой дороге, а результат умножить на 2. Все возможные пути закодируем следующим образом: если мы сворачиваем на данную просе­лочную дорогу, то ставим цифру 1, если нет — то 0.

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

. Ответ: 2048 дорог.

ЗАКЛЮЧЕНИЕ

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

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

Практическая значимость полученных знаний в области комбинаторики не только в матема­тике, но и в жизни заинтересовала нас не менее. Представителям самых различных специальностей приходиться решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр или иных объектов. Руководителю необходимо распределить несколько видов работ между подчиненными, диспетчеру школы – составить расписание уроков, ученому-химику — рассмотреть возможные связи между атомами и молекулами, филологу – провести анализ текста или изучить различные варианты сочетаний букв иностранного языка и т.д.

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

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

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Большая Российская энциклопедия в 30 томах. Т.14, 2009. — 751 с.

2. Будаев В.Д., Стефанова Н.Л. Математика и информатика. Учеб. пособие для студентов педагогических вузов. М.: Высш.шк., 2004. — 349 с.

3. Гнеденко Б. В., Журбенко, И. Г. Теория вероятностей и комбинаторика //Математика в школе. 2007 — №6. – с. 67-70.

4. Дихтярь М., Эргле Е. Исторические комбинаторные задачи и комбинаторные модели. //Математика. 2007. — №14. – с. 23-24.

5. Мордкович А.Г., Семенов П.В. Алгебра и начала анализа. Учебник и задачник. 10 класс. М.: Мнемозина, 2007.

6. Ожегов С.И., Шведова Н.Ю. Толковый словарь русского языка. М.,1999.

7. Рыбников К. А. История математики в двух томах. М.: Издательство МГУ, 1960-1963.

8. Халамайзер А.Я. Комбинаторика и бином Ньютона. М.: Просвещение. 1980.

9. http://www.mathclub.zala.ru/0921.html
10. http://combinatorica.narod.ru/second.html

ПРИЛОЖЕНИЯ

Приложение 1. Треугольник Паскаля.

Приложение 2. Треугольник Паскаля (в виде равнобедренного треугольника).

Приложение 3. Схема определения вида комбинации.