Ignore...

Translate this into graph terminology, let cities be vertices and roads edges. Label the vertices $v_1,v_2, \cdots v_{2018n+1}$. Clearly $n$ can not be odd because this would result into having an odd sum of degrees of vertices. For $n=2m$ connect vertex $v_i$ with vertices $v_{i\pm 1},v_{i\pm 2} \cdots, v_{i\pm m}$, where indices are taken modulo $2018n+1$.

MNJ2357 wrote: Already posted here. I don't know what you're talking about.

whatshisbucket wrote: Let $n$ be a positive integer. There are $2018n+1$ cities in the Kingdom of Sellke Arabia. King Mark wants to build two-way roads that connect certain pairs of cities such that for each city $C$ and integer $1\le i\le 2018,$ there are exactly $n$ cities that are a distance $i$ away from $C.$ (The distance between two cities is the least number of roads on any path between the two cities.) For which $n$ is it possible for Mark to achieve this? Proposed by Michael Ren All even $n$ works. It can be proved by double counting that $n$ must be even. For an example consider the graph with vertices $V_1,V_2,\ldots,V_{2018n+1},$ and $V_i$ and $V_j$ are adjacent iff $|i-j|\le \tfrac{n}{2}.$ (Obviously, $V_i$s are cities and edges are bridges.)

This problem is quite interesting when we change 2018 to an odd integer.

For a fixed vertex $u$, the sum of distances from $u$ to the other vertices is given by $$\sum_{i=1}^{2018} i \cdot n = n \cdot 1009 \cdot 2019$$ Summing over all vertices $u$ of the graph, we get that $$\sum_{\{u,v\} \in G} d(u,v) = 1009 \cdot 2019 \cdot n \cdot (2018n+1)$$ But $\sum_{\{u,v\} \in G} d(u,v)$ is even because each distance is counted twice. Thus $n$ is even. We show that all even $n$ work. Arrange the $2018n+1$ points on the circle uniformly, and join each vertex to $n$ nearest points along the circle.

Does one need to prove why the construction works?

Here was my solution on contest, almost verbatim. The answer is all even $n$. Consider the graph $G$ with cities as vertices and roads as edges. Then each vertex has degree $n$, so $$\sum_{v\in V(G)}\deg v = n(|V(G)|)=n(2018n+1).$$Since $\sum \deg v$ is always even, $n$ must be even. Now we provide a construction for even $n$. For convenience, let $n=2m$ and $N=2018n+1=4036m+1$. Label the vertices $0, 1, \dots, N-1$ and connect $i$ and $j$ if $$i-j\equiv \pm 1, \pm 2, \dots, \pm m\pmod N.$$This graph is completely symmetric, so it suffices to show that the property holds for vertex $0$. Partition the other vertices into sets $$S_k=\{km+1, km+2, \dots, (k+1)m\}$$for $0\le k\le 4035$. Then $|S_k|=m$, and exactly the vertices in $S_{i-1}$ and $S_{4036-i}$ are distance $i$ away from $0$. Thus, the condition is satisfied for vertex $0$, and therefore for all vertices. Here is an example where $2018$ is replaced by $2$ and $n=4$. [asy][asy] size(150); defaultpen(fontsize(10pt)); pair A0, A1, A2, A3, A4, A5, A6, A7, A8; A0 = dir(90); A1 = dir(50); A2 = dir(10); A3 = dir(330); A4 = dir(290); A5 = dir(250); A6 = dir(210); A7 = dir(170); A8 = dir(130); draw(A0--A1--A2--A3--A4--A5--A6--A7--A8--cycle); draw(A0--A2--A4--A6--A8--A1--A3--A5--A7--cycle); dot("$0$", A0, dir(A0)); dot("$1$", A1, dir(A1)); dot("$2$", A2, dir(A2)); dot("$3$", A3, dir(A3)); dot("$4$", A4, dir(A4)); dot("$5$", A5, dir(A5)); dot("$6$", A6, dir(A6)); dot("$7$", A7, dir(A7)); dot("$8$", A8, dir(A8)); [/asy][/asy] In this case, we have $S_0=\{1, 2\}$, $S_1=\{3, 4\}$, $S_2=\{5, 6\}$, $S_3=\{7, 8\}$. Then the vertices in $S_0$ and $S_3$ are distance $1$ away, and the vertices in $S_2$ and $S_3$ are distance $2$ away.

