Американские математики решили знаменитую задачу, над которой бились почти сто лет
1 ноября, 12:30 Поделиться:
Поиск решения проблемы занял годы (Фото:pexels)
Исследователи из Калифорнийского университета в Сан-Диего, Жак Верстрете и Сэм Маттеус, обнаружили решение для задачи Рамсея, которая десятилетиями представляла собой головоломку для математиков.
Суть задачи Рамсея заключается в нахождении комбинаторного порядка, где среди большого графика точек и линий можно гарантированно найти определенную структуру. Эта структура представляет собой набор точек, либо с линиями между ними, либо без таких линий. Эти наборы называются «кликами» и обозначаются как r (s, t), где s — количество точек с линиями, и t — количество точек без линий.
Самая известная проблема Рамсея, r (3,3), иногда называется «теоремой о друзьях и незнакомцах». Она объясняется примером: в группе из шести человек всегда можно найти как минимум троих, которые друг друга знают, либо троих, которые друг друга не знают. Решение r (3,3) — 6.
Читайте также:
Сила мысли. Математики нашли 12 000 новых решений неразрешимой задачи трех тел
Затем появилась задача нахождения r (4,4), которая была решена и составляет 18. Но более сложная задача r (5,5) до сих пор оставалась нерешенной. Почему задача, которую кажется легко сформулировать, так сложна? Дело в том, что поиск решения осложняется экспоненциальным ростом возможных вариантов.
Исследователи Верстрете и Маттеус решили использовать псевдослучайные графики, которые оказались более эффективными при приближении к решению сложных задач Рамсея. Они обнаружили, что выборка из псевдослучайных графиков часто дает лучшие оценки, чем случайные графики, сужая диапазон возможных решений. Результатом их исследования стало приближенное решение для r (4,t), которое близко к кубической функции t.
Важно отметить, что это приближенный ответ, но он близок к точному решению. Их исследование было отправлено на рассмотрение в журнал Annals of Mathematics. Ученые подчеркивают, что решение этой проблемы было результатом многолетних усилий, и это показывает важность настойчивости и поиска новых подходов к сложным математическим задачам.
«Никогда не следует сдаваться, независимо от того, сколько времени это займет», — утверждает Жак Верстрете, демонстрируя, как находя решения для сложных задач Рамсея, математики продолжают исследовать и расширять свои знания в области комбинаторики и теории графов.
Новий випуск журналу NV вже у продажу
Директор ЦРУ Вільям Бернс написав книжку,
яка, на мою думку, має бути обов’язковою для прочитання тими, хто прагне зрозуміти всі важливі події у світі з кінця ХХ століття, зокрема за кулісами дипломатії, міжнародної політики
Кирило Буданов, начальник ГУР, — про книгу
Невидима сила. Як працює американська дипломатія
Повний текст про улюблені книжки
Буданова читайте в номері,
що можна придбати тут
Новий випуск журналу NV вже у продажу
Путін був змушений вбити одного зі своїх найдовіреніших лейтенантів, Пригожина, на очах у всього світу, щоб показати, що він все ще головний. Це схоже на кінець гангстерського фільму Обличчя зі шрамом, коли Тоні Монтана вбиває свого найкращого друга
Борис Джонсон, британський експрем’єр
Повне інтерв’ю з Джонсоном
читайте в номері,
що можна придбати тут
Новий випуск журналу NV вже у продажу
Європейський Союз з’явився тільки тому, що Захід програв всі війни за свої імперії
Тімоті Снайдер, знаменитий американський історик
Повне інтерв’ю з Снайдером
читайте в номері,
що можна придбати тут
Новий випуск журналу NV вже у продажу
Володимир Зеленський є президентом країни в стані війни понад 600 днів, він неабияк втомився, і я не впевнений, що він настільки жадає влади, що захоче лишитися при владі назавжди
Френсіс Фукуяма, зірковий американський політолог і філософ
Повне інтерв’ю з Фукуямою
читайте в номері,
що можна придбати тут