Условие
Имеется
m точек, некоторые из которых соединены отрезками так, что каждая
соединена с
l точками. Какие значения может принимать
l?
Решение
Так как каждую точку можно соединить не более чем с
m - 1 другими,
l <
m.
Кроме того, общее число пар вида (отрезок, конец этого отрезка) равно
lm,
а значит, общее число отрезков равно
lm/2, откуда следует, что число
lm
чётно.
Докажем, что для любых
l <
m, для которых число
lm чётно, описанная
в условии конструкция осуществима. Рассмотрим сначала случай, когда число
l
чётно. Расположим точки в вершинах правильного
m-угольника и проведём
те хорды, по какую-нибудь сторону от которых лежит не более
- 1
вершин многоугольника. Тогда каждая вершина будет соединена ровно с
l
другими. Рассмотрим теперь случай, когда число
l нечётно, а число
m
чётно. Расположим точки в вершинах двух правильных (
m/2)-угольников.
Разобьём все вершины на пары так, чтобы в каждой паре была одна вершина
первого многоугольника и одна вершина второго многоугольника. Соединим
отрезком получившиеся пары вершин, а в каждом многоугольнике соединим вершины
так, чтобы каждая вершина была соединена ровно с
l - 1 другими.
Источники и прецеденты использования
