Знакомства людей

Как известно, лучший способ самому разобраться в чём-то - это рассказать предмет исследования другим. Этим я сейчас и займусь.

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

Задачи такого рода часто называют задачами рамсеевского типа. Про классические числа Рамсея я уже писал раньше.

А обсуждаемая сегодня задача была предложена на 15-й Азиатско-Тихоокеанской олимпиаде в 2003 году.

Оказывается, что ответ в этой задаче - это 2(m+n)-min{m,n}-1.

Будем считать, что m>=n. Тогда ответ, назовём его R(m,n), можно представить в виде 2m+n-1.

Для начала приведём пример, показывающий, что R(m,n)>=2m+n-1.

Рассмотрим (2m-1) человек, среди которых все попарно знакомы, и (n-1) человек, которые ни с кем не знакомы. Понятно, что в такой компании нет ни m пар знакомых, ни n пар незнакомых. Поэтому, R(m,n)>2m+n-2.

Теперь надо доказать, что 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)+(m-1)-1+3=2m+n-1>=2m>=2n.

Если в G найдутся 2m людей, которые попарно знакомы, то найдутся и m пар взаимно знакомых пар. Если же в G найдутся 2n людей, которые попарно незнакомы, то мы тоже победим, потому что найдётся n пар взаимно незнакомых людей.

В любом другом случае найдутся три человека в G (назовём их u, v, w), что u знаком с v, но u не знаком с w.

Рассмотрим множество T, полученное исключением u, v, w из множества G. В множестве T ровно t-3=R(m-1,n-1) людей. В T найдется либо (m-1) пар знакомых, либо (n-1) пар незнакомых. В первом случае добавим пару знакомых (a,b), во втором случае добавим пару (a,c).

Осталось проверить базу индукции. Но очевидно, что R(s,1)=2s.