Много пар знакомых или незнакомых

Даны два натуральных числа m и n. Найдите наименьшее натуральное число k такое, что среди любых k людей либо найдутся 2m людей, которые образуют m взаимно знакомых пар, либо найдутся 2n людей, которые образуют n взаимно незнакомых пар.

Эта задача была предложена на Азиатско-Тихоокеанской олимпиаде в 2003 году.

Ответ: 2(m+n)-min{m,n}-1.

Эта задача является одной из задач теории графов. А точнее, той её части, которая изучает числа Рамсея.

Обозначим наименьшее натуральное число k, удовлетворяющее условию задачи, через r(m,n). Докажем, что

r(m,n)=2(m+n)-min{m,n}-1.

Легко понять, что r(m,n)=r(n,m). Рассмотрим случай m>=n. Теперь надо доказать, что r(m,n)=2m+n-1.

Для начала приведём пример, показывающий, что r(m,n)>=2m+n-1.

Назовём группу из k людей, любые два из которых попарно знакомы, k-союзом. Рассмотрим множество из 2m+n-2 людей, состоящее из (2m-1)-союза и (n-1) людей, никто из которых не знаком ни с кем другим (назовём таких людей изолированными).

Тогда в этом множестве не найдутся 2m людей, которые образуют m взаимно знакомых пар, и не найдутся 2n людей, которые образуют n взаимно незнакомых пар.

Таким образом, r(m,n)>=(2m-1)+(n-1)+1=2m+n-1 просто по определению r(m,n).

Для окончание решения осталось убедиться то, что r(m,n)<=2m+n-1.

Докажем, что

r(m,n)<=r(m-1,n-1)+3 для всех m>=n>=2.

Пусть G - это группа, состоящая из t=r(m-1,n-1)+3 человек.

Заметим, что

t>=2(m-1)+(n-1)-1+3=2m+n-1>=2m>=2n.

Если G является t-союзом, то в G найдутся 2m людей, образующих m взаимно знакомых пар. Если G состоит только из изолированных людей, то в G найдутся 2n людей, образующих n взаимно незнакомых пар.

В любом другом случае найдутся три человека в G (назовём их A, B и C) таких, что A знаком с B, но не знаком с C. Рассмотрим множество H, полученное исключением A, B, C из множества G. Тогда H состоит из t-3=r(m-1,n-1) людей.

По определению r(m-1,n-1) в A найдутся 2(m-1) людей, образующих (m-1) взаимно знакомых пар, или найдутся 2(n-1) людей, образующих (n-1) взаимно незнакомых пар. В первом случае добавим пару знакомых A и B, во втором случае добавим пару незнакомых A и C.

Очевидно, что r(m,1)=2m для всех m. Значит, неравенство r(m,n)<=2m+n-1 выполняется при n=1, что нам даёт базу индукции.

Значит, по индукции

r(m,n)<=r(m-1,n-1)+3<=2(m-1)+(n-1)-1+3=2m+n-1,

что завершает доказательство.