Головоломка из 7 мостов Кенигсберга

Кенигсберг был построен на берегу реки Прегель(Преголя), которая поделила город на четыре отдельных жилых массива. Люди перебирались из 1-го района в иной через семь различных мостов. Согласно легенде, популярным развлечением во время воскресных прогулок были пробы пройти через весь город так, чтобы пересечь каждый мост только один раз. Никто так не выдумал, как это сделать, но это совсем не значит, что задачка не имеет решения.
Им просто необходимо было обратиться к подходящему эксперту, чтобы узнать его.

В 1735 году мэр городка Данцига(сейчас польский Гданьск), размещенного в 120 километрах к западу от Кенигсберга, Карл Леонард Готлиб Эйлер, обратился к Леонарду Эйлеру с письмом, в каком просил о помощи в решении данной задачки от имени местного доктора арифметики по имени Генрих Кюн. Уже тогда Эйлер был известным и очень удачным математиком – он опубликовал свою первую книгу в течение года после чего же письма, а за всю жизнь написал наиболее 500 книжек и статей.
Головоломка из 7 мостов Кенигсберга
Поэтому логично, что поначалу Эйлер поразмыслил, что заниматься решением данной задачки ниже его плюсы, и написал в ответ: «Итак, вы видите, досточтимый сэр этот тип решения фактически не имеет дела к арифметике, и я не понимаю, почему вы обращаетесь с таковой просьбой к математику, а не к кому-то еще, поскольку решение основано только на здравом смысле не зависит ни от 1-го из известных математических принципов».
Но, в конце концов, Элеру и Кюну удалось убедить Эйлера, и он сообразил, что это был совсем новейший тип арифметики – «геометрия положений», сейчас популярная как топология. В топологии четкая форма или размещение объекта не имеют значения. Есть даже древняя шуточка о том, что тополог не в состоянии определить разницу между пончиком и кофейной чашечкой, поскольку оба предмета имеют ровно одно отверстие. О данной совсем новой области арифметики до тех пор только писали, но никто еще не осознавал, какие трудности она способна решать. Семь мостов Кенигсберга были красивым экспериментальным доказательством новой теории, поскольку задачка не требовала каких-то измерений или точных расчетов. Можно превратить сложную карту городка в обычный и понятный граф(схему), не теряя при всем этом никакой принципиальной инфы.
Хотя у кого-либо может возникнуть соблазн решить эту задачу, наметив все вероятные маршруты через город, Эйлер сразу сообразил, что эта стратегия потребует очень много времени не будет работать с иными похожими задачками(что, если в другом городке будет, скажем, двенадцать мостов?). Заместо этого он решил на время отвлечься от мостов и отметил участки суши знаками A, B, C и D. Таковым образом, он теперь мог описать путешествие через мост из района А в район В как АВ, а путешествие из района А через район В район D как АВD. Здесь принципиально отметить, что количество букв в описании маршрута постоянно будет на единицу больше, чем количество пересекаемых мостов. Так, маршрут АВ пересекает один мост, а маршрут АВD – два моста, и так дальше. Эйлер сообразил, что поскольку в Кенигсберге семь мостов, а для того, чтобы пересечь их все, маршрут должен состоять из восьми букв, значит, решение задачки потребует конкретно восьми букв.

Потом он выдумал наиболее общее правило, используя еще наиболее упрощенную схему. Если бы у вас было всего два сухопутных участка, А и В, и вы пересекали мост один раз, то участок А мог бы быть там, где путешествие начиналось, или там, где оно заканчивалось, но вы находились бы на участке А только однажды. Если бы вы пересекали мосты а, b и c по одному разу, то оказались бы на участке А ровно дважды. Это привело к созданию комфортного правила: если у вас имеется четное число мостов, ведущих на один участок суши, вы должны добавить к этому числу единицу, а потом разделить полученную сумму на два, чтобы выяснить, сколько раз этот участок должен употребляться в процессе путешествия.(в данном примере, добавив единицу к количеству мостов, то есть к 3, получаем четыре, а разделив четыре на два получаем два, то есть конкретно дважды в путешествии пересекается участок А).
Этот результат вернул Эйлера к начальной дилемме. Есть пять мостов, которые ведут к участку А, поэтому в восьмибуквенном решении, которое он ищет, его придется пересекать трижды. У участков В, С и D есть по два моста, которые ведут к ним, поэтому любой из них должен пересекаться дважды. Но 3+2+2+2 – это 9, а не 8, хотя по условию необходимо пройти только через 8 участков и пересечь 7 мостов. Это означает, что нереально пройти через весь город Кенигсберг, использовав каждый мост ровно один раз. Иными словами, в данном случае задачка не имеет решения.
Но, как и всякий настоящий математик, Эйлер на этом не тормознул. Он продолжал работать и сделал наиболее общее правило для других городов с иным количеством мостов. Если в городке нечетное количество мостов, то существует обычный метод выяснить, сможете ли вы совершить такое путешествие или нет: если сумма количества возникновений каждой буквы, обозначающей участок земли, на единицу больше, чем количество мостов(как, например, в восьмибуквенном решении, о котором упоминалось ранее), такое путешествие может быть. Если же сумма больше этого числа, оно нереально.
Как насчет четного количества мостов?В данном случае все зависит от того, с чего же начать. Если вы начинаете с участка А и путешествуете по двум мостам, А в вашем решении покажется дважды. Если вы начнете с иной стороны, то А покажется только один раз. Если имеется четыре моста, тогда А возникает трижды, если этот участок был отправной точкой, или дважды, если не был. В общем виде это означает, что, если путешествие не начинается с участка А, он должен пересекаться в дважды наименьшее количество раз, чем число мостов(четыре деленное на два дает два). Если же путешествие начинается с участка А, тогда он должен пересекаться на один раз больше.
Гениальность решения Эйлера заключается даже не в ответе, а в способе, который он применил. Это был один из первых случаев использования теории графов, также известной как теория сетей, очень нужной области арифметики в современном мире, заполненном транспортными, соц и электронными сетями. Что касается Кенигсберга, в городке в конечном итоге возник очередной мост, который сделал решение Эйлера спорным, а потом английские войска разрушили большую часть городка во время 2-ой мировой войны. Сейчас и город и река имеют новейшие наименования, но древная задачка живет в совсем новой области арифметики. 

Похожие публикации


Опрос
БЫСТРО ЛИ ГРУЗИТСЯ САЙТ?