Мушкетёры и дуэли

Удобно изображать мушкетёров точками плоскости, а дуэли между ними — отрезками, соединяющими эти точки.

К задаче А. Попробуйте разобрать такие три случая:
1) есть точка, из которой выходит не менее 4 отрезков;
2) есть точка из которой выходит не более 2 отрезков;
3) из каждой точки выходит по три отрезка.

К задаче Б. Ответ в этой задаче отрицателен.

К задаче А. Третий случай невозможен. Сосчитайте для него общее число дуэлей между всеми мушкетерами — оно окажется нецелым.

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

Задача А.

Для краткости будем называть непоссорившихся мушкетёров друзьями .

а) Если кто-то из мушкетёров имеет не более чем четверых друзей, то с четырьмя остальными он дерется. Но тогда все его соперники дружат между собой — иначе было бы противоречие условию задачи. Значит, мы нашли четверку друзей.

б) Теперь рассмотрим другой случай. Кто-то из мушкетёров (например, Арамис) дерется не более чем с двумя, а дружит не менее чем с шестью остальными. Пусть Портос — один из друзей Арамиса. Если Портос дерется хотя бы с тремя из друзей Арамиса, то никто из этих троих уже не может драться друг с другом, значит, они все дружат между собой. А так как они еще и дружат с Арамисом, то у нас получилась четверка друзей. Если же Портос дерется не более чем с двумя из друзей Арамиса, то трое оставшиеся — общие друзья Арамиса и Портоса. Поскольку они не могут все драться друг с другом, то какие-то двое из них (Атос и Д’Артаньян) дружат. Следовательно, вместе с Портосом и Арамисом они составят четверку друзей.

в) Наконец, что будет, если не нашлось ни мушкетёра с шестью (или более) друзьями, ни мушкетёра с четырьмя (или менее) друзьями. Это значит, что каждый из мушкетёров сохранил в друзьях ровно пятерых, а дерется ровно с тремя. Тогда получается, что для каждого из 9 человек предстоят три дуэли — то есть всего ожидается 27 участий в дуэлях. Но это, очевидно, невозможно, потому что у каждой дуэли ровно двое участников, то есть общее количество участий должно быть четным.

Задача Б.

Здесь нарисованы только дуэли, все остальные мушкетёры друг с другом не поссорились. Несложно убедиться в том, что условие задачи выполнено — никакие три проведенных отрезка не образуют треугольника (пересечение отрезков в центре не считается, потому что центральная точка не соответствует никакому мушкетёру).

Но и четверки друзей при этом не найдется, потому что каждый остался дружить с такой четверкой, в которой предстоят три дуэли. Например, четверке C, D, F, G, с которой дружит мушкетер A, предстоят дуэли (C, D), (F, G) и (G, C). Несложно убедиться, что в этой четверке нет трех попарных друзей.

Числа Рамсея

Эту задачу в математике принято формулировать, во-первых, не разбивая ее на «А» и «Б», а во-вторых, симметрично относительно «дружб» и «ссор». Стандартная постановка задачи примерно такая:

Рассмотрим полный граф на N вершинах, ребра которого произвольно раскрашены в два цвета — красный и синий. Чему равно наименьшее N, для которого при любой такой раскраске обязательно найдется либо полный синий подграф на b вершинах, либо полный красный подграф на r вершинах.

Число, являющееся ответом на этот вопрос, называют числом Рамсея и обозначают R(r, b) в честь британского математика Фрэнка П. Рамсея (Frank P. Ramsey), в чьей работе 1930 года содержится и первая постановка аналогичной задачи, и ее решение.

Разобранный нами частный случай соответствует нахождению R(3, 4), а точнее, установлению факта R(3, 4) = 9. Действительно, наше условие «если не нашлось троих мушкетеров, которые вызвали на дуэль друг друга, то найдутся четверо не поссорившихся» легко переформулируется в «или найдутся трое мушкетёров, вызвавших на дуэль друг друга, или найдутся четверо не поссорившихся». В задаче A доказано, что это верно для группы из девяти мушкетёров, то есть для полного графа на девяти вершинах, а в задаче Б проверено, что это неверно для полного графа на восьми вершинах. Таким образом, задача A доказывает, что R(3, 4) ≤ 9, а задача Б — что R(3, 4) > 8. Два доказанных неравенства и дают окончательный результат R(3, 4) = 9. (Кроме этого, мы по ходу доказательства задачи A нашли, что R(3, 3) = 6 — сможете ли вы самостоятельно обнаружить, в каком именно месте наших рассуждений это было установлено?). Кстати, значение R(3, 4) впервые было найдено менее 60 лет назад — в 1955 году.

Задача Рамсея и ее обобщения (на другие графы, на большее количество цветов, на многие другие специальные случаи) породили целый раздел дискретной математики — рамсеевскую теорию графов. Библиография, посвященная рамсеевским графам, исчисляется сотнями названий статей и несколькими десятками названий книг. И тем не менее, даже исходная задача о числах Рамсея R(3, n) (то есть таких полных графах, в которых при любой двуцветной раскраске должен найтись либо красный треугольник, либо синий n-угольник со всеми диагоналями) еще далеко не раскрыла всех своих тайн. Например, в статье 1990 года, написанной двумя видными исследователями — Р. Грэхемом и Дж. Спенсером, указаны границы 28 ≤ R(3, 8) ≤ 29, то есть на тот момент точное значение R(3, 8) известно не было. А вот с 1994 года стало точно известно, что R(3, 8) = 28. Кроме того, сейчас известно, что R(3, 5) = 14, R(3, 6) = 18, R(3, 7) = 23 и R(3,9) = 36. А вот дальше начинаются неопределенности, то есть нерешенные задачи и открытые проблемы: 40 ≤ R(3, 10) ≤ 43, 46 ≤ R(3, 11) ≤ 51, 52 ≤ R(3, 12) ≤ 59, 59 ≤ R(3, 13) ≤ 69. Кстати, часть из этих верхних и нижних границ была установлена сравнительно недавно — в 1989-м, 1998-м, 2001 годах. Если же рассматривать не частную задачу об отыскании R(3, n), а более общую — то новые результаты по ним появляются буквально ежегодно.

Для дальнейшего ознакомления с вопросом можно прочитать страничку Ramsey Number. Для тех, кому этого покажется недостаточно, есть написанный Станиславом Радзишовским обзор всех «рамсеевских» результатов, полученных до 2008 года включительно, — он лежит на страничке Dynamic Surveys. На русском языке есть материалы лекций А. М. Райгородского на летней школе в Дубне в 2006 году «Вероятность и линейная алгебра в комбинаторике» (PDF, 377 Кб), где результатам рамсеевской теории графов было посвящено одно из занятий. Еще одна «рамсеевская» теорема подробно освещена в книжке В. О. Бугаенко «Обобщенная теорема Ван дер Вардена» (PDF, 247 Кб).