Đáp án bài toán du lịch trên đảo cọ ở Dubai

95


Trong 25 bạn đọc giải bài toán, chỉ một bạn có phương pháp tính đúng nhưng khi thực hiện phép nhân chứa thừa số 72 và 3 lại cho ra số có chữ số tận cùng là 0.

Đề bài:

Hình dưới là toàn cảnh quần đảo Palm Jumeirah có hình cây cọ mà từ trục đường chính giữa (thân cây) có 8 nhánh bên trái, 8 nhánh bên phải (đối xứng nhau) và một nhánh ở trên cùng (ngọn cây) thẳng hàng với thân cây. Giả định mỗi nhánh đều có 3 đường đi (2 đường ven biển và một đường nằm ở giữa mỗi nhánh) và 2 nhánh đối xứng thông nhau qua đoạn ngang trên trục chính.

Hỏi có bao nhiêu cách để một ôtô đi từ “gốc cây” (điểm O trên trục chính trước khi phân nhánh) đến “ngọn cây” (điểm Z trên trục chính xa gốc cây nhất) với yêu cầu phải đi qua hết tất cả nhánh cây theo thứ tự lần lượt từ nhánh ở sát “gốc cây” nhất tiến dần đến “ngọn cây”, nhưng không có lộ trình nào có đường đi trong các nhánh hoặc trục chính bị lặp lại?

Đảo cọ ở Dubai. Ảnh: Pinterest

Đảo cọ ở Dubai. Ảnh: Pinterest

Đáp án:

Ta gọi nút là giao của trục chính với các cặp nhánh trái và phải đối xứng nhau. Từ hình vẽ suy ra trên “cây cọ” có 8 nút và tại mỗi nút có 2 cách chọn đi trước ở nhánh bên phải hoặc nhánh bên trái.

Với mỗi nhánh ở mỗi nút ta đều có 3 cách chọn đường đi vào và 2 cách chọn đường đi ra nên có 3×2=6(cách) đi vào và đi ra mỗi nhánh.

Như thế tại mỗi nút trong 8 nút đều có: 2x6x6=72 cách đi (1).

Mặt khác từ nút thứ 8 đến “ngọn cây” Z ta có 3 cách đi (2) Từ (1) và (2) suy ra số cách để một ôtô đi từ “gốc cây” O đến “ngọn cây” Z mà không có một đoạn nào bị lặp lai là:

72x72x72x72x72x72x72x72x3= 2,166,612,408,926,208 (cách đi)

Trần Phương