Простая логическая задача, у которой нет решения

Один весьма одаренный ученый как-то раз попытался решить эту простейшую логическую задачу и не смог. Точнее, ему удалось доказать, что решения не существует и параллельно открыть математическую последовательность, которую он назвал, естественно, в свою честь. Тем ученым был Леонард Эйлер, а его последовательность называется эйлеровы циклы. Однако, спустя более двух столетий задачу все-таки решили. И если вы ничего из написанного не поняли, то рекомендуем к прочтению этот материал.

Издавна среди жителей старого Кенигсберга была в ходу такая головоломка: как так исхитриться и пройти по всем городским мостам через реку Преголя, чтобы не пройти ни по одному из них дважды. Не один мозг был сломан в попытках решить эту задачу как теоретически, так и во время прогулок. Более того, доказать или опровергнуть возможность существования такого маршрута никто тоже не мог. Попробуйте сами, может вам удастся найти тот самый путь?

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

Так и жили бедные горожане без решения, пока в 1736 году талантливый во всех смыслах член Петербургской академии наук Леонард Эйлер, внесший существенный вклад в становление российской науки, научно обосновал невозможность решения этой задачи.

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ
РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

Итак, для начала нарисуем упрощенную схему города в виде математического графа. Его ребра у нас будут соответствовать мостам — их всего семь, — а частям города — вершины нашего графа. В процессе решения задачи Эйлер пришел к следующим выводам:

  • Не существует такого графа, который имел бы нечетное число нечетных же вершин
  • Если все вершины графа четные, то можно начертить его без отрыва карандаша от бумаги, при этом начало и конец могут быть в одной вершине
  • Если две вершины графа нечетные, то этот граф можно начертить без отрыва карандаша от бумаги, но в таком случае начало будет в одной нечетной вершине, а конец — в другой
  • У графа кенигсбергских мостов все вершины были нечетными, из чего следовало, что невозможно пройти по всем мостам, не проходя ни по одному из них дважды
РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

Благодаря семи кенигсбергским мостам Эйлер изобрел математические циклы имени себя. Эйлеров цикл — это замкнутый путь, проходящий через каждое ребро графа ровно по одному разу. Согласно теореме, эйлеров цикл существует тогда и только тогда, когда граф связный (между любой парой вершин графа есть как минимум один путь) или будет являться связным, если удалить из него все изолированные вершины, и в нем отсутствуют вершины нечетной степени.

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

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

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

Но на этом история с семью кенигсбергскими мостами не заканчивается. Решение Эйлера было актуально на протяжении долгого времени, но в 1905 году все изменилось. Существует городская легенда, что на одном из светских приемов группа ученых решила подшутить над самим кайзером — императором Вильгельмом II. Тот пыхтел не один час в попытке решить головоломку, пока не включил императорскую смекалку. Так в Кенигсберге появился восьмой мост, который назвали, естественно, Императорским, а что стало с теми учеными-шутниками доподлинно не известно.

Увы, но восьмой мост был разрушен в ходе бомбардировки во время Второй мировой войны. На его опорах уже в 2005 году был построен Юбилейный мост, чье открытие приурочили к 750-летнему юбилею города.