- 14,593
- 22
- 8 Ноя 2022
Теория Рамсея объясняет, почему ваши связи не так случайны, как кажутся.
На небольшом мероприятии с шестью приглашенными гостями всегда возникнет ситуация, при которой найдется группа из трех человек, которые либо все друг друга знают, либо являются абсолютно незнакомыми. С первого взгляда это кажется простой закономерностью, но при более внимательном рассмотрении проблема приобретает неожиданные сложности. Партия из шести человек может иметь 15 возможных связей между ними, и каждая связь может быть двух типов: знакомство или незнакомство. Хотя на первый взгляд кажется, что могут существовать разные способы организации таких связей, существует строгое математическое доказательство, что всегда можно найти такую группу, в которой все либо друзья, либо незнакомцы.
Эта задача тесно связана с Для просмотра ссылки Войдиили Зарегистрируйся , названной в честь британского математика Фрэнка Рамсея, который жил в начале XX века. Теория Рамсея изучает закономерности, которые неизбежно возникают в, казалось бы, случайных или хаотических системах. Основной идеей этой теории является попытка найти «порядок в хаосе». Пример с вечеринкой можно выразить следующим образом: сколько минимально нужно людей, чтобы среди них гарантированно нашлась группа из трех человек, которые либо все друг друга знают, либо не знают никого из группы?
Для понимания этой проблемы можно использовать графы — математические структуры, представляющие собой набор узлов (в данном случае людей) и рёбер (связей между ними). Представьте, что шесть человек сидят по кругу. Связи между ними можно изобразить в виде рёбер, которые соединяют каждую пару. Всего таких рёбер — 15, и каждое ребро можно окрасить либо в красный цвет (если два человека знакомы), либо в синий (если не знакомы). Теория Рамсея утверждает, что в любом раскладе окрашенных рёбер всегда найдется одноцветный треугольник — группа из трех людей, которые либо все друзья (красный треугольник), либо все незнакомцы (синий треугольник).
Если попытаться перебрать все возможные варианты раскрашивания связей между шестью гостями, можно убедиться, что в каждом случае возникнет одноцветный треугольник. Хотя вариантов связей — 32,768, все они подчиняются этому правилу. Более того, задача интересна тем, что шесть человек — это минимальное количество участников, при котором гарантированно возникает группа из трех друзей или незнакомцев. Если пригласить меньшее количество гостей, например пятерых, можно найти расклад, при котором такой треугольник не образуется.
Чтобы продемонстрировать эту закономерность, можно начать с одной конкретной точки на графе — допустим, с одного из гостей, назовем его A. Этот гость может иметь связи с пятью остальными участниками вечеринки. Эти связи могут быть либо дружескими, либо нет. В любом случае, хотя бы три связи должны быть одноцветными — либо красными, либо синими. Предположим, что A знает троих других гостей, то есть его три связи окрашены в красный цвет. Чтобы избежать образования красного треугольника, эти три знакомых между собой должны быть незнакомы. Но если провести синие рёбра между ними, получится синий треугольник. Этот пример показывает, что в любой конфигурации обязательно образуется одноцветный треугольник.
Но этим математики не ограничиваются. В теории Рамсея интересуют не только частные случаи с тремя людьми, но и более сложные конфигурации. Следующий вопрос: сколько людей нужно пригласить, чтобы среди них всегда можно было найти группу из четырех человек, которые либо все друзья, либо все незнакомцы? Ответ на этот вопрос был найден: если пригласить 18 человек, то всегда найдется группа из четырех человек с однотипными связями. Это число обозначается как R(4,4) — минимальное количество людей, при котором гарантированно возникает группа из четырех друзей или незнакомцев.
Однако с увеличением числа участников задача становится гораздо сложнее. Например, для пяти человек до сих пор не найдено точного решения. Математики смогли определить только диапазон возможных значений: известно, что минимальное количество людей, при котором гарантированно возникнет группа из пяти человек с однотипными связями, находится между 43 и 48. Это означает, что если пригласить 43 человека, возможно, что не будет группы из пяти человек, которые все друзья или все незнакомцы. Но если пригласить 48 человек, такая группа обязательно появится.
Может показаться, что такую задачу можно решить с помощью компьютеров, перебрав все возможные варианты связей между 43 или 48 людьми. Однако на практике это невозможно из-за огромного количества комбинаций. Если связать всех 43 человек, получится 903 рёбра, и каждое из них может быть либо красным, либо синим. Это дает 2^903 возможностей, что примерно равно числу 10^272 (единица с 272 нулями). Это число настолько велико, что его невозможно осмыслить. Для сравнения: считается, что во всей Вселенной около 10^82 атомов. Даже если каждый атом был бы компьютером, выполняющим квинтиллион (10^18) операций в секунду, и эти компьютеры начали бы работать сразу после Большого взрыва 13,8 миллиардов лет назад, они бы до сих пор не успели перебрать все возможные конфигурации.
Таким образом, даже с самыми современными вычислительными мощностями задача остается нерешенной. Математики продолжают искать более эффективные способы решения подобных проблем, но пока окончательный ответ на вопрос о точном значении R(5,5) не найден.
Теория Рамсея иллюстрирует, как в хаосе может скрываться порядок, и показывает, что даже в случайных системах возникают неизбежные закономерности.
На небольшом мероприятии с шестью приглашенными гостями всегда возникнет ситуация, при которой найдется группа из трех человек, которые либо все друг друга знают, либо являются абсолютно незнакомыми. С первого взгляда это кажется простой закономерностью, но при более внимательном рассмотрении проблема приобретает неожиданные сложности. Партия из шести человек может иметь 15 возможных связей между ними, и каждая связь может быть двух типов: знакомство или незнакомство. Хотя на первый взгляд кажется, что могут существовать разные способы организации таких связей, существует строгое математическое доказательство, что всегда можно найти такую группу, в которой все либо друзья, либо незнакомцы.
Эта задача тесно связана с Для просмотра ссылки Войди
Для понимания этой проблемы можно использовать графы — математические структуры, представляющие собой набор узлов (в данном случае людей) и рёбер (связей между ними). Представьте, что шесть человек сидят по кругу. Связи между ними можно изобразить в виде рёбер, которые соединяют каждую пару. Всего таких рёбер — 15, и каждое ребро можно окрасить либо в красный цвет (если два человека знакомы), либо в синий (если не знакомы). Теория Рамсея утверждает, что в любом раскладе окрашенных рёбер всегда найдется одноцветный треугольник — группа из трех людей, которые либо все друзья (красный треугольник), либо все незнакомцы (синий треугольник).
Если попытаться перебрать все возможные варианты раскрашивания связей между шестью гостями, можно убедиться, что в каждом случае возникнет одноцветный треугольник. Хотя вариантов связей — 32,768, все они подчиняются этому правилу. Более того, задача интересна тем, что шесть человек — это минимальное количество участников, при котором гарантированно возникает группа из трех друзей или незнакомцев. Если пригласить меньшее количество гостей, например пятерых, можно найти расклад, при котором такой треугольник не образуется.
Чтобы продемонстрировать эту закономерность, можно начать с одной конкретной точки на графе — допустим, с одного из гостей, назовем его A. Этот гость может иметь связи с пятью остальными участниками вечеринки. Эти связи могут быть либо дружескими, либо нет. В любом случае, хотя бы три связи должны быть одноцветными — либо красными, либо синими. Предположим, что A знает троих других гостей, то есть его три связи окрашены в красный цвет. Чтобы избежать образования красного треугольника, эти три знакомых между собой должны быть незнакомы. Но если провести синие рёбра между ними, получится синий треугольник. Этот пример показывает, что в любой конфигурации обязательно образуется одноцветный треугольник.
Но этим математики не ограничиваются. В теории Рамсея интересуют не только частные случаи с тремя людьми, но и более сложные конфигурации. Следующий вопрос: сколько людей нужно пригласить, чтобы среди них всегда можно было найти группу из четырех человек, которые либо все друзья, либо все незнакомцы? Ответ на этот вопрос был найден: если пригласить 18 человек, то всегда найдется группа из четырех человек с однотипными связями. Это число обозначается как R(4,4) — минимальное количество людей, при котором гарантированно возникает группа из четырех друзей или незнакомцев.
Однако с увеличением числа участников задача становится гораздо сложнее. Например, для пяти человек до сих пор не найдено точного решения. Математики смогли определить только диапазон возможных значений: известно, что минимальное количество людей, при котором гарантированно возникнет группа из пяти человек с однотипными связями, находится между 43 и 48. Это означает, что если пригласить 43 человека, возможно, что не будет группы из пяти человек, которые все друзья или все незнакомцы. Но если пригласить 48 человек, такая группа обязательно появится.
Может показаться, что такую задачу можно решить с помощью компьютеров, перебрав все возможные варианты связей между 43 или 48 людьми. Однако на практике это невозможно из-за огромного количества комбинаций. Если связать всех 43 человек, получится 903 рёбра, и каждое из них может быть либо красным, либо синим. Это дает 2^903 возможностей, что примерно равно числу 10^272 (единица с 272 нулями). Это число настолько велико, что его невозможно осмыслить. Для сравнения: считается, что во всей Вселенной около 10^82 атомов. Даже если каждый атом был бы компьютером, выполняющим квинтиллион (10^18) операций в секунду, и эти компьютеры начали бы работать сразу после Большого взрыва 13,8 миллиардов лет назад, они бы до сих пор не успели перебрать все возможные конфигурации.
Таким образом, даже с самыми современными вычислительными мощностями задача остается нерешенной. Математики продолжают искать более эффективные способы решения подобных проблем, но пока окончательный ответ на вопрос о точном значении R(5,5) не найден.
Теория Рамсея иллюстрирует, как в хаосе может скрываться порядок, и показывает, что даже в случайных системах возникают неизбежные закономерности.
- Источник новости
- www.securitylab.ru
