28
28
Сколько всего различных путей и какой из них наикратчайший!
Вот одна любопытная головоломка, примечательная не только общим принципом, лежащим в ее основе, но также и тем, что она достаточно древняя и связана с некой забавной историей. Некогда город Кенигсберг,[6] разделенный рекой Прегель на четыре части, включая остров Кнайпхоф, имел восемь мостов. Вот с этими-то мостами и связана старая головоломка, озадачивавшая его славных жителей более двух веков назад.
Прогулка по всем мостам всегда была приятным развлечением для молодежи. Согласно преданиям, размышления о том, насколько длинным окажется путешествие по всем мостам, привели к поразительному выводу, что совершить прогулку по всем мостам, не пройдя по какому-то из них более одного раза, невозможно.
История сохранила упоминание о том, как группа молодежи в 1735 г. посетила математика Леонарда Эйлера с просьбой внести в это дело ясность. Год спустя Эйлер представил Российской Академии наук внушительный отчет, в котором утверждалось, что данная задача неразрешима. Этот отчет появился в трудах Академии за 1741 г. и был переиздан на французском и английском языках, поскольку речь шла о принципе, применимом в случае любого числа мостов.
Профессор У. Роуз Болл из Тринити-колледж, обсуждая древность и достоинство этой задачи, заблуждается, приписывая ее авторство самому Эйлеру, кроме того, он утверждает, что, согласно картам Бедекера, мостов в Кенигсберге было тогда семь. Но в старых записях говорится о восьми мостах, а наша карта аккуратно перерисована из Бедекера.
В данной задаче мы не касаемся вопросов возвращения в исходную точку. Нужно просто доказать, что, начав с какого-то произвольного места в городе, можно попасть в некую его точку, пройдя по каждому мосту ровно один раз. Мы просим читателя ответить, сколькими различными путями это можно сделать и какой из этих путей наикратчайший?