Олимпиада Туймаада по математике. Старшая лига. 2022 год

Патшалықта 100 қала бар, кейбір қала жұптары жолдармен қосылған. Кез келген жолмен жалғасқан $A$ және $B$ қалалары үшін олардың екеуінің біреуімен де жалғаспаған $C$ қаласы табылады. Бұл патшалықта ең көп дегенде қанша жол болуы мүмкін? ( X. Zhan, P. Qiaoa )

Комментарий/решение

Из условия понятно что у нашего графа нету треугольников. Тогда теоремой Турана для n=<8.

ex(100,3)=[100²×((3-2)/(6-2))]=2500.