Как математики ищут друзей

Даже самые суровые ученые-математики иногда развлекаются – например, собираются в математических клубах и в целом неплохо проводят время. И конечно же, после таких посиделок у математиков появляется множество новых идей! Однажды такое событие произошло и в жизни лондонского исследователя Фрэнка Пламптона Рамсея, а его результатом стала наша с вами сегодняшняя задача.

В тот дождливый вечер обсудить математику собрались сразу шестеро ученых. Оказалось, что не все они были ранее знакомы между собой, и Рамсей заинтересовался вопросом: можно ли найти среди них троих знакомых между собой людей? А троих совсем не знакомых друг с другом? В итоге вопрос нашей задачи звучит так: в любой ли компании из 6 человек можно выделить троих так, чтобы все они были или знакомы между собой, или незнакомы друг с другом?

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

Теперь будем раскрашивать ребра. Обозначим красным ребро между двумя вершинами, если соответствующие математики знакомы друг с другом, и синим – если в этот раз они в клубе встретились впервые. Получается, вопрос задачи будет звучать для нас так: существует ли в графе К₆ с любой двухцветной раскраской ребер одноцветный треугольник? К сожалению, по условию задачи раскраска ребер графа нам с вами неизвестна, поэтому придется включить воображение. Давайте подумаем, как могут быть раскрашены ребра, выходящие, например, из вершины 1?

Согласно принципу Дирихле, среди пяти выходящих из вершины 1 ребер хотя бы три окажутся одного цвета. Так как по условию задачи нам неважно, какого именно цвета будет искомый треугольник, будем говорить, что совпадающий цвет трех ребер – красный, как на рисунке.

Наш второй шаг – присмотреться к трем вершинам, которые с вершиной 1 соединяют ребра красного цвета: 2, 3 и 5. Они, разумеется, тоже образуют треугольник. Если все его ребра синего цвета, то мы нашли искомый треугольник – как на рисунке слева. А если нет – значит, хотя бы одно его ребро красное, и вместе с двумя ребрами, соединяющими концы его с вершиной 1, это ребро как раз образует треугольник красного цвета, как на рисунке справа.

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