
Задача, ставившая математиков в тупик почти столетие, наконец решена
Задача Рамсея одна из самых сложных и древних проблем в комбинаторике, разделе математики, изучающем способы выбора и распределения объектов. Она связана с поиском порядка и регулярности в хаотичных и случайных структурах, таких как графы, числа или геометрические фигуры. Одним из примеров такой задачи является вопрос: сколько человек нужно пригласить на вечеринку, чтобы гарантированно найти четырех человек, которые знакомы друг с другом или четырех человек, которые незнакомы ни с кем? Это число называется числом Рамсея и обозначается как r (4,4).
Числа Рамсея очень трудно найти, так как они растут очень быстро с увеличением количества людей или групп. Например, известно, что r (3,3) 6, то есть на вечеринке из шести человек всегда найдутся три человека, которые знакомы между собой, или три незнакомых ни с кем человека. Также известно, что r (4,4) 18, то есть на вечеринке из 18 человек всегда найдутся четыре человека, которые знают друг друга, или четыре человека, которые не знают друг друга. Однако r (5,5) до сих пор неизвестно, и его значение лежит где-то между 43 и 49.
Два математика из Сан-Диего, Жак Верстраете и Сэм Маттеус, сделали значительный прогресс в решении одной из вариаций задачи Рамсея, которая называется r (4, t). Эта задача спрашивает: сколько человек нужно пригласить на вечеринку, чтобы гарантированно найти четырех человек, которые знакомы, или t гостей, которые не знают друг друга? Эта задача была предложена в 1930-х годах венгерским математиком Полем Эрдешем, который обещал приз в 250 долларов за ее решение.
Верстраете и Маттеус нашли приближенное решение для r (4, t), используя понятие псевдослучайных графов, которые выглядят случайными, но имеют некоторые скрытые свойства. Они показали, что r (4, t) примерно равно t³, то есть на вечеринке из t³ человек всегда найдутся четыре знакомых между собой человека, или t человек, которые не знают друг друга. Это решение является лучшей известной оценкой для r (4, t) и улучшает предыдущий результат, полученный в 1989 году.
—Жак Верстраете.
На первый взгляд кажется, что решение задачи заняло практически век, однако, когда речь идет о теории графов, внешность может быть обманчивой. Например, при решении r (5,5) при известном диапазоне ответов от 40 до 50, если начать с 45 точек на графе, потребуется целых 10 234 комбинации.

Задачи Рамсея, такие как r(4,5), сформулировать просто, но, как показано на этом графе, возможные решения почти безграничны.
— Жак Верстраете.
Этот прорыв является важным шагом в понимании теории Рамсея и ее приложений в разных областях математики, таких как теория чисел, теория кодирования, криптография и теория игр. Он также демонстрирует, что даже самые сложные и давние задачи могут быть решены с помощью новых идей и современных методов.
Числа Рамсея очень трудно найти, так как они растут очень быстро с увеличением количества людей или групп. Например, известно, что r (3,3) 6, то есть на вечеринке из шести человек всегда найдутся три человека, которые знакомы между собой, или три незнакомых ни с кем человека. Также известно, что r (4,4) 18, то есть на вечеринке из 18 человек всегда найдутся четыре человека, которые знают друг друга, или четыре человека, которые не знают друг друга. Однако r (5,5) до сих пор неизвестно, и его значение лежит где-то между 43 и 49.
Два математика из Сан-Диего, Жак Верстраете и Сэм Маттеус, сделали значительный прогресс в решении одной из вариаций задачи Рамсея, которая называется r (4, t). Эта задача спрашивает: сколько человек нужно пригласить на вечеринку, чтобы гарантированно найти четырех человек, которые знакомы, или t гостей, которые не знают друг друга? Эта задача была предложена в 1930-х годах венгерским математиком Полем Эрдешем, который обещал приз в 250 долларов за ее решение.
Верстраете и Маттеус нашли приближенное решение для r (4, t), используя понятие псевдослучайных графов, которые выглядят случайными, но имеют некоторые скрытые свойства. Они показали, что r (4, t) примерно равно t³, то есть на вечеринке из t³ человек всегда найдутся четыре знакомых между собой человека, или t человек, которые не знают друг друга. Это решение является лучшей известной оценкой для r (4, t) и улучшает предыдущий результат, полученный в 1989 году.
Многие ученые более 90 лет ломали голову над проблемой r (4, t). Однако эта задача не была центральной темой нашего исследования. Все знают, что это сложная задача, и все пытаются в ней разобраться. Но если у вас нет свежей идеи, вряд ли вы добьетесь какого-либо прогресса
—Жак Верстраете.
На первый взгляд кажется, что решение задачи заняло практически век, однако, когда речь идет о теории графов, внешность может быть обманчивой. Например, при решении r (5,5) при известном диапазоне ответов от 40 до 50, если начать с 45 точек на графе, потребуется целых 10 234 комбинации.

