ЛЕТНЯЯ ШКОЛА ДЛЯ ОДАРЕННЫХ ДЕТЕЙ
Решение логических задач
Решение логических задач
Три девочки, каждая со своим папой. Нужно переправить всех с одного берега на другой. В их распоряжении одна лодка без гребца, поднимающая только двух человек. Как переправить всех, если: а ) Девочки не согласны ехать в лодке, или быть на берегу с одним или двумя чужими папами без своего папы. б) Каждая девочка может самостоятельно вести лодку.
Уровень 2: ВЕДРО
Оригинальная физическая игра. Постройте цепь таким образом, чтобы докатить шар до ведра. Чем дольше путь шара к ведру, тем выше счет.
Помогите профессору преодолеть множество интересных уровней, хорошенько подумав.
Уровень 4:
МУРАВЬИ
Чёрные муравьи враждуют с красными. Найдите способ избежать стычки, чтобы все чёрные муравьи добрались до дома.
Чёрные муравьи враждуют с красными. Найдите способ избежать стычки, чтобы все чёрные муравьи добрались до дома.
Уровень 5:
МАШИНА ОТ ЗЛОДЕЕВ
Квест про грабителей. В этой флэш-игре нужно сделать механизм, который им поможет. Берите объекты и пробуйте их вставить в схему.
Квест про грабителей. В этой флэш-игре нужно сделать механизм, который им поможет. Берите объекты и пробуйте их вставить в схему.
Уровень 7:ТУРНИР ПО КОРИДОРУ
http://vorojeya77.narod.ru/QUORIDOR_ALLA.swf
СПРАВКА ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗМИНКИ (на листочках)
ГРАФЫ
(Источник: http://matschool2005.narod.ru/Lessons/Lesson2.htm)
СПРАВКА ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗМИНКИ (на листочках)
ГРАФЫ
(Источник: http://matschool2005.narod.ru/Lessons/Lesson2.htm)
Фигура образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек, называется плоским графом, или просто графом (рис. 2.1, а). Точки называются вершинами, а отрезки – ребрами графа.
Вместо отрезков в качестве ребер графов рассматриваются также кривые линии на плоскости (рис. 2.1, б).
Примерами графов могут служить схемы метрополитена, железных и шоссейных дорог, планы выставок и т.д. С помощью графов указываются различные связи между объектами.
Исторически сложилось так, что теория графов зародилась в ходе решения головоломок двести с лишним лет назад.
Одной из таких задач-головоломок была задача о кенигсбергских мостах, которая привлекла к себе внимание Леонарда Эйлера (1707-1783), долгое время жившего и работавшего в России (с 1727 по 1741 год и с 1766 до конца жизни).
Задача. В г. Кёнигсберге (ныне Калининград) было семь мостов через реку Прегель (рис. 2.2, где Л - левый берег, П - правый берег, А и Б - острова). Задача заключалась в следующем: можно ли, прогуливаясь по городу, пройти через каждый мост ровно один раз?
Эта задача связана с другими головоломками, суть которых заключалась в том, чтобы обвести контур некоторой фигуры, не отрывая карандаша от бумаги и не обводя ни одной линии контура дважды, т.е. "нарисовать одним росчерком". Такие контуры образуют так называемые уникурсальные графы.
На рисунке 2.3 изображен граф, соответствующий задаче о кёнигсбергских мостах. Требуется доказать, что этот граф является уникурсальным. Для этого рассмотрим понятие индекса вершины - число ребер графа, сходящихся в данной вершине, и докажем, что имеет место следующая теорема. Теорема. Для уникурсального графа число вершин нечетного индекса равно нулю или двум. Доказательство. Действительно, если граф уникурсален и его начало не совпадает с концом, то начало и конец являются единственными вершинами нечетного индекса. Остальные вершины имеют четный индекс, так как в каждую точку мы входим и выходим из нее. Если начало совпадает с концом, то вершин с нечетным индексом нет.
Приступим теперь к решению задачи. Определим четность вершин графа на рисунке 2.3. Вершина А имеет индекс 5, Б - 3, П - 3 и Л - 3. Таким образом, мы имеем четыре вершины нечетного индекса, и, следовательно, данный граф не является уникурсальным. Отсюда получаем, что во время прогулки по городу нельзя пройти по каждому из семи мостов только один раз.
