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