Задача, ставившая математиков в тупик почти столетие, наконец решена
Задача Рамсея одна из самых сложных и древних проблем в комбинаторике, разделе математики, изучающем способы выбора и распределения объектов. Она связана с поиском порядка и регулярности в хаотичных и случайных структурах, таких как графы, числа или геометрические фигуры. Одним из примеров такой задачи является вопрос: сколько человек нужно пригласить на вечеринку, чтобы гарантированно найти четырех человек, которые знакомы друг с другом или четырех человек, которые незнакомы ни с кем? Это число называется числом Рамсея и обозначается как 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), сформулировать просто, но, как показано на этом графе, возможные решения почти безграничны.
Так как точные числа очень сложно найти, математики работают с оценками. В этом направлении мы достигли прогресса в нашей последней работе. Мы пытаемся найти не точный ответ, а лучшие оценки для чисел Рамсея
— Жак Верстраете.
Этот прорыв является важным шагом в понимании теории Рамсея и ее приложений в разных областях математики, таких как теория чисел, теория кодирования, криптография и теория игр. Он также демонстрирует, что даже самые сложные и давние задачи могут быть решены с помощью новых идей и современных методов.
Наши новостные каналы
Подписывайтесь и будьте в курсе свежих новостей и важнейших событиях дня.
Рекомендуем для вас
Возможно, целлофановые пчелы — спасение человечества: они миллионы лет делают то, что нужно нам как воздух
Поразительно, но удивительный продукт ученые нашли почти полвека назад, но почему-то до последнего времени не обращали на него внимания...
Тайна скифской ДНК: что поразило российских ученых, когда они заглянули в геном легендарных кочевников древности
Оказалось, что 2500 лет подряд историки ошибались в происхождении этого народа. Теории и учебники придется серьезно переписать...
Новый рецепт апокалипсиса: даже небольшая ядерная боеголовка на орбите гарантировано выведет из игры 99% аппаратов за считаные дни
Однако самое опасное, по словам ученых, начнется позже. Почему космос будет фактически закрыт?...
Ненужный рай: 1500-километровое путешествие показало, почему древние люди обходили стороной Зеленую Аравию
Выяснилось, что питьевая вода еще не делает местность пригодной для жилья. Племенам из древности требовалось еще кое-что необходимое...
Назад в будущее: в России вернут проводное радио. Зачем? Почему спорят эксперты?
В технологию уже вложено более миллиарда рублей, а МЧС называет проводное радио лучшим способом оповещения на сегодня...
Древние майя настолько любили красный цвет, что в итоге эта страсть, возможно, стала одной из причин гибели цивилизации
Ученые нашли доказательства, как яркая краска способствовала краху великой империи...
Авиация в США наконец-то уходит… с дискет: почему так поздно и как с этим обстоят дела в России?
Американцы потратили на выход из 90-х чудовищные суммы, но далеко не факт, что все заработает в срок и как надо...
Настоящий Ковчег Завета, возможно, спрятан в Эфиопии: почему его может видеть только один человек?
Этой истории 3000 лет, но она до сих пор далека от своего завершения...
Загадочный астероид неожиданно ускорился: у астрофизиков заканчиваются объяснения и гипотезы
Пожалуй, это самый интересный космический детектив за последнее время, и пока он далек до финала...
Наша Вселенная скреплена невидимым галактическим клеем: и без него нас бы не было
По словам ученых, «склеивание» произошло уже в первые секунды существования мироздания...
Парадокс Древнего Перу: жили мирно, но при этом приносили массовые и жестокие человеческие жертвы. Почему?
Ученый рассказал, какую роль в истории сыграл Эль-Ниньо и почему ритуальные убийства совершали «без гнева и конфликта»...
Усиленно боролись за чистоту, но просчитались: как роковая ошибка властей поставила под угрозу целый средневековый город
Норвежский Тронхейм был самым чистым в Европе, однако руководству города этого показалось мало. Хотели как лучше, а получилось как всегда...
В России создана революционная упаковка: молоко будет свежим целый месяц
Разбираемся: не испортился ли вкус продукта и когда ожидать чудо-пачки в продаже...
Выход на новый уровень: почему Россия возрождает проводное радио, а Китай давно прокачал этот вид связи
У старой технологии обнаружился огромный потенциал, который поможет миллионам людей...