Наименьшее из таких N называется числом Рамсея и обозначается R(n, k). Несложно доказать, что R(n,k) <= R(n-1,k) + R(n,k-1). В самом деле, обозначив R(n-1,k)=A, R(n,k-1) = B, рассмотрим произвольные A+B человек. Покажем, что среди них найдется либо n попарно знакомых, либо k попарно незнакомых. Выберем любого, скажем Васю. Вася или знаком хотя бы с A людьми, или незнаком хотя бы с B (потому что без него людей ровно A+B-1). В первом случае по определению числа A=R(n-1, k) среди его знакомых найдется либо n-1 попарно знакомых (добавив к ним знакомого с ними Васю, получим n попарно знакомых), либо k попарно незнакомых и сразу имеем то, что надо. Второй случай аналогичен.
Отсюда последовательно получаем неравенства R(2, n) <=n, R(3, n) <= n(n+1)/2 и т.д. При k=n получим оценку: R(n, n) < 4n, т.е. из любых 4n человек можно выбрать n попарно знакомых или попарно незнакомых. Насколько точна эта оценка? Наилучшую нижнюю оценку получил Эрдёш: из 2n/2 людей, n попарно знакомых или попарно незнакомых найдутся не всегда.
Доказательство удивительно просто: проверяем, что годится случайная компания! Пусть n – четно и выберем N=2n/2 людей. Каждых двух знакомим, если подброшенная для них монетка упадет орлом. Вероятность того, что данные n людей попарно знакомы (и попарно незнакомы), равна (1/2)n(n-1)/2. Складывая по всем наборам из n людей, получим число, меньшее 1 (вычисления опустим), и с положительной вероятностью наша компания не содержит ни n попарно знакомых, ни n попарно незнакомых людей.
