Азиатско-Тихоокеанская математическая олимпиада, 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
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.