Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

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