Добавить новость
Август 2011
Сентябрь 2011
Октябрь 2011
Ноябрь 2011
Декабрь 2011
Январь 2012Февраль 2012Март 2012Апрель 2012Май 2012Июнь 2012
Июль 2012
Август 2012
Сентябрь 2012
Октябрь 2012
Ноябрь 2012Декабрь 2012Январь 2013Февраль 2013Март 2013Апрель 2013Май 2013Июнь 2013Июль 2013Август 2013Сентябрь 2013Октябрь 2013Ноябрь 2013Декабрь 2013
Январь 2014
Февраль 2014
Март 2014
Апрель 2014
Май 2014
Июнь 2014Июль 2014Август 2014Сентябрь 2014Октябрь 2014Ноябрь 2014
Декабрь 2014
Январь 2015
Февраль 2015
Март 2015Апрель 2015Май 2015Июнь 2015Июль 2015
Август 2015
Сентябрь 2015
Октябрь 2015
Ноябрь 2015
Декабрь 2015
Январь 2016
Февраль 2016
Март 2016
Апрель 2016
Май 2016Июнь 2016Июль 2016Август 2016Сентябрь 2016
Октябрь 2016
Ноябрь 2016
Декабрь 2016Январь 2017
Февраль 2017
Март 2017Апрель 2017
Май 2017
Июнь 2017Июль 2017
Август 2017
Сентябрь 2017
Октябрь 2017
Ноябрь 2017
Декабрь 2017
Январь 2018
Февраль 2018
Март 2018
Апрель 2018
Май 2018
Июнь 2018
Июль 2018
Август 2018
Сентябрь 2018
Октябрь 2018
Ноябрь 2018Декабрь 2018
Январь 2019
Февраль 2019Март 2019
Апрель 2019
Май 2019Июнь 2019Июль 2019Август 2019Сентябрь 2019Октябрь 2019Ноябрь 2019Декабрь 2019Январь 2020Февраль 2020Март 2020Апрель 2020Май 2020Июнь 2020Июль 2020Август 2020Сентябрь 2020Октябрь 2020Ноябрь 2020Декабрь 2020Январь 2021Февраль 2021Март 2021Апрель 2021Май 2021Июнь 2021Июль 2021Август 2021Сентябрь 2021Октябрь 2021Ноябрь 2021Декабрь 2021Январь 2022Февраль 2022Март 2022Апрель 2022Май 2022
Блоги |

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



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

Им просто нужно было обратиться к подходящему эксперту, чтобы узнать его.


В 1735 году мэр города Данцига (ныне польский Гданьск), расположенного в 120 километрах к западу от Кенигсберга, Карл Леонард Готлиб Эйлер, обратился к Леонарду Эйлеру с письмом, в котором просил о помощи в решении этой задачи от имени местного профессора математики по имени Генрих Кюн. Уже тогда Эйлер был знаменитым и весьма успешным математиком – он опубликовал свою первую книгу в течение года после этого письма, а за всю жизнь написал более 500 книг и статей.





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

Однако, в конце концов, Элеру и Кюну удалось убедить Эйлера, и он понял, что это был совершенно новый тип математики – «геометрия положений», сегодня известная как топология. В топологии точная форма или расположение объекта не имеют значения. Есть даже старая шутка о том, что тополог не в состоянии определить разницу между пончиком и кофейной чашкой, поскольку оба предмета имеют ровно одно отверстие. Об этой совершенно новой области математики до тех пор только писали, но никто еще не понимал, какие проблемы она способна решать. Семь мостов Кенигсберга были прекрасным экспериментальным подтверждением новой теории, поскольку задача не требовала каких-либо измерений или точных расчетов. Можно превратить сложную карту города в простой и понятный граф (схему), не теряя при этом никакой важной информации.

Хотя у кого-то может возникнуть соблазн решить эту задачу, наметив все возможные маршруты через город, Эйлер сразу осознал, что эта стратегия потребует слишком много времени и не будет работать с другими схожими задачами (что, если в другом городе будет, скажем, двенадцать мостов?). Вместо этого он решил на время отвлечься от мостов и пометил участки суши буквами A, B, C и D. Таким образом, он теперь мог описать путешествие через мост из района А в район В как АВ, а путешествие из района А через район В район D как АВD. Здесь важно отметить, что количество букв в описании маршрута всегда будет на единицу больше, чем количество пересекаемых мостов. Так, маршрут АВ пересекает один мост, а маршрут АВD – два моста, и так далее. Эйлер понял, что поскольку в Кенигсберге семь мостов, а для того, чтобы пересечь их все, маршрут должен состоять из восьми букв, значит, решение задачи потребует именно восьми букв.





Затем он придумал более общее правило, используя еще более упрощенную схему. Если бы у вас было всего два сухопутных участка, А и В, и вы пересекали мост один раз, то участок А мог бы быть там, где путешествие начиналось, или там, где оно заканчивалось, но вы находились бы на участке А только однажды. Если бы вы пересекали мосты а, b и c по одному разу, то оказались бы на участке А ровно два раза. Это привело к созданию удобного правила: если у вас имеется четное число мостов, ведущих на один участок суши, вы должны добавить к этому числу единицу, а затем разделить полученную сумму на два, чтобы выяснить, сколько раз этот участок должен использоваться в ходе путешествия. (в данном примере, добавив единицу к количеству мостов, то есть к 3, получаем четыре, а разделив четыре на два получаем два, то есть именно дважды в путешествии пересекается участок А).

Этот результат вернул Эйлера к первоначальной проблеме. Есть пять мостов, которые ведут к участку А, поэтому в восьмибуквенном решении, которое он ищет, его придется пересекать три раза. У участков В, С и D есть по два моста, которые ведут к ним, поэтому каждый из них должен пересекаться дважды. Но 3+2+2+2 – это 9, а не 8, хотя по условию нужно пройти только через 8 участков и пересечь 7 мостов. Это означает, что невозможно пройти через весь город Кенигсберг, использовав каждый мост ровно один раз. Другими словами, в данном случае задача не имеет решения.

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

А как насчет четного количества мостов? В этом случае все зависит от того, с чего начать. Если вы начинаете с участка А и путешествуете по двум мостам, А в вашем решении появится дважды. Если вы начнете с другой стороны, то А появится только один раз. Если имеется четыре моста, тогда А появляется три раза, если этот участок был отправной точкой, или два раза, если не был. В общем виде это означает, что, если путешествие не начинается с участка А, он должен пересекаться вдвое меньшее количество раз, чем число мостов (четыре деленное на два дает два). Если же путешествие начинается с участка А, тогда он должен пересекаться на один раз больше.

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








Russian.city

Читайте также

Интернет |

Учёные объявили успешной пересадку почек свиньи человеку

Интернет |

Токсичные "Вечные химикаты" скоро перестанут быть вечными

Интернет |

Врачи вылечили тяжелую форму детской эпилепсии


Персональные новости

News24.pro и Life24.pro — таблоиды популярных новостей за 24 часа, сформированных по темам с ежеминутным обновлением. Все самостоятельные публикации на наших ресурсах бесплатны для авторов Ньюс24.про и Ньюс-Лайф.ру.




Разместить свою новость локально в любом городе по любой тематике (и даже, на любом языке мира) можно ежесекундно с мгновенной публикацией самостоятельно — здесь.

Новости России

Russian.city

Музыкальные новости
Баста

Названа дата выхода документального фильма о творческом пути Басты



Персональные новости

Новости тенниса
Уимблдон

WTA вслед за ATP лишила Уимблдон рейтинговых очков из-за недопуска российских теннисистов