112828 (591185), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Задачи:

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

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

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

4. (Устно) Важен или нет порядок в следующих выборках (комбинациях):

1. капитан волейбольной команды и его заместитель;

2. три ноты в аккорде;

3. «шесть человек останутся убирать класс!»;

4. две серии для просмотра из нового многосерийного фильма.

5. Придумайте сами четыре различные ситуации, в двух из которых порядок выбора важен, а в двух – нет.

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

7. В магазине продают кепки трех цветов: белые, красные и синие. Кира и Лена покупают себе по одной кепке. Сколько существует различных вариантов покупок для этих девочек? Перечислите их.

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

Занятие №2. Подсчет вариантов с помощью графов. Таблица вариантов.

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

Д



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

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

Перебор вариантов можно организовать следующим образом. Выписать все числа, начинающиеся с цифры 1 в порядке их возрастания; затем – начинающиеся с цифры 2; после чего – начинающиеся с цифры 3. Таких комбинаций получим 27. При переборе легко было упустить какую-нибудь из них.

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

Рассмотрим два вида графов:

1. Граф-дерево (называют за внешнее сходство с деревом).

С помощью дерева проиллюстрируем проведенный перебор вариантов в примере 1.

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

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

1. Полный граф. Используется для решения задач, в которых все элементы множества взаимосвязаны.

П ример 2. При встрече каждый из друзей пожал другому руку (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было четверо?

Четырех друзей поместим в вершины графа и проведем все возможные ребра. В данном случае отрезки-ребра обозначают рукопожатия каждой пары друзей.

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

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

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

Для подсчета образующих чисел составим таблицу:

N=3·4=12

Задачи:

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

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

3. Одновременно происходят выборы мэра города и префекта округа. На должность мэра выставили свои кандидатуры Алкин, Балкин, Валкин, а на должность префекта – Эшкин, Юшкин, Яшкин.

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

   2. В скольких вариантах будет кандидатура Эшкина?

   3. В скольких вариантах фамилии кандидатов на должность мэра и на должность префекта состоят из разного числа букв?

   4. Как изменятся ответы в пунктах а) и б), если учесть еще кандидата «против всех»?

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

1. Нарисуйте дерево возможных вариантов похода.

2. Сколько всего вариантов похода могут выбрать туристы?

3. Сколько есть полностью не пеших вариантов?

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

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

   2. Составляя расписание уроков на понедельник для 10А класса, завуч хочет первым уроком поставить либо физику, либо алгебру, а вторым – либо русский язык, либо литературу, либо историю. Сколько существует вариантов составления расписания на первые два урока?

Определиться в успешности усвоения данной темы поможет самостоятельное составление учащимися задач. Можно предложить им придумать так называемое «задание для друга» с использованием каждого из трех методов.

Занятие №3. Кортежи. Правило произведения.

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

Рассмотрим задачу про «Суеверного председателя».

«Опять восьмерка!» - горестно воскликнул председатель клуба велосипедистов, взглянув на прогнутое колесо своего велосипеда. «А все почему? Да потому, что у меня членский билет № 888 – целых три восьмерки. И теперь не проходит и месяца, чтобы то на одном, то на другом колесе не появилась восьмерка. Надо менять номер билета! А чтобы меня не обвинили в суеверии, проведу ка я перерегистрацию всех членов клуба и буду выдавать только билеты с номерами, в которые не входит ни одна восьмерка. Не знаю только, хватит ли на всех номеров – ведь у нас в клубе почти 600 членов. Неужели придется сначала выписать все номера от 000 до 999, а затем вычеркивать из них все номера с восьмерками?» Чтобы помочь председателю, нам нужно решить такую комбинаторную задачу (учащимся можно предложить ее сформулировать):

Сколько существует трехзначных номеров, не содержащих цифры 8?

Далее учащиеся должны ответить на вопросы (Как бы вы решили такую задачу? С помощью какого метода? Какие еще методы решения применимы к данной задаче?) и вместе с учителем разобрать решение данной задачи.

Сначала найдем количество однозначных номеров, отличных от 8. Ясно, что таких номеров девять: 0,1,2,3,4,5,6,7,9. А теперь найдем все двузначные номера, не содержащие восьмерок. Их можно составить так: взять любой из найденных однозначных номеров и написать после него любую из девяти допустимых цифр. В результате из каждого однозначного номера получится 9 двузначных. А так как двузначных номеров было 9, то получится 9·9 = 9² двузначных номеров.

