Bài toán tháp Hà Nội (Tower of Hanoi) xuất hiện ở Đông Á từ thế kỷ 19, là trò chơi toán học dịch chuyển và sắp xếp các đĩa kích cỡ khác nhau từ một cột sang một cột trung gian để tạo ra trật tự đĩa xếp từ lớn đến bé trong cột còn lại.
Nhà toán học người Pháp Edouard Lucas đã đặt tên Tower of Hanoi vào năm 1883, đưa nó lan tỏa khắp châu Âu và thế giới. Thậm chí người ta trao thưởng một triệu franc cho ai hoàn thành việc dịch chuyển 64 đĩa bằng tay theo quy tắc của trò chơi. Điều này là không thể bởi nếu mỗi giây dịch chuyển được một đĩa phải mất đến 18 446 744 073 709 551 615 giây tức là hơn 3 tỷ năm.
Tại lễ khai mạc kỳ thi Toán Hà nội mở rộng lần thứ 15 (HOMC 2018) vào ngày 27/3 vừa qua, Trưởng đoàn Đội tuyển Toán Ba Lan Lukasz Bozyk đã ca ngợi vẻ đẹp của bài toán tháp Hà Nội. Từ bài toán, ông đã biết đến Hà Nội và Việt Nam.
Cũng tại kỳ thi HOMC 2018 với sự tham dự của hơn 500 thí sinh từ 9 quốc gia, một bài toán tổ hợp về tháp Rùa Hà Nội được Ban tổ chức "đặt hàng" thầy giáo Trần Phương, Phó giám đốc Trung tâm hỗ trợ phát triển tài năng, cho phần thi đồng đội Bảng A quốc tế. Sau đây là nội dung đề bài cho khối Junior (lớp 8).
Đề bài:
Hình trên mô phỏng tháp Rùa Hà Nội gồm 3 phần. Tầng 1 và 2 mỗi tầng có 10 ô cửa gồm 3 ô cửa mặt trước, 3 ô cửa mặt sau, 2 ô cửa bên trái và 2 ô cửa bên phải, tầng 3 là nóc tháp. Mặt trước tháp là mặt có biểu tượng hình tròn trên nóc tháp. Sử dụng 3 màu sơn xanh, vàng và nâu để trang trí tháp rùa theo các yêu cầu sau đây:
i) Nóc tháp được sơn bằng một màu
ii) Ba ô cửa mặt trước của tầng hai được sơn cùng một màu
iii) Ba ô cửa mặt trước của tầng một được sơn cùng một màu
iv) 14 ô cửa không ở mặt trước của tầng 1 và tầng 2 được sơn bằng 1 trong 3 màu sao cho trong mỗi tầng các ô cửa kề nhau (chung cạnh với nhau) phải sơn khác màu nhau.
1. Hỏi có bao nhiêu cách sơn trang trang trí theo yêu cầu cho tầng 1?
2. Hỏi có bao nhiêu cách sơn trang trang trí khác nhau cho tháp Rùa Hà Nội?