Встреча у 50 школьников

[daogiauvang]

На встрече клуба математиков есть 50 школьников, в любых 3 школьниках существует 2 школьника, которые знают друг друга. Найти минимальное значение знакомых пар.

-- Вс сен 25, 2016 06:52:02 --

По-моему это минимальное значение равно количеству диагоналей 50-стороный многоугльник.

[staric]

Для 6 школьников хватит и 6 пар, а диагоналей 9.

[DeBill]

Пусть в нашем графе $M$ ребер из $N = 25\cdot 49$ возможных.
Пусть вершины $x,y$ не соединены, $d(x)$ - степень вершины $x$. Тогда $d(x) + d(y) \geqslant 48$ (ибо для любой прочей вершины $z$ она соединена либо с $x$, либо с $y$, либо с обоими двумями). Сложив все эти неравенства (их - $N-M$ штук), получим здоровенную сумму $\Sigma$, которая не меньше $ 48\cdot (N-M)$.
В эту сумму каждое число $d(x) $ входит ровно $49 - d(x)$ раз. Но $X\cdot (49 - X ) \leqslant 25\cdot 24$, так что $\Sigma \leqslant 50\cdot 25 \cdot 24$.
Из этих неравенств имеем $M \geqslant 25\cdot 24$.
Пример (по мотивам staric): 25 мальчиков и 25 девочек, все однополые дружат друг с другом. Тогда ровно стоко ребер, а из любых трех есть два однополых...

[daogiauvang]

Спасибо. Очень интересное решение.