Trò chơi Tháp Hà Nội: Lịch sử và bài toán tổng quát

Phiên âm tiếng Pháp là Tuerme Von Hanoi, hay Hanoi Towers, Tower Of Hanoi, Tháp Hà Nội (vt: ToH) là một trò chơi giải đố toán học. Đây là một game trí tuệ, điểm độc đáo đầu tiên là ở cái tên, lần đầu tiên thế giới biết đến một nước nửa thuộc địa ở Đông Nam Á qua tên thủ đô được đặt làm tựa đề cho một trò chơi (đồng thời cũng là kiểu chơi) mà sau này trở thành đối tượng độc đáo cho các nhà toán học say mê nghiên cứu.

Trò chơi được tìm thấy xuất hiện lần đầu trong sách minh họa quan thoại Trung Quốc, nhưng có thể đã xuất hiện ở Đông Á từ thế kỷ 19 hoặc trước đó _ vì theo một truyền thuyết Ấn Độ có nói đến sự di chuyển càn khôn của 64 (ứng với thuyết Kinh Dịch) đĩa vàng giữa 3 tòa tháp Brahma, Brahmin, Golcone. Khi công việc hoàn thành là thời điểm kết thúc của vũ trụ. Đây là lý do mà đa số người Tây Á gọi trò chơi kiểu này là ‘Tòa tháp Brahma’ hay Tháp Phật.




Năm 1883 nhà toán học người Pháp _ Édouard Lucas (1842 -1891) truyền bá trò chơi sang phương Tây (ToH mãi gắn liền với tên tuổi của ông do đã được đăng ký bản quyền cùng năm), ông cũng được cho là nhà bác học đầu tiên nghiên cứu toán tử ToH. Nhưng theo một giai thoại thì giữa thế kỷ XV, Lương Thế Vinh của Đại Việt đã tìm hiểu qui luật trên những chiếc đĩa – trạng lường gọi đây là ‘bài toán bất tận’ (kết luận này trùng quan điểm với điển tích ‘bài toán tự nó giải nó’). Để cho dễ nhớ Lucas chọn “Hà Nội” đặt tên cho game, với ý nghĩa công bố thuộc địa mới đô hộ của chính quyền thực dân Pháp.

Ý tưởng của trò chơi đã phác họa lên mô hình sơ khai, làm cơ sở cho tháp Bá hộ Kim ra đời 3 năm sau đó. Và như một tiền định, các kiểu tháp ở Việt Nam đến nay không đâu có kiến trúc độc đáo như tháp Rùa: tầng dưới mang phong cách kiến trúc Âu châu với ô cửa cuốn gô-tích, xong phần mái cong bên trên giữ nguyên quy thức kiến trúc Việt Nam. Ba tầng tháp chồng lên nhau mô phỏng mức đơn giản nhất của game. F.E.A. Lucas mất ở tuổi 49 trong một tai nạn hi hữu: do người bồi bàn vô tình đánh vỡ đĩa tại buổi tiệc thường niên của Viện hàn lâm toán học quốc gia, gây lên một vết sước nhỏ bên má, dẫn đến nhiễm trùng máu (septicemia).


Các phiên bản đầu tiên được Pháp sản xuất, minh họa ngoài bìa với lời giới thiệu “THÁP HÀ NỘI - Trò chơi trí tuệ của An Nam - Trò chơi được đem về từ Đông Kinh” và hướng dẫn. Đính kèm tiểu thuyết bán trong các hiệu sách ở Paris, Bắc Kinh, Tokyo và Sài Gòn. Trò chơi đến tay người chơi ban đầu chỉ qua 3 tờ giấy giới thiệu: vui và bổ ích, dễ học và dễ chơi, đồ chơi dễ làm. Cấp đơn giản nhất khởi đầu game là cho một tháp 3 tầng (đĩa với kích thước khác nhau) và 3 vị trí (cọc).

Luật chơi: di chuyển tháp đó sang cọc cuối cùng (từ vị trí 1 sang 3), theo các quy tắc: 1 lần chỉ chuyển được 1 đĩa. Chỉ đĩa lớn hơn mới chấp nhận cái nhỏ hơn xếp chồng lên. Quá trình chồng và chuyển đĩa không yêu cầu tính liền kề (vị trí khoảng cách, hay đường kính). Đánh giá hoàn hảo mỗi màn chơi căn cứ vào số lần chuyển đĩa tối ưu.

Lời giải 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 này vẫn chưa được khẳng định. Chẳng thế mà chỉ với 3 cọc chơi, nếu số tầng tháp là 64 (ngầm hiểu là màn ‘phá đảo’) thì số lần di chuyển là 18.446.744.073.709.551.615 ( >5 tỷ thế kỷ - một đáp số đánh đố cả nhân loại +_+).