Вот одна любопытная головоломка,
примечательная не только общим принципом, лежащим в ее основе, но также и
тем, что она достаточно древняя и связана с некой забавной историей.
Некогда город Кенигсберг, разделенный рекой Прегель на четыре части, включая
остров Кнайпхоф, имел восемь мостов. Вот с этими-то мостами и связана
старая головоломка, озадачивавшая его славных жителей более двух веков
назад.
Прогулка по всем мостам всегда была
приятным развлечением для молодежи. Согласно преданиям, размышления о
том, насколько длинным окажется путешествие по всем мостам, привели к
поразительному выводу, что совершить прогулку по всем мостам, не пройдя
по какому-то из них более одного раза, невозможно.
История сохранила упоминание о том, как
группа молодежи в 1735 г. посетила математика Леонарда Эйлера с просьбой
внести в это дело ясность. Год спустя Эйлер представил Российской
Академии наук внушительный отчет, в котором утверждалось, что данная
задача неразрешима. Этот отчет появился в трудах Академии за 1741 г.
и был переиздан на французском и английском языках, поскольку речь шла о
принципе, применимом в случае любого числа мостов.
Профессор У. Роуз Болл из Тринити-колледж,
обсуждая древность и достоинство этой задачи, заблуждается, приписывая
ее авторство самому Эйлеру, кроме того, он утверждает, что, согласно
картам Бедекера, мостов в Кенигсберге было тогда семь. Но в старых
записях говорится о восьми мостах, а наша карта аккуратно перерисована
из Бедекера.
В данной задаче мы не касаемся вопросов
возвращения в исходную точку. Нужно просто доказать, что, начав с
какого-то произвольного места в городе, можно попасть в некую его точку,
пройдя по каждому мосту ровно один раз. Мы просим читателя ответить,
сколькими различными путями это можно сделать и какой из этих путей
наикратчайший? ПРАВИЛЬНЫЙ ОТВЕТ Существует 416 способов выполнить это задание. Наикратчайшим будет путь O – P, D – C, E – F, H – G, I – J, L – K, N– M и А – В; но поскольку существует миллион неподходящих нам путей, то такой малостью, как 416, можно смело пренебречь.
[Читатель не должен всерьез принимать
слова автора головоломки Лойда относительно числа мостов, ему, разумеется, было известно,
что Эйлер изучал случай семи мостов и эта знаменитая работа явилась
первой публикацией по топологии.]
|