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

Bài toán tập huấn cho đội tuyển lớp 6 của Việt Nam tham dự kỳ thi Toán học trẻ quốc tế IIMC cuối tháng 7 lấy bối cảnh từ đảo cọ ở Dubai.

Đảo cọ ở Dubai là quần đảo nhân tạo lớn nhất thế giới gồm ba hòn đảo: Palm Deira, Palm Jebel Ali và Palm Jumeirah.

Đề bài: Quần đảo Palm Jumeirah có hình cây cọ, 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?