Қалалық Жәутіков олимпиадасы, 9 сынып, 2017 жыл

Елде $2n$ қала бар. Кез келген үш қала үшін, түзу жолмен қосылмаған екі қала табылатыны белгілі. Елде ең көп дегенде қанша жол бар екенін табыңыз.

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Докажем индукцией по $n\in \mathbb{N}$, что если в графе с $2n$ вершинами никакие три ребра не образуют треугольника, то число ребер не превосходит ${{n}^{2}}$. Для $n=1$ число ребер всегда не превосходит $1={{n}^{2}}$.
Пусть утверждение доказано для числа $n$. Докажем его для числа $n+1$. Пусть имеется граф с $2\left( n+1 \right)$ вершинами, никакие три ребра которого не образуют треугольник. Выберем две вершины, соединенные ребром (если в графе нет ни одного ребра, то все доказано). Тогда каждая из оставшихся $2n$ вершин соединена ребром не более чем с одной, из выбранных вершин. Эти $2n$ вершин соединены между собой, по предположению индукции, не более чем ${{n}^{2}}$ ребрами. Тогда общее число ребер не превосходит ${{n}^{2}}+2n+1={{\left( n+1 \right)}^{2}}$. Утверждение доказано.
Наконец, если $2n$ вершин разделить на два множества по $n$ вершин, а затем любые две вершины, лежащие в разных множествах, соединить ребрами, то получится граф с ${{n}^{2}}$ ребрами, не содержащий ни одного треугольника.