Маша с Варей поспорили. Маша утверждает, что можно нарисовать на плоскости 9 отрезков так, чтобы они пересекались ровно с 11 другими. Верно ли её утверждение?

Решение:

Это задача из области теории графов. Каждый отрезок можно представить как ребро графа, а каждую точку пересечения — как вершину, где пересекаются два ребра. Утверждение Маши означает, что можно построить граф с 9 рёбрами, в котором сумма степеней вершин равна 22 (так как каждое ребро соединяет две вершины, а сумма степеней вершин равна удвоенному числу рёбер).

Рассмотрим максимальное число пересечений для 9 отрезков. Если все отрезки пересекаются друг с другом, то число пересечений равно числу пар отрезков, которое вычисляется по формуле сочетаний:

\( C(n, 2) = \frac{n(n-1)}{2} \)

Для 9 отрезков это будет:

\[ C(9, 2) = \frac{9(9-1)}{2} = \frac{9 \times 8}{2} = \frac{72}{2} = 36 \]

Таким образом, 9 отрезков могут пересекаться максимум в 36 точках.

Однако, условие задачи сформулировано иначе: «чтобы они пересекались ровно с 11 другими». Это можно интерпретировать как то, что сумма количества пересечений каждого отрезка с остальными должна быть равна 11. В контексте теории графов, это относится к сумме степеней вершин, но в задачах на пересечение отрезков, обычно подразумевается общее количество точек пересечения.

Предположим, что речь идёт об общем количестве точек пересечения, и оно должно быть равно 11.

Попробуем построить пример: 9 отрезков могут дать 11 пересечений. Например, если мы расположим отрезки так, чтобы большинство из них пересекались лишь с несколькими другими.

Рассмотрим задачу с точки зрения количества точек пересечения. Для 9 отрезков максимальное количество точек пересечения равно 36. Минимальное количество пересечений (если отрезки не пересекаются) равно 0.

Если Маша утверждает, что можно нарисовать 9 отрезков так, чтобы они пересекались ровно с 11 *другими* отрезками, это может означать, что каждый отрезок пересекается в среднем с 11/9 отрезками, что не является целым числом.

Более вероятная интерпретация: общее количество точек пересечения равно 11. Это вполне возможно. Например, 3 отрезка, пересекающиеся в одной точке (3 пересечения), и 6 отрезков, пересекающихся друг с другом попарно (36 пересечений, но нам нужно 11).

Можно ли получить ровно 11 пересечений?

Рассмотрим следующий случай: 5 отрезков пересекаются в одной точке. Это 5 пересечений. Допустим, у нас есть ещё 4 отрезка, которые не пересекаются с этими 5, но пересекаются друг с другом. Максимум для 4 отрезков — 6 пересечений (C(4,2)). Тогда общее число будет 5+6 = 11. Но это не 9 отрезков.

Давайте попробуем построить конфигурацию для 9 отрезков, дающую 11 пересечений. Это возможно. Например:

1. 5 отрезков пересекаются в одной точке (5 пересечений).
2. Оставшиеся 4 отрезка проходят так, чтобы они пересекались между собой и с первыми пятью, но так, чтобы общее число пересечений было 11.

Более простая интерпретация: сумма степеней вершин равна 22. Например, один отрезок пересекает 3 других (3 пересечения), второй — 3 других (3 пересечения), третий — 3 других (3 пересечения), четвёртый — 3 других (3 пересечения), пятый — 3 других (3 пересечения). Итого 5 отрезков по 3 пересечения = 15 пересечений. Остается 4 отрезка. Нужно еще 11-15 = -4 пересечения, что невозможно.

Рассмотрим следующую структуру: 5 отрезков пересекают друг друга, давая 10 пересечений (C(5,2)=10). Тогда нужно еще 1 пересечение от оставшихся 4 отрезков. Например, один из оставшихся 4 отрезков пересекает один из первых пяти. Но это не 9 отрезков, дающих 11 пересечений.

Если мы возьмем 3 отрезка, пересекающихся в одной точке (3 пересечения), и еще 6 отрезков. Максимум для 6 отрезков - 15 пересечений. Но нам нужно 11.

Если Маша имела в виду, что *каждый* отрезок пересекается ровно с 11 другими, то это означало бы, что каждый из 9 отрезков имеет степень 11. Тогда сумма степеней была бы 9 * 11 = 99. Число ребер было бы 99/2, что не целое число. Значит, это неверная интерпретация.

Вернемся к общему количеству пересечений, равному 11.

Это возможно. Вот пример:

1. Возьмем 5 отрезков, которые пересекаются друг с другом. Число пересечений = C(5,2) = 10.
2. Теперь добавим еще 4 отрезка. Пусть один из этих 4 отрезков пересекает один из первых 5 отрезков. Это даст нам 1 дополнительное пересечение.
3. Остальные 3 отрезка добавляем так, чтобы они не создавали новых пересечений или чтобы общее число пересечений осталось 11. Это возможно, если эти 3 отрезка не пересекаются ни между собой, ни с другими отрезками, что не соответствует условию «9 отрезков» (подразумевается, что все они могут участвовать в пересечениях).

На самом деле, задача сформулирована неоднозначно. Традиционно, когда говорят «пересекались ровно с 11 другими», имеют в виду общее число точек пересечения. И это число может быть 11.

Вот более точный пример, как можно получить 11 пересечений с 9 отрезками:

1. Возьмем 4 отрезка, которые пересекаются друг с другом. Число пересечений: C(4,2) = 6.
2. Добавим еще 5 отрезков. Пусть три из этих пяти отрезков пересекают каждый из первых четырех отрезков. Это 3 * 4 = 12 пересечений. Уже слишком много.

Рассмотрим другой подход. Если каждый отрезок является ребром графа, а точка пересечения — вершиной. У нас 9 ребер. Максимальное число вершин в графе, где 9 ребер, может быть до 9+1=10 (если это цепь) или меньше.

Если утверждение Маши