Внеклассное мероприятие "Введение в комбинаторику".
занимательные факты по алгебре (9, 10, 11 класс) на тему

        Внеклассное мероприятие «Введение в комбинаторику»

 Сценка 1

Ватсон – Холмс, это, кажется, по вашей части ….

Холмс – Дорогой Ватсон, у вас на подносе бутылки с «Фантой», «Колой»,  «Спрайтом» и «Мериндой». Но я не пью искусственных напитков. Вы же знаете.

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

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

Ватсон – Вы смеетесь, Холмс. О какой науке может идти речь в подобной ситуации?

Холмс – Речь идёт о комбинаторике – разделе математики, в котором рассматриваются задачи о подсчёте числа комбинаций, составленных из некоторых элементов по определенным правилам. Вот сейчас вы, Ватсон, столкнулись с элементарной комбинаторной задачей: “Сколько существует способов составить коктейль из двух напитков, взятых в равных дозах, если у вас имеются четыре различных напитка.

Ватсон – И как же вы так быстро решили эту задачу?

Холмс – Эта задача решается элементарно, Ватсон. Возьмите листок бумаги и изобразите условно четырьмя кружками ваши бутылки с напитками, а теперь соедините линиями каждую  со всеми остальными. Теперь подсчитайте, сколько всего соединенных линий образовалось. Вот вам  те шесть комбинаций, о которых я говорил. Условно их можно записать так: АВ, АС, AD, BC, BD, CD.

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

Холмс – Ну, и сколько, Ватсон?

Ватсон – Подождите минуточку, сейчас сделаю рисунок и подсчитаю.

- О, Холмс, теперь я понимаю, почему, когда мы расследовали преступление в загородном доме сэра Джорджа Бэрнвелла, вы заметили, что совершить его могла одна из двенадцати парочек… Помните, мы обнаружили в зарослях кустарника в парке рядом сэра Джорджа место, где, очевидно, воры долгое время стояли (там еще была примята трава, но отпечатки ног не были четко видны) и наблюдали за окнами дома. Вы обнаружили табачный пепел и шпильку. Как потом выяснилось, табаком пользовались четверо из слуг виллы, а длинные волосы, требующие укладывания с помощью шпилек, имели в доме три женщины

Холмс – Вы абсолютно правы, Ватсон, я подсчитал, что «дуэтов» воришек существует всего 4*3=12. Если помните, мы их тогда обнаружили довольно быстро, найдя еще несколько улик.

Автор

Шерлок Холмс и доктор Ватсон столкнулись с так называемыми комбинаторными задачами. Так что же изучает комбинаторика?

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

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

                                         Решение:

Первая цифра                             Вторая  цифра

двузначного числа                     двузначного числа

                                                                 0

                                                                 1

           1                                                   2

                                                                 3

                                                                 0

                                                                 1

           2                                                   2

                                                                 3

                                                                 0

                                                                 1

           3                                                   2

                                                                 3

Таким образом 3*4=12.

Для решения этой задачи мы воспользовались правилом произведения.

Правило произведения: Если элемент х можно выбрать n способами, а элемент у – m способами, то пару (х, у) можно выбрать n*m способами.

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

                                             Решение

Девушку можно выбрать 5 способами, а юношу можно выбрать 3 способами. Значит по правилу произведения пару можно выбрать 3*5=15 способами.

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

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

                                            Решение

На первом месте могут быть 4 цифры ( все, кроме 0)

На втором месте могут быть 5 цифр

На третьем месте могут быть 5 цифр

Дальше находим по правилу произведения 4*5*5=100 трехзначных чисел.

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

                                           Решение

               4*4*4*4= 256 четырехзначных чисел.

Обобщенное правило произведения. Если элемент х1 можно выбрать k1 способами, а элемент х2 – k2 способами, …, элемент хm – km способами, то набор (х1, х2, …,хm) можно выбрать k1*k2*…..*km способами.

Сценка2                              

Холмс - Ватсон, а хотите еще одну задачку, на первый взгляд похожую на вашу задачу с коктейлями?

Ватсон - Любопытно послушать.

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

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

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

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

Обратимся к задаче из диалога.

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

                                      Решение

                                     Генри

 Вилли                         Джон

                                     Сэм

                                     Вилли

 Генри                         Джон

                                     Сэм

                                     Генри

 Джон                          Вилли

                                     Сэм

                                     Генри

 Сэм                             Джон

                                     Вилли

