Câu hỏi 134
Một quốc gia gồm $n$ hòn đảo. Một số hòn đảo được nối với nhau bằng các cây cầu, và các cây cầu chỉ giao nhau tại các hòn đảo. Mỗi cây cầu có một mức phí qua cầu là số nguyên dương. Một đường đi được định nghĩa là một dãy các cây cầu sao cho hai cây cầu liên tiếp bất kì có chung một đầu mút tại cùng một hòn đảo.
Chứng minh rằng $n$ hoặc $n-2$ là số chính phương nếu các điều kiện sau được thỏa mãn:
* Giữa hai hòn đảo bất kì có đúng một đường đi nối chúng.
* Tổng chi phí đi qua mỗi đường đi là đôi một khác nhau và không vượt quá $N = \frac{n(n-1)}{2}$.
Ví dụ, xét trường hợp có bốn hòn đảo $A, B, C$ và $D$, với các mức phí $d(A, B) = 1$, $d(A, C) = 2$ và $d(A, D) = 4$. Cấu hình này thỏa mãn các điều kiện đã cho.
(Bilegdemberel Bat-Amgalan)
Chứng minh rằng $n$ hoặc $n-2$ là số chính phương nếu các điều kiện sau được thỏa mãn:
* Giữa hai hòn đảo bất kì có đúng một đường đi nối chúng.
* Tổng chi phí đi qua mỗi đường đi là đôi một khác nhau và không vượt quá $N = \frac{n(n-1)}{2}$.
Ví dụ, xét trường hợp có bốn hòn đảo $A, B, C$ và $D$, với các mức phí $d(A, B) = 1$, $d(A, C) = 2$ và $d(A, D) = 4$. Cấu hình này thỏa mãn các điều kiện đã cho.
(Bilegdemberel Bat-Amgalan)