Двадцать четвёртая книжка серии «Школьные математические кружки» посвящена задачам классической комбинаторики. В них обычно требуется найти число элементов множества, причём порядок их перечисления не очевиден. Основное внимание уделяется общим принципам организации подсчёта и построению адекватных математических моделей с помощью соответствия. Эта брошюра продолжает и дополняет книжку «Комбинаторика»; здесь обсуждаются старые (сочетания) и новые базовые модели (шары и перегородки, диаграммы), а также изучаются способы их применения к решению более сложных задач.
Книжка содержит десять занятий математического кружка и обширный набор дополнительных задач. Все занятия доступны ученикам 7 - 9 классов, а некоторые – и 5 - 6 классов. Для удобства использования заключительная часть книжки, как всегда, сделана в виде раздаточных материалов. Возможность самостоятельного обучения обеспечена дублированием ответов в отдельном разделе. Книжка адресована школьным учителям математики и руководителям математических кружков.
Надеемся, что она будет интересна школьникам и их родителям, студентам педагогических вузов, а также всем любителям математики.
Как следует из названия, эта книжка служит продолжением нашей книжки "Комбинаторика". Это не значит, что пока первая полностью не изучена, ни одно занятие второй нельзя проводить. Например, с опытными пятиклассниками, много решавшими олимпиадные задачи в начальной школе, можно проводить два первых занятия: про перебор и про соответствие, а сочетания из первой книжки из-за работы с дробями отложить до 6 класса. Но все занятия этой книжки предназначены для кружка не первого года обучения.
Идейный стержень книжки "Комбинаторика"– кодировка. Её можно рассматривать как установление взаимно-однозначного соответствия между множествами, считаемыми в разных задачах. На этот раз нас в первую очередь интересует соответствие между двумя множествами, считаемыми в одной и той же задаче. Иногда уже в условии требуется сравнить указанные множества. В других случаях требуется подсчитать элементы неудобного множества, а для этого хорошо подобрать легко считаемое множество с тем же количеством элементов. Как видно по оглавлению, соответствию полностью посвящены два занятия: второе, рассчитанное на учеников 5-7 классов, и девятое, для более опытных 7-9-классников.
Задачи, решающиеся с помощью деления (см. занятие 3), тоже связаны с соответствием, на этот раз многозначным. На поиске соответствия между нужным и удобным множествами (которое может оказаться как однозначным, так и многозначным) строится и занятие 6. Ярким примером соответствия служит метод шаров и перегородок, предложенный на седьмом занятии.
Если соответствие можно считать обобщением кодировки, то перебор (см. занятие 1) – обобщением перечисления элементов множества с помощью таблиц и регулярных деревьев. Дети занимаются перебором с первых шагов в олимпиадной математике, постепенно набираясь опыта. Для того, чтобы этот опыт осознать, нужна мотивация. Ребёнок должен успеть достаточно много раз увязнуть в хаотичном переборе вместо разумно организованного и почувствовать, как трудно доказать полноту перебора. Только после этого он оценит разговор о видах перебора. Так что занятие не вошло в первую книжку не из-за сложности, а из-за неактуальности постановки вопроса для начинающих.
Девятое занятие в некотором смысле – антипод первого. На нём рассматриваются задачи, в которых перебор неоправданно трудоёмок или вовсе невозможен. Но постановка этих задач и не требует точного ответа, достаточно получить оценки.
По уровню сложности книжку можно условно разделить на две части. Первые пять занятий составлены для массового кружка 6-7 класса. Занятие про сочетания предполагает, что ребята с ними уже знакомы, но и их, и другие темы пора повторить. А занятие про треугольник Паскаля, напротив, написано для первого знакомства с ним, причём в более раннем возрасте, чем это принято. На нём детям предлагается заметить и объяснить интересные числовые закономерности, не используя ни алгебраическую технику, ни строгие рассуждения по индукции.
Занятия 6-10 следующего уровня сложности и написаны для ребят, серьёзно занимающихся олимпиадной математикой, и их учителей.
Разделяет эти две части статья, в которой обсуждается однозначность постановки вопроса "Сколькими способами ?" Учителя давно привыкли к этой фразе и не всегда осознают трудности в понимании её детьми. Часть этих трудностей объективны и связаны с нечётким условием, допускающим разные трактовки. Опытный человек понимает, что обычно имеется в виду в таких случаях, и решает привычную задачу. А ребёнок не обязан догадываться, что имел в виду, но не написал автор. Чтобы избежать ненужных терминологических трудностей в начале пути, мы в книжке "Комбинаторика" впервые сформулировали вопрос о количестве способов только на пятом занятии.
Вторая часть книжки отличается от первой не только сложностью задач, предлагаемых ученикам, но и степенью новизны подходов к ним, на которую хотелось бы обратить внимание учителей. Мы предлагаем взглянуть на задачи с традиционными формулировками с необычной стороны, в ряде случаев это приводит к новым приёмам решения. А на занятиях 8 и 9 и постановки задач нетипичны для школьного кружка.
В задачах для начинающих подсчёт вариантов разбивается на несколько аналогичных друг другу этапов, дерево перебора помогает как придумать решение, так и наглядно его изобразить. В более сложных задачах этапы не аналогичны, разбиение на них требует творческого подхода, и нарисовать дерево удаётся только уже постфактум, когда ключевая идея придумана. Занятие 6 посвящено именно таким задачам. Универсального алгоритма их решения не существует; предлагаемый нами метод скелетов учит лишь задавать себе правильные вопросы.
Задачи, решаемые методом шаров и перегородок, мы разделили на два занятия, седьмое и восьмое. Дело в том, что сводящиеся к нему задачи могут описываться и другими родственными моделями, заслуживающими на наш взгляд отдельного рассмотрения. Особое внимание уделено на занятии 7 строкам неотрицательных чисел с фиксированной суммой, а на занятии 8 – диаграммам Юнга. Навык переформулировки задач на языке наиболее уместной модели, а также понимание связей между моделями углубляет понимание соответствия – идейного стержня комбинаторики.
Диаграммы Юнга используются в различных разделах высшей математики. Школьники легко могут понять их определение и доказать простейшие свойства. Но пока диаграммы не возникают как естественная модель в содержательных задачах, возня с ними кажется бессмысленной. В занятии 8 и соответствующей ему части задачника мы предлагаем авторские задачи с типичными для математических соревнований формулировками, ключом к решению которых служат диаграммы Юнга.
Два последних занятия с разных сторон развивают всё ту же основную идею: комбинаторика – это не сборник задач с вопросом "Сколькими способами", а раздел математики, изучающий в первую очередь соответствие между объектами. Тема девятого занятия – комбинаторные неравенства. Они возникают в задачах, где вместо точного подсчёта всех объектов достаточно доказать, что их достаточно много (или, напротив, не слишком много). Мы не встречали подборок таких задач, поскольку начинающие с ними сталкиваются редко: зачем прикидывать, если несложно точно подсчитать? Однако в научной и практической работе и на олимпиадах высокого уровня не менее важно умение оценивать с помощью неравенств и понимать, какой оценки достаточно.
Последнее, десятое занятие продолжает второе. В нём тоже установление соответствия применяется в первую очередь для доказательства равномощности двух множеств, а не для подсчёта количества элементов каждого. Часть задач этого занятия связана с числами Каталана. Мы не ставим цели изучить их как можно более подробно и многогранно, а лишь используем как богатый источник интересных соответствий.
Завершает книжку список из более чем сотни дополнительных задач. Среди них есть известные, но большинство – новые, авторские. Дополнительные задачи разделены на две части. В первой части задачи попроще и сгруппированы по занятиям. Задачи второй части потруднее, как правило требующие при решении несколько идей; их порядок тоже связан с занятиями, но в меньшей степени. При ссылках они помечаются звёздочкой. Как всегда в этой серии, ко всем задачам приведены решения и ответы. Ответы есть в решениях и повторены в отдельном разделе. Часто ответ даётся в двух видах, например, С(4,24)-1=10625. Числовые ответы приведены только для проверки «других» решений, от учеников не надо требовать вычисления ответов, превосходящих 200.
Авторы благодарны И.С.Рубанову, чья авторская методика обучения комбинаторике, основанная на идее кодировки, а также опыт совместного преподавания повлияли на формирование наших взглядов.