Processing math: 100%

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


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

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

  0
22 дней 6 часов назад #

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

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