Bài làm :
Gọi $X$ là thành phố có nhiều đường đi liên quan nhất ( theo nghĩa tổng số đường đi từ $X$ đến thành phố khác và từ thành phố khác đến $X$ là lớn nhất ).
Ta chia $209$ thành phố còn lại làm $3$ nhóm : Nhóm $A$ gồm tất cả các thành phố có đường đi một chiều tới $X$, nhóm $B$ gồm các thành phố mà từ $X$ có đường đi một chiều tới và nhóm $C$ bao gồm các thành phố còn lại (trừ X). Đặt $a,b,c$ lần lượt là số phần tử của $A, B, C$. Khi đó, số đường đi có liên quan tới $X$ là $a+b$ và $a+b+c =209$.
Ta có một số nhận xét sau
$\bullet$ Giữa các thành phố cùng thuộc nhóm A không có đường đi nối với nhau.
C/minh: giả sử $A_1,A_2$ là 2 thành phố cùng thuộc $A$ sao cho có đường đi nối giữa $A_1$ và $A_2$, không mất tổng quát giả sử đó là đường đi từ $A_1$ tới $A_2$. Khi đó có đường đi từ $A_1$ tới $A_2$ và từ $A_2$ tới $X$, nên theo giả thiết không có đường đi từ $A_1$ tới $X$, vô lí vì $A_1 \in A $
Tuơng tự, giữa các thành phố cùng thuộc nhóm B không có đường đi nối với nhau.
Từ đó, số đường đi nối giữa các thành phố thuộc $A$ và $B$ không lớn hơn $ab$.
$\bullet$ Số đường đi liên quan tới các thành phố thuộc nhóm $C$ không lớn hơn $c(a+b)$.
Thật vậy, vì nếu ngược lại thì theo nguyên lí Đirichlet tồn tại một thành phố thuộc $C$ có số đường đi liên quan lớn
hơn $a+b$, mâu thuẫn với cách chọn $X$.
Từ các nhận xét trên ta suy ra số con đường có thể xây dựng không lớn hơn: $a+b+ab+c(a+b)$.
Ta có $P = a+b+ab+c(a+b) \leq a+b+\frac {(a+b)^2} {4} + (209 -a-b)(a+b) = 2d + d^2+2d(209 -2d) = - 3(d-70)^2 + 3.70^2 \leq 14700$.
(với $d= \frac {a+b} {2} $)
Ta chỉ ra một cách xây dựng đường đi thoả mãn yêu cầu bài toán.
Chia $210$ thành phố thành 3 nhóm $A,B,C$, mỗi nhóm có 70 thành phố. Với mỗi bộ ba thành phố $X,Y,Z$ với $X \in A, Y \in B, Z \in C$ thì ta xây dựng đường đi theo quy tắc $X \Rightarrow Y \Rightarrow Z \Rightarrow X$. Dễ thấy cách xây dựng này thoả yêu cầu bài. Khi đó số bộ thành phố là $70^3$, với mỗi bộ có $3$ con đường được xây và mỗi con đường được tính lặp lại $70$ lần nên số đường đi là $3.70^2=14700$.
Tóm lại, số đường đi nhiều nhất có thể là $14700$