Question

Пусть n — целое положительное число. В Королевстве Селлке Аравия насчитывается 2018n+1 городов. Король Марк хочет построить дороги с двусторонним движением, соединяющие определенные пары городов, так что для каждого города C и целого числа $1\le i\le 2018,$ существует ровно n городов, которые находятся на расстоянии i от C. (Расстояние между двумя городами – это наименьшее количество дорог на любом пути между двумя городами.) Для каких n Марк может добиться этого?

Answer 1

Рассмотрим граф $G$ с городами в качестве вершин и дорогами в качестве ребер. Тогда каждая вершина имеет степень $n$, поэтому

$\sum_{v\in V(G)}\deg v = n(|V(G)|)=n(2018n+1)$

Поскольку $\sum \deg v$ всегда четная, то $n$ должно быть четным.

Теперь приведем конструкцию для четных $n$. Для удобства пусть $n=2m$ и $N=2018n+1=4036m+1$. Пометим вершины $0, 1, \dots, N-1$ и соединим $i$ и $j$, если

$i-j\equiv \pm 1, \pm 2, \dots, \pm m\pmod N$

Этот граф полностью симметричен, поэтому достаточно показать, что это свойство выполняется для вершины $0$. Разобьем остальные вершины на множества

$S_k=\{km+1, km+2, \dots, (k+1)m\}, \ \ 0\le k\le 4035$

Тогда $|S_k|=m$, и именно вершины в $S_{i-1}$ и $S_{4036-i}$ находятся на расстоянии $i$ от $0$. Условие выполняется для вершины $0$, а значит, и для всех вершин

Приведем пример, в котором $2018$ заменено на $2$ и $n=4$. В этом случае имеем $S_0=\{1, 2\}$, $S_1=\{3, 4\}$, $S_2=\{5, 6\}$, $S_3=\{7, 8\}$. Тогда вершины в $S_0$ и $S_3$ находятся на расстоянии $1$, а вершины в $S_2$ и $S_3$ - на расстоянии $2$