1/2 финала. Вариант 2 (10)

Будем вершинами графа обозначать шахматистов, а ребрами — встречи, закончившиеся не вничью. По условию, в графе нет циклов длины 3 (треугольников). Покажем, что максимум числа ребер (минимум ничьих) достигается на двудольном графе. Легко видеть, что в двудольном графе может быть не менее 12 ничьих.

При этом возможен случай (см. рисунок), когда ничьих ровно 12.

Если в графе есть цикл длины 5, то в этом пятиугольнике нет диагоналей (иначе образуется треугольник) — получаем уже пять ничьих. Каждый из трех оставшихся шахматистов должен свести вничью хотя бы три партии с шахматистами из этой пятерки — получаем еще не менее 3 × 3 = 9 ничьих. Еще одна ничья должна быть во встрече между этими тремя оставшимися шахматистами. Итого в этом случае будет не менее 5 + 9 + 1 = 15 ничьих, что более 12.

Если есть цикл длины 7, то либо в этом семиугольнике нет диагоналей (тогда получаем уже 14 ничьих), либо диагональ, отсекающая треугольник (противоречие условию), либо диагональ, отсекающая пятиугольник - тогда сводим случай к предыдущему, получаем, что и в этом случае минимум не достигается.

Граф двудольный тогда и только тогда, когда в нем нет циклов нечетной длины. Перебирая возможные двудольные графы на 8 вершинах (2-6, 4-4), получаем минимум на указанном выше графе, отсюда минимальное число ничьих 12.