Из схемы видно, что пары типа Вилли – Генри, Генри – Вилли различные (важен порядок записи имен джентльменов). Рассмотренные в этом примере всевозможные комбинации из 2-х элементов, выбираемых из данных четырех элементов, в случае, когда порядок расположения элементов в паре имеет значение, называют размещениями из четырех элементов по два.

Обозначают  = 3*4=12

(А – первая буква французского слова arangement, что в переводе означает размещение, приведение в порядок).

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

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

                                        Решение

В введенных нами обозначениях мы должны найти .

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

                               = 4*3*2 = 24.

Дадим теперь общее определение понятия размещения. Комбинации, составленные из k элементов, взятых из n данных элементов (0< k), и отличающиеся одна от другой либо составом, либо порядком расположения элементов, называются размещениями из n элементов по k элементов. Обозначается

Пусть составлены размещения из 5 элементов по 3.

1 элемент можно выбрать 5 способами, 2 элемент можно выбрать 4 способами, 3 элемент можно выбрать 2 способами (повторение первого элемента не допускается)

 = 5*4*3 = 60.

Проанализировав получившийся результат, получим формулу.

Число размещений из n элементов по k ( обозначается ) равно произведению к последовательно уменьшающихся на единицу сомножителей, первый из которых равен n, то есть, для любых натуральных n и k (k) справедлива формула

                                              = n( n - 1)( n - 2 )……( n – k + 1 ).

Задача 2. Найти ,

              Решение

 = 6*5*4*3*2 = 720,

7*6 = 42.

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

               Решение

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

Задача 4. Сколько семибуквенных слов можно образовать из букв, составляющих слово «гипотенуза» (под «словом» здесь понимается любая комбинация из 7 букв Г, И, П, О, Т, Е, Н, У, З, А, без повторения какой- либо буквы в «слове», само слово необязательно должно существовать в русском языке).

               Решение

        =10 *9*8*7*6*5*4 = 604800.

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

              Решение

      = 30 * 29 = 870.

Задача 6. В соревновании участвуют 10 команд. Сколько существует вариантов распределения призовых мест?

             Решение

     = 10 * 9 * 8 = 720.

                                       Сочетания

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

Ватсон – Да, мне тогда не очень хотелось пробовать все комбинации из двух напитков.

Холмс – Ватсон, а ответьте на такой вопрос: влияет ли на вкус коктейля порядок вливания напитков в бокал? Допустим ваши напитки имели названия А, В, С, Д. Так вот коктейль АВ и коктейль ВА – это один и тот же коктейль или разные?

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

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

Комбинации, составленные из к элементов, взятых из n данных элементов (0< k< n), отличающиеся друг от друга составом элементов, называются сочетаниями из n элементов по k элементов.

Для обозначения числа сочетаний из n элементов по к в комбинаторике используется запись Сn. Читается: « Число сочетаний из эн элементов по к» или более коротко: «Цэ из эн по ка»; С первая буква французского слова  combinaison, что в переводе обозначает «сочетание».

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

Ватсон – Холмс, я помню, что в моей задаче число всевозможных коктейлей из двух напитков, выбираемых из четырех имеющихся, равно, 6, но мы для подсчета рисовали  схему, а вы, хитрец, наверняка знаете формулу для нахождения числа сочетаний при любых значениях n и k.

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

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

Таким образом  Аn = СnРk откуда легко получаем формулу для подсчета числа сочетаний из п элементов по к элементов: Сn = 

Ватсон – Холмс, я теперь хорошо буду помнить формулу, связывающую сочетания, размещения и перестановки. Но, очевидно, при решении задач нужна формула, выражающая число сочетаний Сn непосредственно через числа n и k?

Холмс – Если в нашу формулу вместо Аn и Рn подставить их выражения Аn = ,      Рk =k!, то получим симпатичную формулу для подсчета числа сочетаний из n элементов по к:        Сk = .

Ватсон – Сейчас проверю, верно, ли мы подсчитали число всевозможных коктейлей, составленных из двух напитков, которые выбирались из четырех имеющихся у нас напитков. В этом случае n=4, k=2,  С4 ==  = 6.

Получился тот же результат, что и ранее.

Использованная литература: В.Ф.Бутузов, Ю.М.Колягин и др. «Математика 11 класс», М. «Просвещение» !996.