Азия-тынық мұхит математикалық олимпиадасы, 2003 жыл

Бізге $m$ және $n$ натурал сандары берілсін. Мына шартты қанағаттандыратын ең кіші $k$ санын табыңдар: кез келген $k$ адамның ішінен немесе екі-екіден өзара таныс адамдардың $m$ парын құратын $2m$ адам, немесе екі-екіден өзара бейтаныс адамдардың $n$ парын құратын $2n$ адам табылады.

Комментарий/решение

Задача на нахождение числа Рамсея:

Для любого натурального числа $m$ и $n$, минимальное число $k$, которое гарантирует, что среди $k$ людей либо найдутся $2m$ людей, которые образуют $m$ взаимно знакомых пар, либо найдутся $2n$ людей, которые образуют $n$ взаимно незнакомых пар, называется числом Рамсея $R(m, n)$.

Формула для числа Рамсея:

R(m, n) = k разбиение множества k людей на 2 группы в одной из них будет m знакомых или n незнакомых

Для малых значений m и n числа Рамсея могут быть найдены вручную, например:

R(3, 3) = 6, R(3, 4)= 9, R(4, 4) = 18