Задача о мостах: олимпиадная математика
Привет, друзья! С вами увлекательная математика, и сегодня у нас очень интересный вид задач.
Удивительно, но целые разделы науки рождаются иногда из интереса увлечённых людей. Например, так из задачи о семи мостах Кёнингсберга родилась теория графов. К уже известному тогда математику Эйлеру обратился знакомый с просьбой решить старинную задачу-развлечение горожан: как пройти по семи мостам, соединяющим 4 района Кёнингсберга, только по одному разу.
Эйлер понял, что это был совершенно новый тип математики - «геометрия положений», сегодня известная как топология. В топологии точная форма или расположение объекта не имеют значения.
Эйлер сразу понял, что такой вид задач не решается перебором маршрутов, ведь мостов в следующий раз может оказаться 12 или 120! Он начал разрабатывать правила для разных случаев - чётного и нечётного количества "связей" (мостов), начала и конца путешествия (нужно вам вернуться в точку старта или нет), и таким образом, увлёкшись, создал теорию графов! Теперь этот раздел математики также называют теорией сетей, он очень востребован - с его помощью разрабатывают транспортные сети, логистические маршруты, вся мировая экономика держится на принципах, разработанных Эйлером.
А вы знаете, как определить, можно ли нарисовать картинку, не отрывая карандаш от бумаги, и не проводя ни одну линию дважды? Или есть похожая задача про дворец, который надо обойти и запереть за собой все двери, и надо понять, с какой комнаты имеет смысл начать обход.
Итак, чтобы обойти всю фигуру, не проходя дважды по каждой линии, нужно посчитать линии, сходящиеся в каждой точке пересечения.
Замкнутые фигуры, у которых во всех пересечениях четные числа, можно обвести одной линией. Остальные фигуры надо начинать обводить в нечётных «узлах», то есть там, где сходится 3, 5, 7 и более линий.
Если в замкнутой фигуре нечётных «узлов» больше двух, то обвести такую фигуру, не отрывая карандаш от бумаги, не получится.
У этой задачи много модификаций. Такие задачи часто встречаются в олимпиадах, и потренироваться решать их можно в .