Методические рекомендации для проведения курса «Комбинаторика» (стр. 8 )

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

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

В финал турнира по шашкам вышли два российских игрока, два немецких и два американских. Сколько партий будет в финале, если каждый играет с каждым по одному разу и представители одной страны не играют между собой? ( Граф на рис.2.25)

2.  В вазе лежали конфеты четырех сортов. Каждый ребенок взял по две конфеты. И у всех оказались отличающиеся наборы конфет. Сколько могло быть детей? ( Граф на рис.2.26)

  н.  1.  . 2

н.  .а

р.  .а  4 .  .3

  р.

  Рис. 2.25  Рис. 2.26

Можно предлагать учащимся и обратные задания: составить по имеющемуся графу задачу. Например, «Рассмотри внимательно граф (рис.2.27) и пофантазируй, о какой ситуации он может тебе рассказать»

  .  .

  .  .

  Рис. 2.27

Ученики, рассуждая, что точки могут обозначать людей, предметы, а линии говорят о том, что из них образуют пары, составляют разные варианты задач. Например: «Четыре подружки вечером по телефону созваниваются друг с другом. Сколько звонков было сделано, если каждая поговорила с каждой по одному разу?», или «В магазине продаются елочные шары четырех видов. Сколько отличающихся наборов, состоящих из разных шаров, можно составить?».

Учащихся V – VI классов можно познакомить с применением граф – дерева для решения комбинаторных задач. Сначала необходимо научить детей понимать эти графы. С этой целью предлагаются следующие задания:

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

  верхний кубик

  .к 

  средний  кубик

  с.  ж.  .з 

  нижний  кубик

  ж.  .з  с.  .з  ж.  .с

  Рис. 2.28

б) Какое число зашифровано в выделенном пути (рис.2.29)? Покажи путь, в котором зашифровано число 5571.

  5

  5  7

  1  7  1  7

  7  1  7  1

  Рис. 2.29

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

Рассмотрим задачу: «Сколько  двухзначных чисел можно составить, используя цифры 1, 4 и 7?»

Для её решения построим специальную схему (граф – дерево) (рис.2.30).

  *

  первая цифра 

  1  4  7

вторая цифра

  1  4  7  1  4  7  1  4  7

числа:  11  14  17  41  44  47  71  74  77

  Рис. 2.30

Эта схема действительно похожа на дерево, вверх ногами и без ствола. Знак * изображает корень дерева, ветви дерева различные варианты решения. Чтобы получить двузначное число, надо сначала выбрать первую цифру, а для этого есть три варианта: 1, 4 или 7.Поэтому, из точки * проведены три отрезка и на концах поставлены цифры 1, 4 и 7 . Затем надо выбрать вторую цифру, а для этого также есть три варианта: 1, 4 или 7. Поэтому от каждой первой цифры проведено по три отрезка, на концах которых снова записано 1, 4 и 7. Итак, получено всего 9 различных двухзначных чисел. Других двухзначных чисел из этих трех цифр составить не возможно.

Рассмотрим, как построение дерева помогает решить самые разные комбинаторные задачи.

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

Решение: Изобразим все возможные  способы, совершить путешествие при помощи дерева (рис.2.31). При построении дерева использованы следующие обозначения: Т – теплоход, П – поезд, С – самолет, А – автобус.

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

  Волгоград

  *

Нижний Новгород

  т  п

Москва

  с  п  т  а  с  т  п  а

варианты: тс  тп  тт  та  пс  пт  пп  па

  Рис. 2.31

Задача 2: Сколько трехзначных чисел меньше 900, в которых нет одинаковых цифр, можно составить из цифр 9, 7, 5 и 0?

