Câu hỏi 78
Một quốc gia có $n$ thành phố. Giữa hai thành phố bất kỳ có đúng một con đường, và mọi con đường đều được quy định chỉ đi một chiều. Một đường đi từ thành phố $X$ đến thành phố $Y$ là một dãy các con đường một chiều sao cho có thể đi từ $X$ đến $Y$ theo các con đường đó mà không ghé thăm thành phố nào hai lần. Một tập các đường đi được gọi là độc lập khi và chỉ khi không có hai đường đi nào trong tập dùng chung một con đường.
Với mỗi thành phố $X$, gọi $n_X$ là số con đường một chiều đi ra từ $X$. Với hai thành phố phân biệt $X$ và $Y$, gọi $N_{XY}$ là số lớn nhất có thể của số đường đi từ $X$ đến $Y$ trong một tập đường đi độc lập. Chứng minh rằng $N_{XY} = N_{YX}$ khi và chỉ khi $n_X = n_Y$.
Với mỗi thành phố $X$, gọi $n_X$ là số con đường một chiều đi ra từ $X$. Với hai thành phố phân biệt $X$ và $Y$, gọi $N_{XY}$ là số lớn nhất có thể của số đường đi từ $X$ đến $Y$ trong một tập đường đi độc lập. Chứng minh rằng $N_{XY} = N_{YX}$ khi và chỉ khi $n_X = n_Y$.