Let $G$ be the obvious graph. Note that $G$ is $n$-regular, so we must have that $n(2018n+1)$ is even, or that $\boxed{2\mid n}$. We now show that all even $n$ work. Let the vertex set of $G$ be $\mathbb{Z}/(2018n+1)\mathbb{Z}$, and connect $i$ and $j$ if and only if $i-j\in\pm\{1,2,\ldots,n/2\}$. We show the property for the vertex $0$, all others follow by symmetry. Note that the vertices $\pm\{1,2,\ldots,n/2\}$ are a distance $1$ from $0$, the vertices $\pm\{n/2+1,\ldots,n\}$ are a distance $2$, and so on. In general, the vertices $\pm\{(i-1)n/2+1,\ldots,in/2\}$ are a distance $i$ from $0$ for $1\le i\le 2018$. This can be shown by induction on $i$. Therefore we have shown that the answer is $n$ even.

sunfishho wrote: Does one need to prove why the construction works? I think no points were deducted if it was obvious why the construction works. (In my opinion though, one should at least claim that it is obvious rather than omitting it entirely, since it's part of the problem.)

Nice and easy. Here's my solution (Quite similar to the above ones, but posting just for practice): Consider a graph $\mathcal{G}$ with $2018n+1$ vertices, such that each vertex represents a city in the Kingdom of Sellke Arabia, and two vertices are connected by an edge if there is a road between the corresponding cities. We claim that all even $n$ work. To see this, suppose that $n=2m$. Label the vertices of the graph $\mathcal{G}$ as $\{v_1,v_2, \dots ,v_{4036m+1}\}$ in any arbitrary order. Join two vertices $v_j$ and $v_k$ iff $|j-k| \leq m$, where all indices are taken modulo $4036m+1$. Now notice that $v_1$ is at a distance $i$ from all vertices $v_s$ such that $(i-1)m+2 \leq s \leq im+1$ or $(4036-i)m+2 \leq s \leq (4036-i+1)m+1$, and thus $v_1$ satisfies the given condition. Then, by the symmetry of our construction, we get that every vertex of our graph satisfies the given condition. So all that remains to be done is show that odd $n$ doesn't work. For this purpose, note that by applying the given condition on $i=1$, we see that each vertex has degree $n$, and so the sum of the degrees of each vertex is equal to $n(2018n+1)$. As both $n$ and $2018n+1$ are odd, so we get that the sum of the degrees is also odd. But this is not possible as the sum of the degrees is equal to $2|E|$, which means that it is always even. Thus, no odd $n$ works. Hence, done. $\blacksquare$

We claim the answer is $n$ even. Obviously we first convert the kingdom into a graph; roads become edges and cities become vertices. The degree of each vertex is $n$, since there are $n$ vertices with distance 1. The sum of all degrees over the entire graph is then $n(2018n+1)$, so the number of edges is $\tfrac12 n(2018n+1)$. This is integer if and only if $n$ is even. We claim that in fact all $n$ even work, and we will provide a construction. Arrange the vertices in a circle and number them from $0$ to $2018n$. We define the length of the edge that connects vertices $i$ and $j$ as $|i-j| \pmod{2018n+1}$. Draw all edges of length $1,2,\ldots,n/2$. We claim this graph satisfies the condition that for any vertex $C$ and for all $1\le i\le 2018$, there are exactly $n$ vertices that are a distance $i$ from $C$. WLOG let $C=0$. The vertices in the set $\{in/2+1,\ldots,(i+1)n/2\}$ are a distance $i$ away from $0$. This is because we can think of each group of $n/2$ vertices (starting at vertex $1$) has a fixed distance from 0, and each group has a distance of $1$ more than the previous group. Similarly, the vertices in the set $\{(2018-i)n/2+1,\ldots,((2018-i)+1)n/2\}$ are a distance $i$ away from $0$. Since both these sets have $n/2$ elements, the total number of vertices that are a distance $i$ from $0$ are $n$, as desired.

I claim that our answer is all even $n$. Clearly odd $n$ do not work, since choosing $i = 1$ tells us that each vertex has degree $n$. Thus, the total sum of degrees is $n(2018n+1)$, which is odd if $n$ is odd, impossible. Now we find a construction for even $n = 2k$. Then, the graph is on $2018n + 1 = 4036k + 1$ vertices. Arrange them in a circle and label these vertices $0, 1, \ldots , 4036k$. We connect all paths $ij$ such that $|i-j| \in [1, k]$. It remains to show that this construction works. We show this for one vertex, say vertex $0$. Notice that the vertices $\in [\tfrac{mk}{2} + 1, \tfrac{(m+1)k}{2}]$ have "distance" $m$ to vertex $0$. Thus, we cam pair $m \to 2018 - m$ and therefore we get the desired $k$ vertices that are distance $m$ away from $0$. Since this construction is symmetric this generalizes to other vertices and we are done. $\blacksquare$

liekkas wrote: This problem is quite interesting when we change 2018 to an odd integer. Exactly...I would love to see what happens when k = 2018 (in the problem) is an odd integer. Does it also have a defined solution set or is it random?

First find for which n does the construction work., From the handshake lemma we see that $$\sum_{i=1}^{n} d(V_i)=2|E|$$,where $d(V_i)$ denotes the degree of a vertex, and $|E|$- means the number of edges Since we know that each city is connected to $n$ other cities, it means that the degree of each city is $d(V_i)=n$ ,now since we have $2018n+1$ vertixes ,it means from the handshake lemma that $(2018n+1)n=2\cdot |E|$. $2018n^2+n=2\cdot |E|$. which means that $n$-even Now make a construct that works for $n$-even.Take a regular $2018n+1$-gon and draw edges that connect vertixes $n\2$ appart.

REDACTED

The answer is $\boxed{\text{all even }n}.$ $\emph{Construction: }$ Label the cities $1,2,\dots,2018n+1,$ and build a road between cities $i$ and $j$ is $|i-j|\equiv2,4,\dots,$ or $n$ modulo $2018n+1.$ $\emph{Proof: }$ Since there are exactly $n$ cities a distance of $1$ from any given city, the degree of each city is $n.$ But this implies that the sum of the degrees of the cities is $n(2018n+1),$ which is odd. This is a contradiction as the sum of the degrees of the vertices of any graph is twice the number of edges.

The answer is even $n$. Note that this condition implies that every city has $n$ roads going out of it; thus, Mark will have to construct \[ \frac{(2018n+1) \cdot n }{2}\]roads in total, which is not an integer when $n$ is odd. The construction (pun intended) for even $n$ is as follows: arrange these cities in a circle. Define the space between two cities $X$ and $Y$ as one plus the number of cities that lie on minor arc $XY$, not including $X$ or $Y$. Then, we construct a road between any two cities whose space between them is no more than $\frac{n}{2}$. As a result of this construction, we can now think of a citizen of Sellke Arabia as a grasshopper that can hop up to $\frac{n}{2}$ cities in one jump. Therefore, cities with a space of $x$ between them are separated by a distance of \[ \left \lceil \frac{x}{\frac{n}{2}} \right \rceil, \]which clearly satisfies the conditions specified in the problem.

The answer is all even $n$. For odd $n$, notice that the sum of $d(u, v)$ across all pairs $(u, v)$ is equal to $n(2018n+1) \cdot 1009 \cdot 2019$, which is odd, but this is impossible as each path is counted twice. For even $n$, place the vertices $v_1, v_2, \dots, v_{2018n+1}$ on a circle, such that $v_i$ is connected to $v_{i \pm j}$ for all $j \leq \frac n2$ (here indices are cyclic.)

Let the i fixed . name the cities v1, .... , vk (k=2018n+1) . consider a graph with vertices v1,..,vk and draw the edge vj vt (for some j and t ) if dist(vj,vt) = i . note that degree of each verterx is n and using handshaking lemma n must be even(since k is odd). example is like other solutions.

The answer is even $n$. Let the Kingdom be an undirected graph, where the cities are vertices. Notice that if $n$ was odd, then the sum of the degrees of the vertices is $n\cdot (2018 n + 1)$, which is odd, but it is $2$ times the number of edges, contradiction. Thus, $n$ must be even. Now we provide a construction. Consider labelling the vertices as $v_1, v_2, \ldots, v_{2018 n + 1}$ and connecting $v_i$ to $v_{i - n/2}, v_{i - n/2 + 1}, \ldots, v_i , v_{i + 1} , \ldots, v_{i + n/2}$ where indices are taken modulo $2018n + 1$. This clearly works, so we are done.

All even $n$ work. Otherwise if $n$ is odd, then the number of degree (distance $ = 1$ case) is $=n$ and there are odd number of vertices. Summing up gives a contradiction to parity. For the construction, select a random vertex temporarily and group the $2018$ consecutive vertices into a group. From the selected vertex, draw an edge to the $2018$th vertex of every group that fall to the left of the axis of symmetry passing through the selected vertex, and for the other half, draw an edge to the $1$st vertex of each group. Do the same for the other vertices. Here is a diagram below to explain the construction more explicitly for the case after changing $2018$ to $6$. [asy][asy] /* Converted from GeoGebra by User:Azjps using Evan's magic cleaner https://github.com/vEnhance/dotfiles/blob/main/py-scripts/export-ggb-clean-asy.py */ /* A few re-additions are done using bubu-asy.py. This adds the dps, xmin, linewidth, fontsize and directions. */ pair A = (-2.42856,5.82298); pair B = (-14.09273,4.26776); pair C = (-25.00369,-0.13936); pair D = (-34.47585,-7.12147); pair E = (-41.91404,-16.23985); pair F = (-46.85090,-26.92157); pair G = (-48.97622,-38.49545); pair H = (-48.15646,-50.23426); pair I = (-44.44314,-61.40041); pair J = (-38.06957,-71.29228); pair K = (-29.43623,-79.28835); pair L = (-19.08557,-84.88617); pair M = (-7.66798,-87.73403); pair N = (4.09912,-87.65298); pair O = (15.47640,-84.64811); pair P = (25.74896,-78.90823); pair Q = (34.27134,-70.79400); pair R = (40.50804,-60.81527); pair S = (44.06719,-49.59903); pair T = (44.72517,-37.85004); pair U = (42.44061,-26.30653); pair V = (37.35708,-15.69384); pair W = (29.79399,-6.67878); pair Z = (20.22655,0.17218); pair A_1 = (9.25592,4.42858); import graph; size(10cm); pen dps = linewidth(0.5) + fontsize(13); defaultpen(dps); real xmin = -5, xmax = 5, ymin = -5, ymax = 5; draw(A--M, linewidth(0.5) + blue); draw(A--N, linewidth(0.5) + blue); draw(A--G, linewidth(0.5) + blue); draw(A--T, linewidth(0.5) + blue); draw(N--B, linewidth(0.5)); draw(B--O, linewidth(0.5)); draw(O--C, linewidth(0.5)); draw(C--P, linewidth(0.5)); draw(P--D, linewidth(0.5)); draw(D--Q, linewidth(0.5)); draw(Q--E, linewidth(0.5)); draw(E--R, linewidth(0.5)); draw(R--F, linewidth(0.5)); draw(F--S, linewidth(0.5)); draw(S--G, linewidth(0.5)); draw(G--T, linewidth(0.5)); draw(T--H, linewidth(0.5)); draw(H--U, linewidth(0.5)); draw(U--I, linewidth(0.5)); draw(I--V, linewidth(0.5)); draw(V--J, linewidth(0.5)); draw(J--W, linewidth(0.5)); draw(W--K, linewidth(0.5)); draw(K--Z, linewidth(0.5)); draw(Z--L, linewidth(0.5)); draw(L--A_1, linewidth(0.5)); draw(A_1--M, linewidth(0.5)); draw(H--B, linewidth(0.5)); draw(B--U, linewidth(0.5)); draw(I--C, linewidth(0.5)); draw(C--V, linewidth(0.5)); draw(J--D, linewidth(0.5)); draw(D--W, linewidth(0.5)); draw(K--E, linewidth(0.5)); draw(E--Z, linewidth(0.5)); draw(L--F, linewidth(0.5)); draw(F--A_1, linewidth(0.5)); draw(M--G, linewidth(0.5)); draw(H--N, linewidth(0.5)); draw(I--O, linewidth(0.5)); draw(J--P, linewidth(0.5)); draw(K--Q, linewidth(0.5)); draw(L--R, linewidth(0.5)); draw(M--S, linewidth(0.5)); draw(N--T, linewidth(0.5)); draw(O--U, linewidth(0.5)); draw(P--V, linewidth(0.5)); draw(Q--W, linewidth(0.5)); draw(R--Z, linewidth(0.5)); draw(S--A_1, linewidth(0.5)); dot("$A$", A, NW); dot("$B$", B, NW); dot("$C$", C, NW); dot("$D$", D, NW); dot("$E$", E, NW); dot("$F$", F, NW); dot("$G$", G, NW); dot("$H$", H, NW); dot("$I$", I, NW); dot("$J$", J, NW); dot("$K$", K, NW); dot("$L$", L, NW); dot("$M$", M, NW); dot("$N$", N, NW); dot("$O$", O, NW); dot("$P$", P, NW); dot("$Q$", Q, NW); dot("$R$", R, NW); dot("$S$", S, NW); dot("$T$", T, NW); dot("$U$", U, NW); dot("$V$", V, NW); dot("$W$", W, NW); dot("$Z$", Z, NW); dot("$A_1$", A_1, NW); [/asy][/asy] Now to show that this works, note that if we color the elements $0$ to $2017$ in a group with $c_0,\ldots, c_2017$; then in $k$ moves, we can end up only on $c_k$ as the color increases by $1$ in every move.