- 25,090
- 46
- 8 Ноя 2022
Она же скрывается в теории чисел, геометрии и теории графов — и никто не знает, почему она такая неуловимая.
Задача об одиноком бегуне формулируется очень просто. Несколько человек стартуют из одной точки на круговой дорожке и бегут с разными постоянными скоростями. Математики спрашивают: найдётся ли для каждого бегуна момент, когда между ним и любым другим участником по дорожке будет не меньше 1/N круга, где N - общее число бегунов? Если такой момент наступает, бегун считается одиноким. Несмотря на простую постановку, чем больше участников, тем труднее доказать, что условие будет одновременно верно для каждого.
Тот же вопрос возникает и в других разделах математики. Его можно переформулировать на языке теории чисел , геометрии и теории графов. В одной версии речь идёт о прямой, проходящей через бесконечную сетку препятствий. В другой - о траекториях на бильярдном столе. В третьей о свойствах графов и сетевых структур. Поэтому задача про бегунов давно стала точкой пересечения нескольких математических направлений.
Интересно, что история началась вовсе не с бега. В 1960-е годы математиков интересовала задача о приближении иррациональных чисел , например числа π, рациональными дробями. Такая тема важна для теории чисел и её приложений. Тогда аспирант Йорг Вилльс высказал гипотезу: один старый способ таких приближений уже оптимален, и улучшить его нельзя. В 1998 году другие математики переписали ту же идею в форме задачи про бегунов. Так появилась современная версия гипотезы.
Позже выяснилось, что у неё есть и ещё одна эквивалентная формулировка. Нужно представить бесконечную клетчатую плоскость. В центре каждой клетки расположен маленький квадрат. Из одного из узлов сетки проводится прямая, не строго вертикальная и не строго горизонтальная. Дальше возникает вопрос: насколько большими могут быть такие квадраты, прежде чем любая такая прямая обязательно заденет один из них? По сути, речь идёт о том же самом вопросе, что и в задаче об одиноком бегуне.
<!--'start_frame_cache_Zg1Ab0'--><div class="banner-detailed"><div class="banner-detailed__shell"><div class="banner-detailed__title">Прокачай резюме бесплатно: митапы, вебинары, нетворкинг в ИБ <span>Стать экспертом</span><div class="banner-detailed__arrow"><svg viewBox="0 0 40 40" fill="none" xmlns="http://www.w3.org/2000/svg"><path d="M20.5375 34.4392L22.465 31.7392C22.5739 31.5872 22.7145 31.4607 22.8772 31.3684C23.0399 31.2762 23.2207 31.2205 23.407 31.2052C23.5934 31.1898 23.7809 31.2152 23.9564 31.2796C24.132 31.344 24.2915 31.4458 24.4237 31.578L29.6025 36.758C30.0787 37.2333 30.724 37.5002 31.3969 37.5002C32.0697 37.5002 32.715 37.2333 33.1912 36.758L36.7575 33.1917C37.2328 32.7155 37.4998 32.0702 37.4998 31.3973C37.4998 30.7245 37.2328 30.0792 36.7575 29.603L31.5775 24.4242C31.4453 24.2919 31.3435 24.1325 31.2791 23.9569C31.2147 23.7814 31.1893 23.5939 31.2047 23.4075C31.22 23.2211 31.2757 23.0404 31.368 22.8777C31.4602 22.715 31.5867 22.5743 31.7387 22.4655L34.4387 20.538C34.6405 20.3939 34.7965 20.1947 34.8878 19.9641C34.9791 19.7336 35.0018 19.4816 34.9534 19.2385C34.9049 18.9953 34.7873 18.7713 34.6146 18.5934C34.442 18.4155 34.2216 18.2912 33.98 18.2355L13.5112 13.5117L18.235 33.9805C18.2907 34.2221 18.415 34.4425 18.5929 34.6151C18.7708 34.7878 18.9948 34.9054 19.238 34.9539C19.4812 35.0023 19.7331 34.9795 19.9637 34.8882C20.1942 34.7969 20.3934 34.641 20.5375 34.4392Z" fill="#FFD98C"></path><path d="M34.0751 37.6413C33.3582 38.3389 32.3973 38.7293 31.397 38.7293C30.3966 38.7293 29.4358 38.3389 28.7189 37.6413L23.4826 32.4663L21.5539 35.165C21.2699 35.5626 20.8773 35.8698 20.423 36.0497C19.9688 36.2295 19.4723 36.2744 18.9931 36.179C18.514 36.0836 18.0726 35.8518 17.7219 35.5117C17.3713 35.1715 17.1263 34.7373 17.0164 34.2613L12.2926 13.7925C12.2447 13.5858 12.2502 13.3702 12.3086 13.1662C12.367 12.9622 12.4764 12.7764 12.6264 12.6263C12.7765 12.4763 12.9623 12.3669 13.1663 12.3085C13.3703 12.2501 13.5859 12.2446 13.7926 12.2925L34.2614 17.0175C34.7374 17.1271 35.1717 17.3719 35.512 17.7225C35.8523 18.073 36.0841 18.5144 36.1795 18.9935C36.275 19.4726 36.23 19.9691 36.0501 20.4233C35.8701 20.8775 35.5628 21.27 35.1651 21.5538L32.4614 23.54L37.6414 28.7188C38.3498 29.43 38.7476 30.393 38.7476 31.3969C38.7476 32.4008 38.3498 33.3637 37.6414 34.075L34.0751 37.6413ZM35.8751 30.4863L30.6951 25.3075C30.4344 25.047 30.2336 24.7328 30.1068 24.3868C29.9799 24.0407 29.9299 23.6712 29.9604 23.3039C29.9908 22.9366 30.101 22.5804 30.2831 22.26C30.4653 21.9396 30.7151 21.6628 31.0151 21.4488L33.6989 19.4488L15.1851 15.1763L19.5001 33.7275L19.5139 33.7113L21.4414 31.0125C21.6555 30.7124 21.9325 30.4626 22.253 30.2805C22.5735 30.0983 22.9298 29.9882 23.2972 29.9577C23.6646 29.9272 24.0342 29.9772 24.3803 30.1041C24.7264 30.231 25.0407 30.4318 25.3014 30.6925L30.4864 35.875C30.728 36.1163 31.0555 36.2518 31.397 36.2518C31.7385 36.2518 32.066 36.1163 32.3076 35.875L35.8751 32.3075C36.1161 32.0657 36.2514 31.7383 36.2514 31.3969C36.2514 31.0555 36.1161 30.728 35.8751 30.4863ZM8.14636 9.385C7.98292 9.38706 7.82069 9.35675 7.66901 9.29583C7.51733 9.2349 7.37921 9.14455 7.26261 9.03L4.58011 6.3475C4.35242 6.11175 4.22643 5.796 4.22927 5.46825C4.23212 5.1405 4.36358 4.82699 4.59534 4.59523C4.8271 4.36347 5.14062 4.23201 5.46836 4.22916C5.79611 4.22631 6.11186 4.3523 6.34761 4.58L9.03012 7.2625C9.20107 7.43787 9.31674 7.65959 9.36277 7.90013C9.4088 8.14068 9.38315 8.38944 9.28901 8.61553C9.19487 8.84162 9.03639 9.03508 8.83325 9.17188C8.63011 9.30867 8.39126 9.38278 8.14636 9.385ZM17.9726 9.03C17.7362 9.26044 17.419 9.3894 17.0889 9.3894C16.7587 9.3894 16.4416 9.26044 16.2051 9.03C15.9708 8.79559 15.8391 8.47771 15.8391 8.14625C15.8391 7.8148 15.9708 7.49691 16.2051 7.2625L18.8876 4.58C19.0029 4.46061 19.1409 4.36538 19.2934 4.29987C19.4459 4.23436 19.6099 4.19988 19.7759 4.19844C19.9418 4.197 20.1064 4.22862 20.2601 4.29147C20.4137 4.35432 20.5532 4.44714 20.6706 4.56451C20.788 4.68187 20.8808 4.82144 20.9436 4.97506C21.0065 5.12868 21.0381 5.29328 21.0367 5.45925C21.0352 5.62523 21.0008 5.78925 20.9352 5.94176C20.8697 6.09426 20.7745 6.23219 20.6551 6.3475L17.9726 9.03ZM6.34761 20.655C6.11146 20.886 5.79423 21.0154 5.46386 21.0154C5.1335 21.0154 4.81627 20.886 4.58011 20.655C4.34578 20.4206 4.21413 20.1027 4.21413 19.7713C4.21413 19.4398 4.34578 19.1219 4.58011 18.8875L7.26261 16.205C7.37792 16.0856 7.51585 15.9904 7.66836 15.9249C7.82086 15.8594 7.98489 15.8249 8.15086 15.8234C8.31684 15.822 8.48144 15.8536 8.63506 15.9165C8.78868 15.9793 8.92824 16.0721 9.04561 16.1895C9.16297 16.3069 9.25579 16.4464 9.31864 16.6001C9.38149 16.7537 9.41312 16.9183 9.41168 17.0843C9.41024 17.2502 9.37575 17.4143 9.31024 17.5668C9.24473 17.7193 9.1495 17.8572 9.03012 17.9725L6.34761 20.655ZM12.6176 7.54375C12.2861 7.54375 11.9682 7.41205 11.7337 7.17763C11.4993 6.94321 11.3676 6.62527 11.3676 6.29375V2.5C11.3676 2.16848 11.4993 1.85054 11.7337 1.61612C11.9682 1.3817 12.2861 1.25 12.6176 1.25C12.9491 1.25 13.2671 1.3817 13.5015 1.61612C13.7359 1.85054 13.8676 2.16848 13.8676 2.5V6.29375C13.8676 6.62527 13.7359 6.94321 13.5015 7.17763C13.2671 7.41205 12.9491 7.54375 12.6176 7.54375ZM2.50011 11.3675H6.29387C6.62539 11.3675 6.94333 11.4992 7.17775 11.7336C7.41217 11.968 7.54387 12.286 7.54387 12.6175C7.54387 12.949 7.41217 13.267 7.17775 13.5014C6.94333 13.7358 6.62539 13.8675 6.29387 13.8675H2.50011C2.16859 13.8675 1.85065 13.7358 1.61623 13.5014C1.38181 13.267 1.25011 12.949 1.25011 12.6175C1.25011 12.286 1.38181 11.968 1.61623 11.7336C1.85065 11.4992 2.16859 11.3675 2.50011 11.3675Z" fill="#272727"></path></svg> <!--'end_frame_cache_Zg1Ab0'--> Для малого числа участников задача решается сравнительно легко. Случаи с двумя и тремя бегунами доказываются элементарно. Для четырёх участников доказательство получили ещё в 1970-е годы. Дальше продвижение шло медленно, и к 2007 году математики сумели закрыть случаи до семи бегунов включительно. После этого наступил долгий перерыв. Почти двадцать лет никто не мог сделать следующий шаг.
Для отдельных случаев математики придумывали остроумные приёмы, но общего метода долго не было. В одном доказательстве помогали инструменты теории чисел , в другом геометрия, в третьем теория графов. Подход, который работал для одного значения, мог оказаться бесполезным для следующего. Поэтому каждое новое продвижение почти всегда требовало отдельного решения.
К середине 2000-х удалось хотя бы сократить число случаев, которые нужно проверять. Исследователи поняли, что не обязательно разбирать все возможные скорости, включая дробные и иррациональные. Достаточно доказать гипотезу для целых скоростей, и тогда общий случай последует автоматически. Такая замена сильно упростила задачу, но не сняла проблему полностью, потому что даже целочисленных наборов остаётся бесконечно много.
В 2015 году важный шаг сделал Теренс Тао. Он показал , что для фиксированного числа бегунов не нужно отдельно рассматривать очень большие скорости. Если гипотеза верна для скоростей до определённого порога, то она верна вообще для всех скоростей. Тем самым задача хотя бы теоретически сводилась к конечному числу проверок.
Однако на практике и такое упрощение почти не помогало. Даже после ограничения сверху число возможных наборов скоростей оставалось огромным. Перебор всех вариантов был слишком тяжёлым. Нужно было не просто сократить список, а резко сузить круг действительно важных случаев.
Именно это в прошлом году сделал Матьё Розенфельд из лаборатории информатики, робототехники и микроэлектроники в Монпелье. Он посмотрел на задачу с другой стороны. Вместо попытки сразу доказать гипотезу исследователь спросил: какими должны быть скорости, если гипотеза неверна? Иначе говоря, как выглядел бы контрпример, в котором хотя бы один бегун никогда не оказывается одиноким?
Выяснилось, что такой гипотетический контрпример должен удовлетворять очень жёстким арифметическим условиям. Розенфельд с помощью компьютерной программы и методов теории чисел показал: если взять произведение всех скоростей, то для контрпримера это произведение должно делиться на определённый набор простых чисел. Такой результат резко ограничил число возможных плохих случаев.
Дальше Розенфельд объединил этот вывод с идеей Тао о пороге. Он переписал условие уже через произведение скоростей. Получилось следующее: если гипотеза верна для всех произведений до некоторой границы, то она верна вообще всегда. Значит, любой контрпример, если бы он существовал, пришлось бы искать ниже этого порога. Но ранее уже было показано, что произведение скоростей в контрпримере должно делиться на слишком большой набор простых чисел , а значит, само это произведение неизбежно выходит далеко за пределы допустимой границы.
В результате возникло противоречие. Контрпример должен был бы одновременно быть и сравнительно маленьким, и очень большим. Такое невозможно. Значит, для восьми бегунов контрпримеров нет, и гипотеза верна. Так математики впервые за много лет продвинулись дальше случая с семью участниками.
На этом развитие не остановилось. Работу Розенфельда увидел Ноа Кравиц из Оксфорда и показал статью студенту второго курса Полу Тракултонгчаю, с которым занимался. Кравиц предложил ему рассмотреть следующий случай, то есть девять бегунов. Тракултонгчай взял за основу общий подход Розенфельда, но сумел заметно улучшить вычислительную часть.
Он разработал более эффективный способ находить простые делители , которые должен был бы иметь любой контрпример. Благодаря этому удалось быстрее исключить все возможные плохие случаи не только для девяти, но и сразу для десяти бегунов. В обоих вариантах гипотеза тоже оказалась верной. При этом Розенфельд независимо получил доказательство для девяти участников почти одновременно, всего через несколько дней после молодого коллеги из Оксфорда.
Для математического сообщества этот результат особенно важен по одной причине. Раньше каждый новый случай обычно требовал отдельной идеи. Теперь один и тот же общий подход позволил закрыть сразу три новых значения: восемь, девять и десять бегунов. Поэтому исследователи увидели в этой работе не просто удачное частное решение, а возможный путь к более общей стратегии.
Полного доказательства для любого числа участников пока нет. Более того, нынешние методы уже упираются в пределы вычислительных возможностей. Для одиннадцати бегунов подход Розенфельда и Тракултонгчая оказывается слишком тяжёлым. Сами авторы новых результатов считают, что для следующего шага, скорее всего, понадобится другой взгляд на задачу.
Осторожность сохраняется и по другой причине. Хотя гипотеза подтверждена для всё большего числа случаев, математики пока не могут с уверенностью сказать, что она верна для любого N. Цепочка частных доказательств выглядит впечатляюще, но общего ответа всё ещё нет. В подобных задачах именно здесь проходит граница между серьёзным прогрессом и окончательным решением.
Тем не менее ситуация явно изменилась. После долгого застоя появились новые доказательства, новый метод и ощущение, что задача снова сдвинулась с места. Осенью в Ростоке планируют специальный семинар по гипотезе одинокого бегуна. Организаторы хотят собрать специалистов из разных областей, где возникает эта проблема, чтобы свести вместе подходы теории чисел, геометрии, теории графов и вычислительной математики.
Задача об одиноком бегуне формулируется очень просто. Несколько человек стартуют из одной точки на круговой дорожке и бегут с разными постоянными скоростями. Математики спрашивают: найдётся ли для каждого бегуна момент, когда между ним и любым другим участником по дорожке будет не меньше 1/N круга, где N - общее число бегунов? Если такой момент наступает, бегун считается одиноким. Несмотря на простую постановку, чем больше участников, тем труднее доказать, что условие будет одновременно верно для каждого.
Тот же вопрос возникает и в других разделах математики. Его можно переформулировать на языке теории чисел , геометрии и теории графов. В одной версии речь идёт о прямой, проходящей через бесконечную сетку препятствий. В другой - о траекториях на бильярдном столе. В третьей о свойствах графов и сетевых структур. Поэтому задача про бегунов давно стала точкой пересечения нескольких математических направлений.
Интересно, что история началась вовсе не с бега. В 1960-е годы математиков интересовала задача о приближении иррациональных чисел , например числа π, рациональными дробями. Такая тема важна для теории чисел и её приложений. Тогда аспирант Йорг Вилльс высказал гипотезу: один старый способ таких приближений уже оптимален, и улучшить его нельзя. В 1998 году другие математики переписали ту же идею в форме задачи про бегунов. Так появилась современная версия гипотезы.
Позже выяснилось, что у неё есть и ещё одна эквивалентная формулировка. Нужно представить бесконечную клетчатую плоскость. В центре каждой клетки расположен маленький квадрат. Из одного из узлов сетки проводится прямая, не строго вертикальная и не строго горизонтальная. Дальше возникает вопрос: насколько большими могут быть такие квадраты, прежде чем любая такая прямая обязательно заденет один из них? По сути, речь идёт о том же самом вопросе, что и в задаче об одиноком бегуне.
<!--'start_frame_cache_Zg1Ab0'--><div class="banner-detailed"><div class="banner-detailed__shell"><div class="banner-detailed__title">Прокачай резюме бесплатно: митапы, вебинары, нетворкинг в ИБ <span>Стать экспертом</span><div class="banner-detailed__arrow"><svg viewBox="0 0 40 40" fill="none" xmlns="http://www.w3.org/2000/svg"><path d="M20.5375 34.4392L22.465 31.7392C22.5739 31.5872 22.7145 31.4607 22.8772 31.3684C23.0399 31.2762 23.2207 31.2205 23.407 31.2052C23.5934 31.1898 23.7809 31.2152 23.9564 31.2796C24.132 31.344 24.2915 31.4458 24.4237 31.578L29.6025 36.758C30.0787 37.2333 30.724 37.5002 31.3969 37.5002C32.0697 37.5002 32.715 37.2333 33.1912 36.758L36.7575 33.1917C37.2328 32.7155 37.4998 32.0702 37.4998 31.3973C37.4998 30.7245 37.2328 30.0792 36.7575 29.603L31.5775 24.4242C31.4453 24.2919 31.3435 24.1325 31.2791 23.9569C31.2147 23.7814 31.1893 23.5939 31.2047 23.4075C31.22 23.2211 31.2757 23.0404 31.368 22.8777C31.4602 22.715 31.5867 22.5743 31.7387 22.4655L34.4387 20.538C34.6405 20.3939 34.7965 20.1947 34.8878 19.9641C34.9791 19.7336 35.0018 19.4816 34.9534 19.2385C34.9049 18.9953 34.7873 18.7713 34.6146 18.5934C34.442 18.4155 34.2216 18.2912 33.98 18.2355L13.5112 13.5117L18.235 33.9805C18.2907 34.2221 18.415 34.4425 18.5929 34.6151C18.7708 34.7878 18.9948 34.9054 19.238 34.9539C19.4812 35.0023 19.7331 34.9795 19.9637 34.8882C20.1942 34.7969 20.3934 34.641 20.5375 34.4392Z" fill="#FFD98C"></path><path d="M34.0751 37.6413C33.3582 38.3389 32.3973 38.7293 31.397 38.7293C30.3966 38.7293 29.4358 38.3389 28.7189 37.6413L23.4826 32.4663L21.5539 35.165C21.2699 35.5626 20.8773 35.8698 20.423 36.0497C19.9688 36.2295 19.4723 36.2744 18.9931 36.179C18.514 36.0836 18.0726 35.8518 17.7219 35.5117C17.3713 35.1715 17.1263 34.7373 17.0164 34.2613L12.2926 13.7925C12.2447 13.5858 12.2502 13.3702 12.3086 13.1662C12.367 12.9622 12.4764 12.7764 12.6264 12.6263C12.7765 12.4763 12.9623 12.3669 13.1663 12.3085C13.3703 12.2501 13.5859 12.2446 13.7926 12.2925L34.2614 17.0175C34.7374 17.1271 35.1717 17.3719 35.512 17.7225C35.8523 18.073 36.0841 18.5144 36.1795 18.9935C36.275 19.4726 36.23 19.9691 36.0501 20.4233C35.8701 20.8775 35.5628 21.27 35.1651 21.5538L32.4614 23.54L37.6414 28.7188C38.3498 29.43 38.7476 30.393 38.7476 31.3969C38.7476 32.4008 38.3498 33.3637 37.6414 34.075L34.0751 37.6413ZM35.8751 30.4863L30.6951 25.3075C30.4344 25.047 30.2336 24.7328 30.1068 24.3868C29.9799 24.0407 29.9299 23.6712 29.9604 23.3039C29.9908 22.9366 30.101 22.5804 30.2831 22.26C30.4653 21.9396 30.7151 21.6628 31.0151 21.4488L33.6989 19.4488L15.1851 15.1763L19.5001 33.7275L19.5139 33.7113L21.4414 31.0125C21.6555 30.7124 21.9325 30.4626 22.253 30.2805C22.5735 30.0983 22.9298 29.9882 23.2972 29.9577C23.6646 29.9272 24.0342 29.9772 24.3803 30.1041C24.7264 30.231 25.0407 30.4318 25.3014 30.6925L30.4864 35.875C30.728 36.1163 31.0555 36.2518 31.397 36.2518C31.7385 36.2518 32.066 36.1163 32.3076 35.875L35.8751 32.3075C36.1161 32.0657 36.2514 31.7383 36.2514 31.3969C36.2514 31.0555 36.1161 30.728 35.8751 30.4863ZM8.14636 9.385C7.98292 9.38706 7.82069 9.35675 7.66901 9.29583C7.51733 9.2349 7.37921 9.14455 7.26261 9.03L4.58011 6.3475C4.35242 6.11175 4.22643 5.796 4.22927 5.46825C4.23212 5.1405 4.36358 4.82699 4.59534 4.59523C4.8271 4.36347 5.14062 4.23201 5.46836 4.22916C5.79611 4.22631 6.11186 4.3523 6.34761 4.58L9.03012 7.2625C9.20107 7.43787 9.31674 7.65959 9.36277 7.90013C9.4088 8.14068 9.38315 8.38944 9.28901 8.61553C9.19487 8.84162 9.03639 9.03508 8.83325 9.17188C8.63011 9.30867 8.39126 9.38278 8.14636 9.385ZM17.9726 9.03C17.7362 9.26044 17.419 9.3894 17.0889 9.3894C16.7587 9.3894 16.4416 9.26044 16.2051 9.03C15.9708 8.79559 15.8391 8.47771 15.8391 8.14625C15.8391 7.8148 15.9708 7.49691 16.2051 7.2625L18.8876 4.58C19.0029 4.46061 19.1409 4.36538 19.2934 4.29987C19.4459 4.23436 19.6099 4.19988 19.7759 4.19844C19.9418 4.197 20.1064 4.22862 20.2601 4.29147C20.4137 4.35432 20.5532 4.44714 20.6706 4.56451C20.788 4.68187 20.8808 4.82144 20.9436 4.97506C21.0065 5.12868 21.0381 5.29328 21.0367 5.45925C21.0352 5.62523 21.0008 5.78925 20.9352 5.94176C20.8697 6.09426 20.7745 6.23219 20.6551 6.3475L17.9726 9.03ZM6.34761 20.655C6.11146 20.886 5.79423 21.0154 5.46386 21.0154C5.1335 21.0154 4.81627 20.886 4.58011 20.655C4.34578 20.4206 4.21413 20.1027 4.21413 19.7713C4.21413 19.4398 4.34578 19.1219 4.58011 18.8875L7.26261 16.205C7.37792 16.0856 7.51585 15.9904 7.66836 15.9249C7.82086 15.8594 7.98489 15.8249 8.15086 15.8234C8.31684 15.822 8.48144 15.8536 8.63506 15.9165C8.78868 15.9793 8.92824 16.0721 9.04561 16.1895C9.16297 16.3069 9.25579 16.4464 9.31864 16.6001C9.38149 16.7537 9.41312 16.9183 9.41168 17.0843C9.41024 17.2502 9.37575 17.4143 9.31024 17.5668C9.24473 17.7193 9.1495 17.8572 9.03012 17.9725L6.34761 20.655ZM12.6176 7.54375C12.2861 7.54375 11.9682 7.41205 11.7337 7.17763C11.4993 6.94321 11.3676 6.62527 11.3676 6.29375V2.5C11.3676 2.16848 11.4993 1.85054 11.7337 1.61612C11.9682 1.3817 12.2861 1.25 12.6176 1.25C12.9491 1.25 13.2671 1.3817 13.5015 1.61612C13.7359 1.85054 13.8676 2.16848 13.8676 2.5V6.29375C13.8676 6.62527 13.7359 6.94321 13.5015 7.17763C13.2671 7.41205 12.9491 7.54375 12.6176 7.54375ZM2.50011 11.3675H6.29387C6.62539 11.3675 6.94333 11.4992 7.17775 11.7336C7.41217 11.968 7.54387 12.286 7.54387 12.6175C7.54387 12.949 7.41217 13.267 7.17775 13.5014C6.94333 13.7358 6.62539 13.8675 6.29387 13.8675H2.50011C2.16859 13.8675 1.85065 13.7358 1.61623 13.5014C1.38181 13.267 1.25011 12.949 1.25011 12.6175C1.25011 12.286 1.38181 11.968 1.61623 11.7336C1.85065 11.4992 2.16859 11.3675 2.50011 11.3675Z" fill="#272727"></path></svg> <!--'end_frame_cache_Zg1Ab0'--> Для малого числа участников задача решается сравнительно легко. Случаи с двумя и тремя бегунами доказываются элементарно. Для четырёх участников доказательство получили ещё в 1970-е годы. Дальше продвижение шло медленно, и к 2007 году математики сумели закрыть случаи до семи бегунов включительно. После этого наступил долгий перерыв. Почти двадцать лет никто не мог сделать следующий шаг.
Для отдельных случаев математики придумывали остроумные приёмы, но общего метода долго не было. В одном доказательстве помогали инструменты теории чисел , в другом геометрия, в третьем теория графов. Подход, который работал для одного значения, мог оказаться бесполезным для следующего. Поэтому каждое новое продвижение почти всегда требовало отдельного решения.
К середине 2000-х удалось хотя бы сократить число случаев, которые нужно проверять. Исследователи поняли, что не обязательно разбирать все возможные скорости, включая дробные и иррациональные. Достаточно доказать гипотезу для целых скоростей, и тогда общий случай последует автоматически. Такая замена сильно упростила задачу, но не сняла проблему полностью, потому что даже целочисленных наборов остаётся бесконечно много.
В 2015 году важный шаг сделал Теренс Тао. Он показал , что для фиксированного числа бегунов не нужно отдельно рассматривать очень большие скорости. Если гипотеза верна для скоростей до определённого порога, то она верна вообще для всех скоростей. Тем самым задача хотя бы теоретически сводилась к конечному числу проверок.
Однако на практике и такое упрощение почти не помогало. Даже после ограничения сверху число возможных наборов скоростей оставалось огромным. Перебор всех вариантов был слишком тяжёлым. Нужно было не просто сократить список, а резко сузить круг действительно важных случаев.
Именно это в прошлом году сделал Матьё Розенфельд из лаборатории информатики, робототехники и микроэлектроники в Монпелье. Он посмотрел на задачу с другой стороны. Вместо попытки сразу доказать гипотезу исследователь спросил: какими должны быть скорости, если гипотеза неверна? Иначе говоря, как выглядел бы контрпример, в котором хотя бы один бегун никогда не оказывается одиноким?
Выяснилось, что такой гипотетический контрпример должен удовлетворять очень жёстким арифметическим условиям. Розенфельд с помощью компьютерной программы и методов теории чисел показал: если взять произведение всех скоростей, то для контрпримера это произведение должно делиться на определённый набор простых чисел. Такой результат резко ограничил число возможных плохих случаев.
Дальше Розенфельд объединил этот вывод с идеей Тао о пороге. Он переписал условие уже через произведение скоростей. Получилось следующее: если гипотеза верна для всех произведений до некоторой границы, то она верна вообще всегда. Значит, любой контрпример, если бы он существовал, пришлось бы искать ниже этого порога. Но ранее уже было показано, что произведение скоростей в контрпримере должно делиться на слишком большой набор простых чисел , а значит, само это произведение неизбежно выходит далеко за пределы допустимой границы.
В результате возникло противоречие. Контрпример должен был бы одновременно быть и сравнительно маленьким, и очень большим. Такое невозможно. Значит, для восьми бегунов контрпримеров нет, и гипотеза верна. Так математики впервые за много лет продвинулись дальше случая с семью участниками.
На этом развитие не остановилось. Работу Розенфельда увидел Ноа Кравиц из Оксфорда и показал статью студенту второго курса Полу Тракултонгчаю, с которым занимался. Кравиц предложил ему рассмотреть следующий случай, то есть девять бегунов. Тракултонгчай взял за основу общий подход Розенфельда, но сумел заметно улучшить вычислительную часть.
Он разработал более эффективный способ находить простые делители , которые должен был бы иметь любой контрпример. Благодаря этому удалось быстрее исключить все возможные плохие случаи не только для девяти, но и сразу для десяти бегунов. В обоих вариантах гипотеза тоже оказалась верной. При этом Розенфельд независимо получил доказательство для девяти участников почти одновременно, всего через несколько дней после молодого коллеги из Оксфорда.
Для математического сообщества этот результат особенно важен по одной причине. Раньше каждый новый случай обычно требовал отдельной идеи. Теперь один и тот же общий подход позволил закрыть сразу три новых значения: восемь, девять и десять бегунов. Поэтому исследователи увидели в этой работе не просто удачное частное решение, а возможный путь к более общей стратегии.
Полного доказательства для любого числа участников пока нет. Более того, нынешние методы уже упираются в пределы вычислительных возможностей. Для одиннадцати бегунов подход Розенфельда и Тракултонгчая оказывается слишком тяжёлым. Сами авторы новых результатов считают, что для следующего шага, скорее всего, понадобится другой взгляд на задачу.
Осторожность сохраняется и по другой причине. Хотя гипотеза подтверждена для всё большего числа случаев, математики пока не могут с уверенностью сказать, что она верна для любого N. Цепочка частных доказательств выглядит впечатляюще, но общего ответа всё ещё нет. В подобных задачах именно здесь проходит граница между серьёзным прогрессом и окончательным решением.
Тем не менее ситуация явно изменилась. После долгого застоя появились новые доказательства, новый метод и ощущение, что задача снова сдвинулась с места. Осенью в Ростоке планируют специальный семинар по гипотезе одинокого бегуна. Организаторы хотят собрать специалистов из разных областей, где возникает эта проблема, чтобы свести вместе подходы теории чисел, геометрии, теории графов и вычислительной математики.
- Источник новости
- www.securitylab.ru
