Ситуация вполне правдоподобная, но, сколько ни думай, доказательство все время ускользает. В условии не говорится, что собравшиеся делятся на две группы: друзья и незнакомцы. Также нигде не сказано, что они все не могут быть друзьями или чужаками. Вроде бы очевидно: если среди собравшихся есть двое друзей, то остальные четверо должны быть чужаками, но это тоже неверно. Двое из этих самых «чужаков» могут быть знакомы между собой, но не знать ни одного из «друзей».
А вот математик враз покончит со всей этой неразберихой. Он возьмет карандаш, а лучше два карандаша, красный и синий, или даже три — красный, синий и черный, и нарисует круг из шести черных точек, каждая из которых обозначает гостя. Затем он соединит красными линиями все пары людей, которые знают друг друга, и синими линиями — пары незнакомцев. В этом узоре из пятнадцати линий обязательно окажется либо красный, либо синий треугольник: трое людей, знакомых друг с другом, либо трое, которые друг друга не знают.
Конечно, рисунок не доказывает изначальное высказывание, зато он переводит неясную ситуацию с людьми в четкое математическое выражение. Задача теперь рассматривает точки, соединенные линиями, то есть схему, а не людей и их взаимоотношения.
Область математики, имеющая дело с такими задачами, называется теорией Рамсея — в честь гениального кембриджского математика Фрэнка Пламптона Рамсея (1903–1930), умершего в 26-летнем возрасте, но успевшего внести существенный вклад в математику, экономику и философию. Задачка с обедом — одна из простейших в этой области, графы к более сложным задачам содержат больше точек, соединенных большим количеством линий. Граф, в котором каждая точка соединена со всеми остальными точками прямыми линиями, называется «полный граф». Граф, находящийся внутри этого множества линий, например красный или синий треугольник из вышеописанного примера, носит название «подграфа». Задачи в теории Рамсея обычно формулируются в виде вопросов типа: каково должно быть минимальное количество точек, чтобы образованный ими полный граф, случайным образом нарисованный красным или синим карандашами, содержал либо красный треугольник, либо синий четырехугольник?
Такие задачи на удивление трудно поддаются решению. Если в задачке про обед изменить условие и вместо трех сделать пятерых друзей или пятерых незнакомцев, то решить ее станет невозможно. Ответ можно будет выразить как R (5,5) — минимальное число гостей, необходимое, чтобы среди них оказалось либо пятеро друзей, либо пятеро человек, незнакомых друг с другом, но что это за число — никто не знает. Максимально близко к ответу ученые подошли, когда определили, что это R (5,5) находится где-то между 43 и 49. Венгерский математик Пал Эрдёш (1913–1996) однажды написал: «Представим себе, что некая инопланетная армия, куда более могущественная, чем наша, прилетит на Землю и потребует сообщить им точное значение R (5,5), а в противном случае пригрозит уничтожить нашу планету. Чтобы найти это значение, нам потребуется привлечь все имеющиеся компьютеры и математиков. А случись инопланетянам, допустим, потребовать значение R (6,6) — проще будет сразу попытаться уничтожить пришельцев».
