Семинар ДООМ: Метод графов в задачах "Кенгуру"

Метод графов в задачах «Кенгуру»

Рано или поздно всякая правильная математи-ческая идея находила применение в том или ином деле. Алексей Николаевич Крылов.

Кто сегодня не играет в «Кенгуру». Большинство учителей математики удив-ленно пожмет плечами: «Таких нет». Потому что, на сегодняшний день, это самая массовая и хорошо организованная в международном масштабе математическая олимпиада. Игра-конкурс «Кенгуру-математика для всех» возник в Австрии. Идея этого конкурса принадлежит известному математику и педагогу Питеру Холлорану. Це-лью конкурса является - привитие самому широкому кругу учащихся интереса к ма-тематике. Удивительный мир математики предстает перед участниками конкурса-игры с самой привлекательной стороны: со стороны мира занимательных, нестан-дартных задач; мира, который наполнен добрыми персонажами детских сказок; ми-ра, в котором все просто и очень интересно и совсем не страшно сделать первый шаг, а потом второй, третий… Все это замечательно, однако мудрость гласит: « Хорош тот экспромт, который как следует подготовлен». Другими словами учитель математики должен готовить своих воспитанников к участию в олимпиаде. В текстах «Кенгуру» за последние годы встречается достаточное количество задач, которые решаются методом графов. Любой ребенок, решающий задачу, не-произвольно пытается изобразить условие в виде схемы, некоторого рисунка. И это понятно, визуализация условия упрощает поиск решения, поэтому метод графов воспринимается детьми естественным образом. Теоретическая и практическая основа по теории графов, предложенная в дис-танционной обучающей олимпиаде по математике ДООМ, позволяет учащимся да-же без помощи учителя освоить основные понятия этой теории и научиться приме-нять их в решении задач, и что самое главное, сделать самые первые шаги к само-обучению с помощью Интернет-технологий. Если знания получены и не нашли дальнейшего применения – это плохо. Олимпиада ДООМ заканчивается, а расставаться не хочется. На носу «Кенгуру». Давайте посмотрим, какие задачи «Кенгуру» решаются методом графов. Такое зада-ние было предложено Парной Даше, ученице 7а класса, капитану команды Новички 019. Результат ее поисков представлен участникам ДООМа на блиц-турнире.

Попытаюсь сделать несложную классификацию задач на графы в «Кенгуру».

1. Задачи на перебор вариантов, комбинаторные. Хорошо решаются с помощью деревьев. Например:

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

(А) 6 (В) 4 (С) 2 (D) 8 (E) 10

Построить дерево вариантов здесь не сложно, остается из полученных трехзначных чисел отобрать те, которые делятся на 6.

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

(А) 24 (В) 9 (С) 1 (D) 4 (E) 12

2. Задачи на пересчет количества путей. Хорошо решаются с помощью схемы маршрутов. Например:

(А) 13 (В) 33 (С) 42 (D) 26 (E) 40

Задача. Сколько путей, идущих по стрелкам, ведут из А в D?

Анализ схемы позволяет наметить пути возможного движения и сосчитать их коли-чество.

1) А-В-Д 3*4=12;

2) А-В-С-Д 3*1*3=9;

3) А-С-Д 3*3=9;

4) А-С-В-Д 3*1*4=12

Итого 12+9+9+12= 42

3. Задачи на оптимизацию (самый короткий маршрут, самый удобный путь, самое меньшее время, наименьшее количество рабочих дней и т.д)

Задача. Во дворе бегают 14 кошек и котят. Каждая кошка-мама вывела на прогулку не меньше двух своих котят. Каким может быть наибольшее количество кошек – мам.

(А) 18; (В) 4; (С) 5; (Д) 6; (Е) 7.

5. Логические задачи, задачи «кто есть кто», задачи на переливание и взве-шивание.

Задача. Когда идет дождь, кошка сидит в комнате или в подвале. Когда кошка в комнате, мышка сидит в норке, а сыр лежит в холодильнике. Если сыр на столе, а кошка - в подвале, то мышка – в комнате. Сейчас идет дождь, а сыр лежит на столе. Тогда обязательно

(А) кошка в комнате; (В) мышка в норке; (С) кошка в комнате или мышка в норке; (D) кошка в подвале, а мышка в комнате; (E) такая ситуация не возможна.

Задача. Старый гном разложил свои сокровища в 3 разноцветных сундука, стоящих у стены: в один – драгоценные камни, в другой - золотые монеты, а в третий – ма-гические книги. Он помнит, что - красный сундук, правее, чем драгоценные камни; - магические книги правее, чем красный сундук. В каком сундуке лежат магические книги, если зеленый сундук стоит левее, чем си-ний?

(А) в синем; (В) в зеленом; (С) в красном; (Д) нельзя определить; (Е) гном что-то запомнил неверно.

Задача. Восемь мальчиков живут на одной улице, каждый в своем доме. Андрей живет рядом с Бернардом, Генрих напротив Клавдия, Эрик рядом с Франциском, Даниэль рядом с Андреем, Франциск напротив Даниэля и рядом с Генрихом, Лех рядом с Эриком. Таким образом

(А) Клавдий живет около Франциска; (В) Генрих – напротив Андрея; (С) Эрик – напротив Бернарда; (Д) Клавдий – рядом с Даниэлем; (Е) Лех – рядом с Генрихом.

6. Задачи «Начертить фигуру одним росчерком пера.

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

(А) А; (В) В; (С) С; (Д) Д; (Е) нет такой точки

7. Задачи, которые решаются с помощью кругов Эйлера ( Не смогли найти в текстах с 1995 по 2004, но они точно есть.)

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