Bài 4
Cho số nguyên . Có trạm trên một sườn núi, tất cả ở các độ cao khác nhau. Mỗi công ty cáp treo trong hai công ty và vận hành cáp treo; mỗi cáp treo đưa khách từ một trạm tới một trạm cao hơn, không dừng ở giữa. cáp treo của có điểm xuất phát khác nhau và điểm đến khác nhau, và cáp treo nào xuất phát cao hơn thì cũng đến nơi cao hơn. Điều kiện tương tự cũng đúng với . Hai trạm được gọi là được nối bởi một công ty nếu có thể xuất phát từ trạm thấp hơn và tới được trạm cao hơn bằng cách dùng một hoặc nhiều cáp treo của công ty đó, không được di chuyển giữa các trạm bằng cách nào khác. Hãy xác định số nguyên dương nhỏ nhất để có thể đảm bảo luôn tồn tại hai trạm được nối bởi cả hai công ty.
Bước 1 trên 8: Biểu diễn mỗi công ty bằng các chuỗi tăng
Hiểu nôm na
Các điểm xuất phát và điểm đến đôi một khác nhau ngăn sự phân nhánh, còn mọi cáp treo đều đi lên, nên mạng của một công ty là tập các đường đi đơn tăng.
Phân tích chi tiết
Xét một công ty, mỗi trạm là điểm xuất phát của nhiều nhất một cáp treo và là điểm đến của nhiều nhất một cáp treo. Hướng mỗi cáp từ độ cao thấp lên cao. Vì vậy mỗi đỉnh có bậc vào và bậc ra không quá một; do độ cao tăng nghiêm ngặt trên mỗi cạnh, không thể có chu trình có hướng. Do đó các thành phần là những đường đi có hướng đôi một không giao đỉnh, kể cả các trạm cô lập. Hai trạm được công ty đó nối với nhau khi và chỉ khi chúng nằm trong cùng một thành phần đường đi.