Докажем лемму

[qwert129]

Здравствуйте, хотелось бы найти такие минимальные $f(n)$ и $g(n)$ (отличные от констант)для которых эта задача была бы верна:

Есть $2n+1$ человек. Каждый человек знаком по крайней мере с $f(n)$ людьми. Докажите, что либо найдется человек который знает всех либо найдутся $g(n)$ попарно знакомых людей.

[ihq.pl]

Если $f(n)>0$, то $\min f(n) = 1$. "Попарно знакомые" - это не знакомые друг с другом пары?

[qwert129]

ihq.pl в сообщении #1622988 писал(а):

Если $f(n)>0$, то $\min f(n) = 1$. "Попарно знакомые" - это незнакомые друг с другом пары?

они отличные от констант, желательно выразить через n

[rightways]

Пардон, нужно найти минимальное f(n) и максимальное $g(n)$

[ihq.pl]

rightways в сообщении #1623064 писал(а):

максимальное $g(n)$

Запросто может быть и минимальным.

-- 20.12.2023, 10:30 --

Мне лично видится пока только попытка обобщить задачу про семерку из соседней темы.

-- 20.12.2023, 10:35 --

Минимальное $g(n)$, как я понимаю, - это мощность максимального множества $A$ попарно знакомых в том случае, когда число незнакомых каждого из $A$ максимально, т.е. $2n-f(n)$, и множества их незнакомцев не пересекаются.....?