Để tiết kiệm chi phí vận hành đồng thời du khách đi tham quan hết 18 danh lam, thắng cảnh trong

Câu hỏi số 272787:

Vận dụng cao

Để tiết kiệm chi phí vận hành đồng thời du khách đi tham quan hết 18 danh lam, thắng cảnh trong tỉnh K, công ty du lịch lữ hành KH đã thiết lập các tuyến một chiều như sau: Nếu đi từ A đến B và từ B đến C thì sẽ không có tuyến từ A đến C. Hỏi có bao nhiêu cách thiết lập để đi hết 18 địa danh trên?

Quảng cáo

Xem lời giải

Câu hỏi:272787

Giải chi tiết

Gọi A là địa điểm có nhiều tuyến đường nhất (gồm cả đường xuất phát từ A và đi đến A). Các địa điểm còn lại ta chia thành 3 loại:

Loại 1: Các đường xuất phát từ A có \(n\left( 1 \right) = m\) tuyến đường.

Loại 2: Các tuyến đi đến A có \(n\left( 2 \right) = n\) tuyến.

Loại 3: Không có tuyến đi và đến A có \(n\left( 3 \right) = p\) tuyến.

Do \(m + n + p = 17\) và:

Số tuyến liên quan đến A có \(m + n\) tuyến.

Số tuyến không liên quan đến A không vượt quá \(m + n\).

Số tuyến không liên quan đến loại 1 và 2 không vượt quá \(m + n\).

Gọi S là số cách thiết lập đi hết 18 địa danh thì:

\(S = m + n + p\left( {m + n} \right) + mn = mn + \left( {p + 1} \right)m + n\left( {p + 1} \right) \le \frac{{{{\left( {m + n + p + 1} \right)}^2}}}{3} = 108\) (Áp dụng bất đẳng thức Cô Si).

Dấu bằng xảy ra khi và chỉ khi \(m = p = 6;\,\,n = 5\).

Vậy có tối đa 108 cách thiết lập đi hết 18 địa danh trên.

Tham Gia Group Dành Cho Học Sinh Lớp 9 - Ôn Thi Vào Lớp 10

Câu hỏi trước Câu tiếp theo

>> Học trực tuyến lớp 9 và Lộ trình UP10 trên Tuyensinh247.com . Học online tại nhà cũng giáo viên giỏi từ trường TOP đầu cả nước. Lộ trình học tập 3 giai đoạn: Học nền tảng lớp 9, Ôn thi vào lớp 10, Luyện Đề. Bứt phá điểm lớp 9, thi vào lớp 10 kết quả cao. Hoàn trả học phí nếu học không hiệu quả. Phụ huynh và học sinh tham khảo chi tiết khoá học tại: Link