Даны два натуральных числа 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,
что завершает доказательство.