Итак, существует 9² = 81 двузначный номер без цифры 8. Но к каждому из этих номеров можно приписать справа любую из цифр 0,1,2,3,4,5,6,7,9 и получить трехзначный номер, не содержащий цифру 8. При этом получаются все трехзначные номера с требуемым свойством. В результате мы нашли 9²·9 = 9³ = 729 трехзначных номеров без восьмерок.

Если бы председатель клуба был еще суевернее и отказался и от цифры 0, поскольку она походит на вытянутое колесо, то он смог бы составить лишь 8³ = 512 трехзначных номеров и их уже не хватило бы на всех членов клуба.

С помощью этого примера вводятся понятие кортежа и правило произведения.

Кортежи. Номера, составленные из трех цифр, нельзя рассматривать как множество элементов. Во-первых, в номерах цифры могут повторяться (например, 775), а в множествах элементы не повторяются, во-вторых, в номерах важен порядок цифр (175 и 571 – совсем разные номера), а в множествах порядок элементов роли не играет. Поэтому, если мы хотим изучать такие объекты, как номера, или слова (в них тоже могут буквы повторяться, от перестановки букв слово меняется), нужно ввести новое математическое понятие, отличное от понятия множество.

Это новое понятие математики назвали кортежем (наряду со словом «кортеж» применяют названия «слово», «набор», «вектор», «конечная последовательность» и т.д.). Кортеж – французское слово, означающее торжественное шествие. И у нас иногда говорят «кортеж автомашин», «свадебный кортеж» и т.д. При этом кортеж автомашин может состоять из нескольких «Волг», нескольких «БМВ» и нескольких «Ауди». Если считать машины одной и той же марки неразличимыми, то получим, что в кортеже автомашин один и тот же элемент может повторяться несколько раз.

В математике кортеж определяют так. Пусть имеется несколько множеств X₁, …, X_k. Представим себе, что их элементы сложены в мешки, а мешки перенумерованы. Вытащим из первого мешка какой-нибудь элемент (то есть возьмем какой-нибудь элемент а₁ множества Х₁), затем вытащим элемент а₂ из мешка Х₂ и будем продолжать этот процесс до тек пор, пока из мешка Х_k не будет вытащен элемент а_k. После этого расставим полученные элементы в том порядке, в котором они появились из мешков (а₁, а₂, …, а_k). Это и будет кортежем длины k, составленным из элементов множеств X₁, …, X_k. Элементы а₁, а₂, …, а_k называют компонентами кортежа.

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

Здесь учащимся можно дать индивидуальное задание: взять любое множество и составить из его элементов кортеж, при этом спросить их, почему он является кортежем, и сколько кортежей можно составить из этого множества?

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

Правило суммы. Если элемент а можно выбрать m способами, а элемент b можно выбрать n способами, причем любой выбор элемента a отличен от любого выбора элемента b, то выбор «a или b» можно сделать m + n способами. (Например, если на блюде лежат 7 яблок и 4 груши, то выбрать один плод можно 7+4=11 способами).

На языке теории множеств это правило формулируется следующим образом: Если пересечение конечных множеств A и B пусто, A∩B=Ø, то число элементов в их объединении равно сумме чисел элементов множеств A и B: A∩B=Ø =>

Здесь целесообразно задать учащимся вопросы: А как будет сформулировано правило суммы для пересекающихся множеств A и B? в общем случае для конечного числа множеств?

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

Правило произведения. Возьмем несколько конечных множеств X₁, …, X_k, состоящих соответственно из n₁, …, n_k элементов, и найдем, сколько кортежей длины k можно составить из элементов этих множеств. Способ, которым мы решим эту задачу по сути дела будет тем же самым, каким было найдено число трехзначных номеров без восьмерок. Сначала найдем число кортежей длины 1, составленных из элементов множества Х_1. Ясно_, что их число равно n₁. Возьмем теперь один из этих кортежей (а₁) и припишем к элементу а₁ справа по очереди все элементы множества х₂.Получится n₂ кортежей длины 2, у которых первая координата равна а₁. Но вместо а₁ можно было бы взять любой другой элемент из Х₁. Поэтому получается n₁ раз по n₂ кортежа, а всего n₁∙ n₂ кортежей длины 2 или, как чаще говорят пар. Из каждой такой пары получим n₃ троек, приписав к ней по очереди все элементы множества Х₃, а всего n₁∙ n₂∙ n₃ троек. Продолжая этот процесс, получим, в конце-то концов, n₁∙ n₂∙ …∙ n_k кортежей длины k, составленных из элементов наших множеств.

Характеристики

Список файлов ВКР