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