Ngay từ khi họ phổ thông, chắc rằng chúng ta đều đã nghe  qua những định lý hay những bài toán có thể gọi là "huyền thoại" mang tên của người phát triển nó. Nhưng có lẽ có ai đó sẽ đặt câu hỏi, vì sao có những định lý Viète, thuật toán Euclid nhưng chưa bao giờ nghe đến một cái tên Việt nào? Đây là một câu hỏi rất hay, khiến những người bi quan có thể liên tưởng đến những điều tiêu cực. Tất nhiên, một điều chắc chắn rằng nền khoa học kĩ thuật Việt Nam chưa thể so sánh được  với các nước phương Tây. Nhưng, không phải không có những con người vĩ đại.

Trong chuỗi bài viết này, chúng tôi muốn tổng hợp và giới thiệu đến qúy độc giả những định lý, thuật toán mang tên Việt. Vài trong số chúng do chính người Việt Nam phát triển, số khác gắn với lịch sử và địa danh của Việt Nam. Mở đầu cho chuỗi bài viết, ta cùng tìm hiểu về bài toán tháp Hà Nội (tower of Hanoi).

Truyền thuyết kể lại rằng có  một ngôi chùa thiêng tại Hà Nội, bên trong là một gian phòng được trồng ba cột trụ. Một trong số chúng được xếp 64 vòng vàng có kích thước từ lớn đến nhỏ chồng lên nhau. Một vị sư trong chùa mỗi  ngày sẽ di chuyển một lần một chiếc vòng  sang cột khác sao cho chiếc vòng đó hiện không có chiếc nào khác ở trên và  không được di chuyển nó đè lên chiếc vòng kích thước nhỏ hơn. Vị sư đang làm theo một lời tiên tri cổ: "khi tất cả các vòng vàng được di chuyển hết từ cột ban đầu sang một cột khác với thứ thứ tự được sắp vẫn vậy, lúc đó thế giới sẽ kết thúc".

Nếu truyền thuyết thành sự thật, liệu con người còn sống được bao nhiêu ngày? Vào năm 1883, nhà toán học người Pháp Édouard Lucas đã đặt ra câu hỏi này và ngày nay nó đã trở thành một bài toán tiêu biểu mà rất nhiều nhà khoa học khác nghiên cứu đưa ra cách giải quyết. Không rõ rằng cảm hứng nào đã khiến ông Lucas nghĩ ra bài toán trên, có thực sự tồn tại ngôi chùa thiêng trong truyền thuyết. Và cũng có rất nhiều dị bản của câu chuyện với địa danh và tôn giáo khác. Một trong số chúng là ngôi đền ở Kashi Vishwanath (Ấn Độ) hay thậm chí có dị bản nói rằng bài toán này xuất phát từ Trung Quốc. Do đó nó có nhiều tên gọi, chẳng hạn như Tower of Brahma.

Lời tiên tri có vẻ khiến chúng ta băn khoăn, nhưng thực sự chúng ta còn sống khá lâu nữa ! (nếu điều đó thành sự thật). Số lần di chuyển nhỏ nhất để đưa toàn bộ các vòng sang cột khác đúng luật là \((2^{64} - 1)\) . Như vậy nếu mỗi ngày di chuyển 1 lần, sẽ cần phải mất hơn \(5\times10^{16}\) năm để thực hiện xong, gấp khoảng 127 lần độ tuổi hiện tại của mặt trời! Đó là khi mọi bước di chuyển đều theo thứ tự chính xác nhất.

Vậy cách di chuyển thế nào là chính xác nhất? Để trả lời câu hỏi này, có hai phương pháp cơ bản nhất: phương pháp đệ quy và phương pháp lặp. Để đơn giản, ta xét bài toán với trường hợp có 5 vòng, hay \(n = 5\) và đánh số các vòng từ \((1)\) đến \((5)\) theo thứ tự vòng lớn hơn có số lớn hơn. TowersOfHanoiFigureVới phương pháp đệ quy, mọi tư duy như vô cùng tự nhiên: nếu tôi muốn di chuyển 5 vòng từ cột A sang C, tôi sẽ bưng cả chồng vòng từ \((1)\) đến \((4)\) sang B và rồi đưa vòng \((5)\) to nhất sang C, sau đó đưa cả chồng vòng ở B đặt qua C. Giai đoạn "bưng cả chồng vòng" từ \((1)\) đến \((4)\) chính là ta đang giải bài toán tháp Hà Nội một lần nữa, nhưng với số lượng đĩa \(n-1=4\) . Như vậy, ta phải thực hiện 2 lần di chuyển chồng \(n-1\) vòng và một lần di chuyển vòng thứ \((n)\) . Gọi \(T_{n}\) là thời gian để giải bài toán với \(n \) vòng, ta có

\(T_{n} = 2T_{n-1}+1\) .

Khi giải phương trình đệ quy này, ta biết được vì sao kết quả của bài toán là \(2^{n}-1\) .

Với phương pháp sử dụng vòng lặp, điều ta cần làm là đặt ra các luật để ràng buộc sao cho ở mỗi bước, theo luật đó ta chỉ có chính xác một cách di chuyển được. Ngoài các luật của bài toán, ta cần thêm vào điều kiện:

  • Trong trạng thái khởi đầu, nếu \(n\) lẻ di chuyển vòng \((1)\) từ A sang C, ngược lại di chuyển sang B.
  • Không được đặt vòng số lẻ trực tiếp lên vòng lẻ.
  • Không được đặt vòng số chẵn trực tiếp lên vòng chẵn.

Bằng cách này, mỗi bước chỉ có duy nhất 1 vòng có thể được di chuyển đúng luật. Do đó ta có thể tìm ra thứ tự di chuyển đúng.

Ngoài ra, còn rất nhiều cách có thể dùng để giải bài toán này, được phát triển nbởi nhiều nhà toán học và khoa học máy tính. Việc cài đặt thuật toán này xin dành lại cho độc giả.

Tham khảo: On the Solution of the Tower of Hanoi problem, Hayedeh Ahrabian,Comfar Badamchi, và Abbass Nowzari-Dalini, World Academy of Science, Engineering and Technology.