Семинар ДООМ. Решение комбинаторных задач с помощью графов

Участник:Янина Ирина Владимировна Участник:ЛОГО 053

Занятие математического кружка в 5 классе

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

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

Цель:

• знакомство с новым способом решения комбинаторных задач;

• развитие математического мышления и логики;

• повышение интереса к изучению математики.

1) Первое знакомство с графом.

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

Задача. У Лёвы 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами он может выбрать конверт и марку, чтобы отправить письмо? Учащиеся легко убеждаются, что всего вариантов 6.

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

Граф для данной задачи строится в два этапа: сначала мы выбираем конверт, а потом марку.

2) Решение задач первого блока с помощью графов.

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

Задача 1.1 Ужасные грабители Кнопка и Скрепка решили украсть из сейфа золотой ключик Буратино. Для того чтобы открыть замок входной двери, им нужно подобрать двузначный код. Причём известно, что дверь запирает Буратино, который знает пока ещё только 4 цифры: 1, 2, 3, 4. Сколько вариантов придётся перебрать Кнопке и Скрипке, чтобы проникнуть в дом?

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

Задача 1.3 У ковбоя Джека две лошади: каурой и гнедой масти, два седла: красное и зелёное, две пары шпор: длинные и короткие, два револьвера: один марки «Кольт», другой – «Смит – и – Вессон». Сколькими способами Джек может экипироваться для конной прогулки по прериям?

Задача 1.4 Космический корабль «Циклоп» опустился на неизвестную планету Х звезды V созвездия Центавр. Планета оказалась обитаема и разделена океанами на три материка. Каждый материк выдвинул трёх представителей для того, чтобы лететь с кораблём на Землю. Представителей первого материка зовут Ман, Зан, Сан, второго – Пын, Фын, Шин, третьего – Хыр, Кыр, Дыр. Но на «Циклопе» не хватит анабиозных ванн для девяти человек. Он может взять только трёх. Сколько способов у инопланетян составить делегацию на Землю?

Учащиеся легко найдут ответ и, не вычерчивая граф полностью.

3)Решение задач второго блока способом умножения.

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

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

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

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

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

Задача 2.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!.

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