Chestiune extremala legata de nr. de vârfuri

[Filip Chindea]

Fie \( n \in \mathbb{N}^{\ast} \). Un grup de persoane se numeste \( n \)-echilibrat daca printre oricare trei persoane gasim doua cunostinte si printre oricare \( n \) persoane gasim doua care nu se cunosc. Aratati ca orice grup \( n \)-echilibrat are cel mult \( (n-1)(n+2)/2 \) membri.

[TST III 2008, Problema 4]

[Filip Chindea]

Hint: Avem inegalitatea cu numarul Ramsey \( R(m, n) \le {m + n - 2 \choose n - 1} \).