- Начну с того, что пересечение отрезков – это точка или интервал, в котором они имеют общие точки.
- Предположим, что у Маши есть 11 отрезков; Нам нужно узнать, верно ли, что они могут пересекаться ровно с 7 другими.
- Если мы представим каждый отрезок как вершину и каждое пересечение как ребро, то можно создать граф.
- В данном случае у нас будет 11 вершин (отрезков) и 7 ребер (пересечений).
- Согласно принципу Дирихле, в графе с p-вершинами и q-ребрами, где p > q, будет как минимум одна вершина с не менее, чем p ⏤ q 1 ребрами.
- В нашем случае имеем 11 вершин и 7 ребер. p > q٫ поэтому есть вершина с не менее٫ чем 11 ─ 7 1 5 ребрами.
- Таким образом, наш граф обязательно имеет хотя бы одну вершину с 5 ребрами, а следовательно, Маша права – возможно построить 11 отрезков так, чтобы они пересекались ровно с 7 другими.