Câu hỏi 46
Hãng *South African Magical Flights* (SAMF) khai thác các chuyến bay giữa các sân bay ở Nam Phi. Nếu có chuyến bay từ sân bay $A$ đến sân bay $B$ thì cũng có chuyến bay từ $B$ đến $A$.
Trụ sở của SAMF đặt tại Kimberley. Mỗi sân bay do SAMF phục vụ đều có thể đến được từ Kimberley theo đúng một cách. Cách đi đến Kimberley này có thể gồm việc dừng ở các sân bay khác trên đường. (Chẳng hạn, có thể xảy ra việc từ Durban đến Kimberley bằng cách bay từ Durban đến Bloemfontein rồi từ Bloemfontein đến Kimberley. Khi đó không có cách nào khác để đi từ Durban đến Kimberley. Chẳng hạn, sẽ không có chuyến bay thẳng từ Durban đến Kimberley.)
Một sân bay (khác Kimberley) được gọi là *sân bay đầu mút* nếu có chuyến bay đến (và từ) đúng một sân bay khác. Giả sử có $t$ sân bay đầu mút.
Do cắt giảm ngân sách, SAMF quyết định đóng cửa $k$ sân bay. Yêu cầu là vẫn có thể đến được từng sân bay còn lại từ Kimberley.
Gọi $C$ là số cách chọn $k$ điểm đến bị ngừng khai thác. Chứng minh rằng
$$
\frac{t!}{k!(t-k)!} \le C \le \frac{(t+k-1)!}{k!(t-1)!},
$$
trong đó $n! = 1 \times 2 \times \dots \times n$ với mọi số nguyên dương $n$, và $0! = 1$.
Trụ sở của SAMF đặt tại Kimberley. Mỗi sân bay do SAMF phục vụ đều có thể đến được từ Kimberley theo đúng một cách. Cách đi đến Kimberley này có thể gồm việc dừng ở các sân bay khác trên đường. (Chẳng hạn, có thể xảy ra việc từ Durban đến Kimberley bằng cách bay từ Durban đến Bloemfontein rồi từ Bloemfontein đến Kimberley. Khi đó không có cách nào khác để đi từ Durban đến Kimberley. Chẳng hạn, sẽ không có chuyến bay thẳng từ Durban đến Kimberley.)
Một sân bay (khác Kimberley) được gọi là *sân bay đầu mút* nếu có chuyến bay đến (và từ) đúng một sân bay khác. Giả sử có $t$ sân bay đầu mút.
Do cắt giảm ngân sách, SAMF quyết định đóng cửa $k$ sân bay. Yêu cầu là vẫn có thể đến được từng sân bay còn lại từ Kimberley.
Gọi $C$ là số cách chọn $k$ điểm đến bị ngừng khai thác. Chứng minh rằng
$$
\frac{t!}{k!(t-k)!} \le C \le \frac{(t+k-1)!}{k!(t-1)!},
$$
trong đó $n! = 1 \times 2 \times \dots \times n$ với mọi số nguyên dương $n$, và $0! = 1$.