На каждом ребре полного графа с 2019 вершинами написано число 1,2 или 3 так, что сумма чисел на рёбрах каждого треугольника не меньше 5. Какова наименьшая возможная сумма всех чисел на рёбрах?
Подсказка
Пример. Выберем 1009 рёбер без общих вершин, на них напишем 1, на остальных рёбрах — 2.
Решение
Ответ. 2019.2018-1009 = 4073333.
Решение. Пример. Выберем 1009 рёбер без общих вершин, на них напишем 1, на остальных рёбрах — 2. Сумма написанных чисел будет как раз 2•(2019•2018/2)
. Оценка. Назовём вершину плохой, если из неё выходит больше одного ребра, помеченного единицей. Если в графе нет плохих вершин, то всё в порядке: ребер с единицами не больше 1009, и сумма написанных не ребрах чисел не меньше 
. Пусть плохая вершина 
есть. Возьмём ребро 
, на котором написана единица, и рассмотрим все треугольники вида 
. Если на одной из сторон 
или 
такого треугольника написана единица, то на другой должна быть тройка. Во всех таких случаях заменим эти единицу и тройку на две двойки. Сумма написанных на ребрах чисел при этом не изменится, сумма чисел на сторонах любого треугольника останется не меньше 5, а число плохих вершин уменьшится. Повторяя описанную процедуру, мы можем уничтожить все плохие вершины, а для графа без плохих вершин всё уже было доказано.