Задача Эйлера Википедия
Запрос «Семь мостов Кёнигсберга» перенаправляется сюда; о самих городских мостах см. Мосты Кёнигсберга. Кёнигсберг в XVII—XVIII вв. (карта 1652 года)Семь мостов Кёнигсберга, или Задача о семи кёнигсбергских мостах (лат. Problema Regiomontanum de septem pontibus, нем. Königsberger Brückenproblem[1]) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году математиком Леонардом Эйлером[2][3][4], доказавшим, что это невозможно, и изобретшим таким образом эйлеровы циклы.
История
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем городским мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Джованни Джакобо Маринони[de] от 13 марта 1736 года. В этом письме Эйлер приводит правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя»[2]. В письме Карлу Готлибу Элеру[en] от 3 апреля 1736 года Эйлер обосновывает найденное им правило[3], а позднее на эту тему Эйлер публикует статью в научном журнале Петербургской академии наук «Commentarii Academiae Scientiarum Imperialis Petropolitanae»[4].
Решение задачи по Леонарду Эйлеру
На упрощённой схеме города (графе) мостам соответствуют линии (ребра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
- Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
- Если все вершины графа чётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
- Если ровно две вершины графа нечётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом нужно начинать с одной из нечётных вершин и завершить его в другой нечётной вершине.
- Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все) — следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Дальнейшая история
В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построен Юбилейный мост. Всего до 2016 года в Калининграде было восемь мостов.
См. также
Примечания
Литература
wikiredia.ru
Задача Эйлера | Социальная сеть работников образования
Слайд 1
Задача Эйлера Автор презентации: Бондаренко Антон, ученик 10 Б Руководитель Стеняева Наталья Сергеевна Г.Выборг 2012 год Министерство образование Российской Федерации МБОУ «Средняя школа № 12» г. Выборг Ленинградская областьСлайд 2
Цели презентации: Кратко рассказать об авторе задачи великом математике Леонард Эйлер Выделить основные утверждения, которые доказываются в задаче Эйлера Показать решение этих утверждений
Слайд 3
Леонард Эйлер 1707 – 1783 Леонард Эйлер – один из величайших ученых, внесший огромный вклад в развитие отечественной и науки вообще. За свою жизнь написал более 800 работ по направлениям: математический анализ, дифференциальная геометрия, теория чисел, приближенным вычислениям, теории музыки, кораблестроению , оптике, баллистике и другие. Его учениками являются первые российские академики Котельников и Румовский. Работал в Петербургской Академии наук с 1731 – 1741, а также с 1766.
Слайд 4
Задача Эйлера: Доказать, что в произвольном треугольнике: 1) точки симметричные точке Н пересечения высот (или их продолжений) относительно сторон треугольника и из середин, лежат на описанной окружности; 2) середины сторон, основания высот и середины отрезков, соединяющих точку Н с вершинами, лежат на одной окружности, центром которой является середина отрезка, соединяющего точку Н с центром описанной окружности, а её радиус в два раза меньше радиуса описанной окружности (окружности Эйлера) 3) точка пересечения медиан лежит на отрезке, соединяющем точку Н с центром описанной окружности, и делит этот отрезок в отношении 1:2, считая от центра описанной окружности (прямая, на которой лежат четыре точки – точка Н , точка пересечения медиан, центр описанной окружности и центр окружности Эйлера, называется прямой Эйлера) 4) точки, симметричные центру описанной окружности относительно прямых, содержащих средние линии треугольника, лежат на окружности Эйлера
Слайд 5
B A C A 1 A 2 A 4 A 5 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G ∆ ABC – данный треугольник O 9 — центр окружности Эйлера OR — описанная окружность СС 1 , АА 1 ВВ 1 – медианы, G – точка их пересечения СС 2 , АА 2 ВВ 2 – высоты А 4 С 4 В 4 – точки, симметричные точке Н относительно сторон треугольника А 5 С 5 В 5 – точки, симметричные точке Н относительно середин этих сторон треугольника А 3 С 3 В 3 – середины отрезков АН , ВН и СН ОН — прямая Эйлера
Слайд 6
Если угол А = 90 о , то точки Н, В 4 и С 4 совпадают с точкой А , точка В 5 с точкой С , а точка С 5 – с точкой В . Угол ВА 4 С = ВА 5 С= А, то А, А 4 и А 5 лежат на окружности с диаметром ВС = > А 5 ,В 4 ,В 5 , С 4 ,С 5 лежат на окружности описанной треугольника АВС B A C A 1 A 2 A 4 A 5 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G Докажем утверждение 1
Слайд 7
Допустим ∆ АВС не является прямоугольным. Поскольку углы АВ 2 Н = АС 2 Н = 90 ₀ , то точки В 2 и С 2 лежат на окружности с диаметром АН = > вписанные углы и ВНС либо равны, либо их сумма равна 180 о . В обоих случаях sin ВНС = sin ВАС . Пусть R 1 – радиус окружности, описанной около ∆ НВС . По теореме ВС =2 R 1 sin ВНС = 2 Rsin ВАС . Но sin ВНС = sin ВАС, значит R 1 =R = > окружности описанные около ∆ АВС и ∆ НВС , симметричны относительно прямой ВС и относительно середины ВС . Точка Н лежит на окружности описанной около ∆ НВС , значит точки А 4 и А 5 лежат на окружности около АВС . Аналогично для В 4 , В 5 , С 4 , С 5 . A 5 B A C A 1 A 2 A 4 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G Утверждение 1 доказано
Слайд 8
B A C A 1 A 2 A 4 A 5 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G Докажем утверждение 2 Рассмотрим центральное подобие с центром Н и коэффициентом 1:2 При этом подобии окружность переходит в окружность радиуса R :2, центр О 9 является серединой отрезка ОН , а точки В 4 , В 5 , С 4 , С 5 , А 5 , А 4 , А , В , С – переходят в точки А 1 , B 1 , С 1 , А 2 , В 2 , С 2 , А 3 , В 3 , и С 3 = > лежат на окружности с центром О 9 и радиусом R:2 Утверждение 2 доказано
Слайд 9
B A C A 1 A 2 A 4 A 5 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G Докажем утверждение 3 Рассмотрим центральное подобие с центром G и коэффициентом -1:2, при этом подобие вершины АВС перейдут в середины А 1 , В 1 и С 1 , противоположных сторон. Из этого следует, что прямые содержащие высоты перейдут в прямые перпендикулярные к его сторонам, т. е. в серединные перпендикуляры сторон. Значит, точка Н перейдет в центр окружности О . Это означает, что точка G лежит на ОН и делит его в отношении 1:2. считая от точки О . Утверждение 3 доказано
Слайд 10
B A C A 1 A 2 A 4 A 5 A 3 C 3 C 4 C 2 C 1 C 5 B 3 B 2 B 1 B 5 B 4 R H O 9 O G Докажем утверждение 4 Из доказанного в утверждение 3 следует: А) окружность описанная около ∆ АВС , переходит в окружность Эйлера Утверждение 4 доказано Задача Эйлера решена! Б) точки А 4 , В 4 и С 4 , симметричные точке Н относительно прямых ВС, СА и АВ, переходят в точки А 6 , В 6 и С 6 окружности Эйлера, симметричные точке относительно прямых В 1 С 1 , С 1 А 1 и А 1 В 1 . Таким образом А 6 , В 6 и С 6 , лежат на окружности Эйлера
nsportal.ru
Project Euler — решайте алгоритмические задачи и смотрите как это делали другие 30к участников на огромном количестве языков.
Пару-тройку месяцев назад наткнулся на замечательный ресурс Project Euler.Project Euler представляет собой набор математических задач, которые вам предлагается решить хоть программным методом, хоть на бумаге.
Для участия в проекте надо пройти быструю регистрацию, после чего можно смело штурмовать алгоритмы.
подробно — внутри
Изюминка ресурса в том, что вы можете решить задачу на любом удобном для вас языке, надо только вписать в форму правильный ответ.
Вы можете посмотреть как данную задачу решили на почти всех живых языках программирования, увидеть красивые решения и грубый брутофорс)
По мере прохождения сложность задач увеличивается.
Посоревноваться в скорости алгоритма и просто обсудить математический аспект задачи.
Выдержки из статистики:
| язык | количество участников |
| C/C++ | 3726 |
| python | 2900 |
| Java | 1782 |
| C# | 917 |
| Assembler | 37 |
| F# | 97 |
| Haskell | 945 |
| Fortran | 32 |
| Nemerle | 8 |
| Ada | 16 |
| R | 7 |
| Prolog | 2 |
| Boo | 6 |
| PHP | 425 |
| Pencil/Paper | 291 |
| Ruby | 804 |
Вот так, к примеру, выглядит самая первая задача из 200штук:
Add all the natural numbers below one thousand that are multiples of 3 or 5.
Вот так 50-я
Which prime, below one-million, can be written as the sum of the most consecutive primes?
100я
Investigate the optimum polynomial function to model the first k terms of a given sequence.
Удачного погружения
habr.com
О Проекте Эйлера
О проекте
Что такое Проект «Эйлер»?
Проект «Эйлер» — это набор интригующих задач по математике и программированию, для решения которых, однако, недостаточно одной только математической интуиции. Разумеется, математика поможет прийти к красивому и элегантному решению, но для успешного решения большинства задач без навыков программирования не обойтись.
Основная мотивация для создания и поддержки проекта — предоставить пытливым умам платформу для погружения в незнакомые области и добавить немного веселья в процесс изучения новых идей.
Для кого предназначены задачи?
Целевая аудитория проекта включает в себя студентов, которым мало университетского курса, не-математиков, которым, тем не менее, интересна математика, а также профессионалов, которым хотят быть в хорошей математической форме.
Значит, задачи может решить кто угодно?
Задачи эти разной степени сложности, и большинство их предполагает индуктивное обучение. То есть очередная решённая задача открывает нечто новое, что позволит подобраться к ранее недоступной задаче. Таким образом упорный участник проекта будет медленно, но верно продвигаться по списку задач.
С чего мне начать?
Это зависит от ваших навыков и способностей. В таблице «Задачи» можно посмотреть сколько человек уже решило каждую из них. В общем случае — чем больше людей решило задачу, тем она проще.
Я написал программу, теперь придётся ждать результата вычислений пару дней?
Разумеется, нет! Каждая задача подчиняется «правилу одной минуты», которое гласит: несмотря на то, что на построение алгоритма решения могут уйти часы, эффективная реализация позволяет получить ответ на компьютере средней вычислительной мощности меньше, чем за одну минуту.
А если моя программа проработала дольше минуты, решение не засчитывается?
Засчитывается. Однако в идеале это должно побудить вас вернуться к задаче и проверить, можно ли как-то улучшить решение. Как только вы решите задачу, вы получите доступ к ветке форума с её обсуждением, где могут найтись советы по отпимизации от других участников.
Можно ли пользоваться поисковиком в процессе решения?
Многие задачи таят в себе настоящие математические сокровища, и использование интернета для их поиска никоим образом не возбраняется. Но существует чёткая граница между собственным исследованием и копипастой решения с другого сайта. Чему вы научитесь, списывая с решебника?
Я перепроверил свою программу десять раз, а ответ всё равно не принимается! Может, у вас там ошибка?
Мы постоянно выкладываем новые задачи, поэтому в самые свежие вполне могут закрасться мелкие ошибки, или же условие может быть сформулировано недостаточно чётко. Но согласитесь, что когда большинство попадает в цель, а один стрелок промахивается десять раз подряд, вряд ли ему придёт в голову стрелять себе в ногу и заключать, что раз оружие работает как нужно, то во всём виновата мишень.
Можете дать парочку советов по решению задач?
Внимательно прочитайте условие и изучите приведённые примеры. Карандаш и бумага помогут лучше понять идею, лежащую в основе задачи. Если идея эта для вас нова, обратитесь к дополнительной литературе и интернету; в условии могут содержаться подсказки, на что обратить внимание. Попробуйте написать программу для простых случаев и удостоверьтесь, что она правильно работает на тестовых данных из условия, это послужит знаком того, что вы вникли в суть задачи и продвигаетесь в верном направлении. Попытайтесь оценить время, которое потребуется для получения окончательного ответа, и если оно явно будет больше минуты, пересмотрите свою стратегию.
Я столько всего изучил, пока решал задачу ХХХ, можно мне публиковать своё решение?
На самом деле, ответ заключается в самом вопросе. Ничто не сравнится с удовлетворением от решения задачи, над которой вы ломали голову не один час. Конечно, желая поделиться своим озарением с другими, вы действуете из лучших побуждений, но увы, скорее всего вы оказывате своим читателям медвежью услугу. Настоящее обучение — это активный процесс, одно дело наблюдать за процессом, и совсем другое — переживать этот опыт самому. Пожалуйста, не лишайте других столь ценного удовольствия.
Кто это всё придумал?
Проект «Эйлер» был основан Colin Hughes (aka euler) в октябре 2001 как подраздел сайта mathschallenge.net. Кто бы мог подумать, что такие задачи окажутся настолько популярными? Поскольку количество пользователей продолжало неуклонно расти, Проект «Эйлер» переехал на отдельный домен в 2006 году.
Кто поддерживает работу Проекта «Эйлер»?
Идеи для новых задач приходят к нам от участников проекта. Затем над ними работает команда трудолюбивых и талантливых математиков и программистов. Проще говоря, Проект живёт благодаря своим участникам.
Благодарности
За создание сайта — Виталию aka Vitalg.
За перевод задач — Элану aka Konnektor, Виталию aka Stumbler.
За адскость — Антону aka antox(z*)
euler.jakumo.org