Để 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.

PH/HS 2K10 THAM GIA NHÓM ĐỂ CẬP NHẬT ĐIỂM THI, ĐIỂM CHUẨN MIỄN PHÍ!

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 Đầy đủ khoá học các bộ sách: Kết nối tri thức với cuộc sống; Chân trời sáng tạo; Cánh diều. 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/HS tham khảo chi tiết khoá học tại: Link