Задачи Рамсея, такие как r(4,5), сформулировать просто, но, как показано на этом графе, возможные решения почти безграничны.
Так как точные числа очень сложно найти, математики работают с оценками. В этом направлении мы достигли прогресса в нашей последней работе. Мы пытаемся найти не точный ответ, а лучшие оценки для чисел Рамсея
— Жак Верстраете.
Этот прорыв является важным шагом в понимании теории Рамсея и ее приложений в разных областях математики, таких как теория чисел, теория кодирования, криптография и теория игр. Он также демонстрирует, что даже самые сложные и давние задачи могут быть решены с помощью новых идей и современных методов.
Наши новостные каналы
Подписывайтесь и будьте в курсе свежих новостей и важнейших событиях дня.
Рекомендуем для вас

Планшет, пролежавший в Темзе пять лет, помог раскрыть серию запутанных преступлений
Эксперты говорят: даже вода не смогла стереть цифровые следы....

«Инопланетяне» на Земле? Древние 8-метровые «грибы» оказались совершенно неизвестной формой жизни
Вот уже 180 лет подряд живые «башни» ставят в тупик всю науку....

«Шерстистый дьявол» обнаружен в пустыне, на границе Мексики и США
Ученые говорят: такой уникальной находки не было последние полвека....

Американские спецслужбы скрывают правду о самой древней из библейских реликвий?
Экстрасенс ЦРУ предупредил: Ковчег Завета убьет каждого, кто к нему прикоснется....

Похоже, что проблема космического мусора в скором времени будет решена раз и навсегда
Новая технология не только очистит космос, но и поможет спутникам работать втрое дольше....

Скрытые миллиарды: население Земли оказалось гораздо больше, чем считалось
Новые исследования бросают вызов официальным демографическим данным....

Почему мы не помним себя младенцами? Новое исследование дало ответы
Возможно, помним, но «ларчик» заперт....

Археологи ликуют: в Испании нашли рисунки, которые старше человечества!
200 000-летняя находка заставит пересмотреть учебники....

Астрофизики рассказали, почему Вселенная замедляется вопреки предсказаниям Эйнштейна
Если открытие DESI и ослабление темной энергии подтвердится, учебники придется переписать....

iPhone, давай до свидания! Илон Маск презентовал инновационный смартфон PhoneX
Это устройство слишком прекрасно для нашей реальности....

Ученые поражены: мыши, как спасатели, оживляют своих сородичей, попавших в беду
Открытие, от которого дрогнет даже самое черствое сердце....

Кислород устарел! Ученые нашли новый ключ к внеземной жизни
Гицеанические миры могут стать новой надеждой астрофизиков....

Самые массовые и дикие розыгрыши на 1 апреля в мировой истории
Это вам не просто «вся спина белая»....

На 100 000 лет раньше людей: ученые рассказали, кто устроил первые похороны на планете
Загадочные карлики Homo naledi, чей мозг был размером с апельсин, оказались не глупее нас с вами....

Секретная мутация гена: оказалось, ее имеют все обитатели Марианской впадины
Поразительное открытие китайских ученых может изменить всю теорию эволюции....

10 лет за 48 часов: ИИ полностью переиграл ученых в поисках секрета супербактерий
Однако эксперты предупреждают: нейросети не только ускоряют науку, они запросто могут столкнуть нас в пропасть....