, 2023

Let the castles be the vertex set $V$, the roads be the edge set $E$, and the number of guards be the edge weights, forming a weighted graph. We will perform a series of operations on this graph so that the King's policy continues to be satisfied, and the number of guards does not decrease.

Define $W(ab)$ to be the weight on edge $ab$, and $W(a) = \sum_{ab \in E} W(ab)$ to be the sum of weights of all edges connected to vertex $a$. Furthermore, for any two non-adjacent vertices $a$ and $b$, define them to be equivalent if and only if, for every other $c \in V$, $ac$ is an edge with $W(ac) = t$ if and only if $bc$ is an edge with $W(bc) = t$.

Now consider the following operation: if there exist two vertices $a$, $b$ that are neither adjacent nor equivalent, suppose $W(a) \ge W(b)$, then for all $c \ne a, b$, change $W(bc)$ to $W(ac)$. Note that:
1. Since $W(a) \ge W(b)$, under this operation $\sum_{v \in V} W(v)$ does not decrease;
2. Since $ab$ is not an edge, $a$ and $b$ cannot simultaneously belong to the three castles or four castles mentioned in the policy, so the policy is still satisfied after the operation;
3. Each operation strictly decreases the total number of equivalence classes, so the operation stops after at most $N-1$ times.

Note that in the graph after the operations stop, any two non-adjacent vertices must be equivalent, so it must be a complete $k$-partite weighted graph. Also note that if any edge has weight $4$, then by policy (1), $k$ must be $2$, and the total number of edges of a complete bipartite graph is at most $(N/2)^2$, so the total weight $\le 4 \times (N/2)^2 = N^2$.

So suppose no edge has weight $3$ [note: this should be weight $4$], and the number of vertices in each of the $k$ parts are $n_1, n_2, \dots, n_k$ respectively. Note that policy (2) forces each part to have edges of weight $3$ going out to at most two other parts. Hence, if we consider the subgraph obtained by keeping only one vertex from each part, and keeping only the edges of weight $3$, then every vertex in this subgraph has degree at most $2$, so it must be a disjoint union of paths and/or cycles. Since adding edges to the subgraph to turn paths into cycles corresponds to increasing the total weight in the original graph, without loss of generality assume the subgraph is a disjoint union of $p$ cycles. Then for each cycle $c_1c_2\cdots c_s$, its corresponding total weight in the original graph is
$$3(n_{c_1}n_{c_2} + \cdots + n_{c_s}n_{c_1}) \le 3(n_{c_1}^2 + \cdots + n_{c_s}^2)$$
where the inequality is the rearrangement inequality. Hence, in the case where all other edges have weight $2$, the total weight of the original graph is
$$\begin{aligned} & 2 \times \#\{ab : W(a, b) = 2\} + 3 \times \#\{ab : W(a, b) = 3\} \\ & \le 2 \times \#\{ab\} + \#\{ab : W(a, b) = 3\} \\ & \le 2 \sum_{i \ne j} n_i n_j + \sum_{i=1}^k n_i^2 = \left(\sum_{i=1}^k n_i\right)^2 = N^2. \end{aligned}$$