На турнир приехало 100 человек. Из любых пяти из них можно по крайней мере двумя способами выбрать трех попарно знакомых. Докажите, что среди них есть по крайней мере 4850 пар знакомых.
Подсказка
Рассмотрим граф, вершинами которого являются участники турнира, а ребрами — пары участников, незнакомых между собой. Если в этом графе есть треугольник 
, то в любой пятерке 
участники 
и 
должны быть знакомы между собой, и каждый из них должен быть знаком с двоими из тройки .
Решение
Рассмотрим граф, вершинами которого являются участники турнира, а ребрами — пары участников, незнакомых между собой. Если в этом графе есть треугольник , то в любой пятерке участники и должны быть знакомы между собой, и каждый из них должен быть знаком с двоими из тройки . Тогда пар знакомых получается не меньше, чем 
. Дальше будем считать, что треугольников нет. Пусть есть цикл 
длины 4. Добавляя сюда произвольного участника , находим, что он дружит со всеми участниками из этого цикла, 
дружит с 
и 
дружить с . Таким образом, каждый цикл длины 4 в нашем графе является компонентой связности. Заметим далее, что в нашем графе нет незамкнутых путей длины 4: если есть такой путь , то в пятерке нет двух троек попарно знакомых. Поэтому нет и циклов длины больше 4 , то есть каждая компонента связности нашего графа — либо цикл длины 4, либо дерево. Но в такой ситуации ребер у этого графа не больше, чем вершин, то есть не больше 100. Соответственно, пар знакомых не меньше, чем 
.