Bài toán Tháp Hà Nội- phần 1

Lịch sử

Trò chơi Tháp Hà Nội có thể đã xuất hiện ở Đông Á từ thế kỷ 19 hoặc trước đó. Các đĩa được làm bằng sứ ở Trung Quốc, Nhật Bản và Việt Nam.

Trò chơi này được đưa sang phương Tây lần đầu bởi nhà toán học người Pháp Edouard Lucas vào năm 1883.

Trò chơi này nhanh chóng được các nhà toán học nghiên cứu sau đó, và trở thành ví dụ về phương pháp giải đệ quy kinh điển trong dạy học và tin học. Lời giải tối ưu cho trò chơi có thể tìm thấy chính xác cho trường hợp 3 cọc. Nhưng khi mở rộng cho 4 cọc hoặc nhiều hơn, lời giải chính xác cho đến nay vẫn chưa được khẳng định.

Luật chơi

Dạng thường gặp nhất của trò chơi này gồm một bộ các đĩa kích thước khác nhau, có lỗ ở giữa, nằm xuyên trên ba cái cọc. Bài toán đố bắt đầu bằng cách sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Yêu cầu của trò chơi là di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:

• Chỉ có 3 cột để di chuyển.
• Một lần chỉ được di chuyển một đĩa (không được di chuyển đĩa nằm giữa).
• Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất).