Головоломка Рамсея

9

Здесь показана трехуветная раскраска полного графа $K_{16}$, т. е. графа с 16 вершинами, все пары вершин которого соединены ребрами. Эта раскраска заменяется тем, что в ней нет ни одного однозначного треугольника, в то время как любая (треугольная) раскраска полного графа с большим числом вершин (например, $K_{23}$) обязательно содержит такой треугольник. Полный граф с наименьшим числом вершин, в котором при раскраске обязательно встречается запрещенная однозначная конфигурация (в данном случае — треугольники), называется «графом Рамсея» (для данного набора запрещенных конфигураций). Так, граф $K_{17}$ — соответствующий граф Рамсея. Разумеется, для других числа цветов и других наборов конфигураций возникают свои графы Рамсея; о них можно прочитать в статье М. Гарднера в этом номере. С каждым графом Рамсея (с п вершинами) связаны головоломка и цгра. Головоломка состоит в том, чтобы раскрасят полный граф $K_{n-1}$, не создав при этом ни одной запрещенной конфигурации. (Так, приведенный здесь рисунок — решение этой головоломки для $n=17$). Изра же проводится на графе Рамсея (скажем, на $K_{17}$) двумя цроками, которые поочередно раскраивают ребра графа (здесь — в три цвета), известная запретных конфигураций (здесь — однозначных треугольников); проигрывает тот, кто вынужден создать такую конфигурацию. Ницы не бывают (почем?).