Азиатско-Тихоокеанская математическая олимпиада, 2003 год

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

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

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

Для любого натурального числа $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