Решение:  При решении ученики рассуждают следующим образом: «Если нужно составить числа меньше 900, то первой цифрой в числе может быть 7 или 5, ставим из точки * два отрезка и на концах ставим цифры 7 и 5 (рис.2.32). Сначала составим все числа с первой цифрой 7. При этом второй цифрой может быть либо 9,либо 5, либо 0 ( проводим линии). Если первая цифра 7, вторая 9, то третьей могут быть только цифры 5 или 0 (проводим линии, ставим две точки). Если первая цифра 7, вторая 5, то третьей могут быть 9 или 0 … и т. д. Всего полачается 12 чисел, удовлетворяющих заданным условиям.”

  *

первая цифра

  7  5

вторая цифра

  9  5  0  9  7  0

третья цифра

  5  0  9  0  9  5  7  0  9  0  9  7

числа:  795  790  759  750  709  705  705 597 590 579 570 509 507

  Рис. 2.32

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

Примеры задач, которые можно решать на третьем этапе с помощью таблиц или графов приведены в приложении 1 (задачи 20 – 31).

§ 5. Обучение решению комбинаторных задач с помощью способа умножения

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

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

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

Задача 1: У Кролика две табуретки: красная и зеленая. К нему в гости пришли Винни – Пух и Пяточек. Сколькими способами он может рассадить гостей?

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

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

Решение: сначала учащиеся решают задачу способом перебора. Затем учитель предлагает провести такие же рассуждения, как и в предыдущей задаче: на красную табуретку может сесть или Пух, или Пяточек, или Иа. Всего имеются три возможности. На синюю табуретку сядет один из двух оставшихся гостей. Ну а на желтую табуретку сядет тот гость, который не успел занять ни красную, ни синюю. Получаем 3 * 2 * 1 = 6  способов.

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

Решение: рассуждая аналогично предыдущей задаче, ребята получат ответ

5 * 4 * 3 * 2 * 1 = 120  способов.

Учитель подводит итог: двух гостей на две табуретки можно рассадить 2 * 1=2 способами; трех гостей на три табуретки можно рассадить 3 * 2 * 1 = 6 способами; четырех гостей на четыре табуретки – 4 * 3 * 2 * 1 = 24 способами; пять гостей на пять табуреток – 5 * 4 * 3 * 2 * 1 = 120 способами.

Здесь необходимо сообщить, что произведение 1 * 2 * 3 * 4 * 5 обозначается 5!, ввести термин « факториал» и предложить учащимся вычислить 6! и 7!.

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

Приведем задачи, которые учащиеся могут решить способом умножения:

Задача 4:  В некотором городе у всех велосипедистов были трехзначные номера. Но  велосипедисты  попросили, чтобы в этих номерах не встречались цифры 0 и 8, потому что первая из них похожа на вытянутое колесо, ну а что для велосипедиста «восьмерка» колеса – знает каждый. Хватит ли им номеров, если в этом городе велосипеды имеют 710 человек?

Решение: для выбора цифры сотен номера имеется восемь возможностей, а именно 1, 2, 3, 4, 5, 6, 7, 9. Столько же возможностей для выбора цифры десятков и единиц. Всего номеров будет: 8 * 8 * 8 = 512. Так что на всех обладателей велосипедов их не хватит.

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

Решение: первый урок можно поставить 10 способами, второй  9 способами (один предмет уже поставлен), третий – 8, четвертый – 7, и т. д., все шесть предметов. Всего получается 10 * 9 * 8 * 7 * 6 * 5 = 151200 способов.

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

Решение: если решать эту задачу аналогично предыдущей, то получится ответ  6 * 5 = 30 партий. Этот ответ не верный. Дело в том, что в первой партии «1» – «2» участника неважно, неважно кокой участник будет первым, а какой вторым. А при нашем методе подсчета эта партия подсчитана дважды – и как партия «1» – «2» и как партия «2» – «1».Поэтому ответ получился вдвое больше, чем следует. Значит, в турнире состоится 30: 2 = 15 партий. Можно предложить ребятам проверить ответ, построив граф или занумеровав участников числами от 1 до 6, выписать все возможности.