Bài toán “Tháp Hà Nội” một bài toán đố hóc búa hơn một trăm năm nay

“ Có nơi nào trên trái đất này/ Mật độ nhà thư như ở đây/ Sáu mét vuông có chín nhà thơ ngồi/ Ba phải đứng vì không đủ chỗ”…

Chính vì vậy, cái gì người ta cũng có thể mang ra làm đề tài cho thơ được. Từ công việc đồng áng của nông dân tới việc trọng đại của quốc gia, từ con giun, con kiến cho tới những anh hùng đã làm vẻ vang cho lịch sử dân tộc đều được xưng tụng bằng thơ. Có lần nhà thơ Phùng Quán hỏi tôi “Toán của các ông là cái gì mà mình chẳng hiểu. Tôi muốn xưng tụng nó nhưng thấy rất khó”. Bí quá tôi trả lời: “Toán là thơ của khoa học tự nhiên!”. Nghe vậy anh nói luôn: “Thế thì thơ cũng là toán của khoa học xã hội!”. Có lẽ như vậy nên tôi chẳng ngạc nhiên khi thấy những bài toán đố trong dân gian VIệt Nam phần lớn đều được viết dưới dạng văn vần.

Ví dụ: “ Vừa gà vừa chó/ Bó lại cho tròn/ Ba mươi sáu con/ Một trăm chân chẵn/ Hỏi có bao nhiêu gà, bao nhiêu chó?”

Hay: “Trăm trâu trăm cỏ/ Trâu đứng ăn năm/ Trâu nằm ăn ba/ Lụ khụ trâu già/ Ba con một bó/ Hỏi có bao nhiêu trâu dứng, trâu nằm, trâu già”.

Cái hay của những bài toán đố đó làm mang tính văn nghệ (có lẽ cốt để làm giảm bớt sự khô khan của toán học). Nhưng cái hạn chế là khả năng khái quát hầu như không có, khả năng giao dịch với nước ngoài khó. Ví dụ ở bài toán trên nếu ta thay gà, chó, trâu bằng những con vật khác hay dịch các bài này ra tiếng nước khác thì thơ chẳng còn là thơ. Người đọc, người nghe cũng không còn hứng thú để giải toán nữa.

Hà Nội xưa nay nổi tiếng là thủ đô của một nước mấy nghìn năm văn vật. Trong giới toán học thế giới, Hà Nội nổi tiếng còn vì có Viện Toán học vào loại tầm cỡ quốc tế. Nhưng nhiều người Việt Nam ta còn chưa hiểu biết tới Hà Nội là cái nôi của một bài toán đố hóc búa. Bài toán này đã được những người làm toán trên thế giới biết đến hơn một trăm năm nay và đã trở thành cơ sở cho nhiều lý thuyết quan trọng trong toán học ứng dụng, đặc biệt trong kinh tế như: Lý thuyết tối ưu tổ hợp, Toán học rời rạc, Thuật toán… Không ai có thể biết rõ bài toán này có ở Hà Nội tự bao giờ, ngày tháng năm nào. Ta chỉ biết chắc chắn rằng nó được nhiều người quan tâm nghiên cứu và viết hàng trăm công trình khoa học, hàng chục quyển sách về nó. Người ta đã đặt cho nó cái tên duyên dáng, đáng yêu: Bài toán “Tháp Hà Nội”. Nhiều khi viết tắt bài toán TH (The towerof Hanoi). Người ta cũng đã kêu ca nhiều về nó, cho nó là hóc búa, bất kham, vì nó đã từng làm cho bao người thông thái đau đầu, mất ăn, mất ngủ.

Trong bài viết ở tạp chí toán học: Proceeding of the Edinburgh Mathematical Society, 2 (1883 – 1884), R. E Allardiece và A. Y. Fras đã kể rằng bài toán “Tháp Hà Nội”, một bài toán đố hóc búa ở xứ Annam đã được Giáo sư N. Claus (de Siam), một quan chức của trường đại học Li - Sou - Stian, mang về Pháp (thực ra ông này tên là N. Lucas thuộc trường đại học Saint, Louis, ông ta đảo vị trí các chữ cho có vẻ là một người lạ, từ một xứ lạ). Người ta đã lấy nó để đố nhau và phát hiện ra nó rất quỷ quái. Nội dung của nó sơ lược như thế này. Trong một ngôi đền thiêng liêng có ba chiếc cọc bằng kim cương, được chôn chặt, thẳng đứng. Ông trời đã xếp 64 chiếc đĩa vàng có các đường kính khác nhau và có lỗ ở giữa vào một chiếc cọc theo thứ tự to trước nhỏ sau (vì vậy mới có tên là tháp). Bài toán đặt ra là làm thế nào chuyển từng chiếc một toàn bộ 64 cái đĩa đó sang chiếc cọc thứ ba thông qua chiếc cọc thứ hai với điều kiện: Trong quá tình chuyển ở cả ba cọc, các đĩa to không bao giờ được nằm trên các đĩa nhỏ hơn chúng.

Bài toán tổng quát: cho trước ba chiếc cọc chôn thẳng đứng. Trên một cọc đã xếp n (n = 1, 2…) đĩa có đường kính khác nhau xuyên qua lỗ thủng ở giữa. Đĩa to nằm dưới, đĩa nhỏ hơn nằm trên. Vấn đề đặt ra là làm thế nào để chuyển từng chiếc một toàn bộ số đĩa đó sang chiếc cọc thứ ba thông qua chiếc cọc thứ hai với yêu cầu trong quá trình chuyển, ở cả ba cọc luôn có trật tự đĩa to nằm dưới đĩa bé nằm trên.

Để giải bài toán này người ta gọi một trạng thái là sự phân bố bất kỳ đĩa ở ba cọc ví dụ: hình 1 dưới đây là một trạng thái.

Một trạng thái gọi là chính qui nếu trong mỗi cọc các đĩa to nằm dưới đĩa nhỏ hơn. Ví dụ hình 2 dưới đây là một trạng thái chính qui.

Một trạng thái được gọi là hoàn hảo nếu nó là chính qui và tất cả các đĩa đều nằm trong cùng một cọc. Ví dụ hình 3 dưới đây là một trạng thái hoàn hảo.

Khi ta chuyển một chiếc đĩa từ cọc này sang cọc khác thì được gọi là một chuyển động.

Cho hai trạng thái A và B bất kỳ. Mọi dãy các chuyển động từ trạng thái A sang trạng thái B được gọi là một đường từ A tới B. Số các chuyển động của dãy này được gọi là độ dài của đường từ A tới B.

Người ta chứng minh một cách dễ dàng rằng: Cho trước hai trạng thái chính quy A và B bất kỳ. Khi ấy sẽ tồn tại con đường ngắn nhất từ A tới B có độ dài nhỏ hơn hoặc bằng 2 ⁿ– 1, trong đó n là số đĩa.

Bài toán “Tháp Hà Nội” thực chất là tìm con đường ngắn nhất để chuyển từng cái một toàn bộ 64 đĩa từ trạng thái hoàn hảo này sang trạng thái hoàn hảo khác.

Năm 1883, Giáo sư Lucas cũng đã chỉ ra rằng để chuyển từng cái một toàn bộ 64 cái đĩa vàng ấy từ cọc thứ nhất sang cọc thứ ba thông qua cọc thứ hai theo con đường ngắn nhất ta cần tới 2 ⁶⁴– 1 chuyển động. Như vậy, nếu mỗi chuyển động ta thực hiện trong một giây đồng hồ thì toàn bộ thời gian để chuyển sang cọc thứ ba theo yêu cầu của bài toán là 18.446.744.073.709.551.615 giây. Tức là, ta phải làm trong 5 tỉ thế kỷ mới song. Tuy nhiên về mặt lý thuyết bài toán “Tháp Hà Nội” nguyên thuỷ đã được giải quyết.

Giáo sư Lucas đã chỉ ra rằng bài toán “Tháp Hà Nội” là một dạng tổng quát của bài toán đố “vòng tròn của Trung Quốc” về các hệ thống số khác nhau. Bài toán “Tháp Hà Nội” tổng quát tìm con đường ngắn nhất từ trạng thái hoàn hảo này sang trạng thái hoàn hảo khác với số cọc nhiều hơn ba cũng đã được giáo sư Dudeney xét tới vào năm 1889. Trong trường hợp này, người ta mới đưa ra được thuật toán để tìm con đường ấy nhưng chưa chứng minh được nó là ngắn nhất. Vấn đề này vẫn còn tồn tại cho tới ngày nay.

Bài toán “Tháp Hà Nội” thực là một bài toán hóc búa. Từ nó đã nảy sinh nhiều vấn đề lý thú và có ứng dụng trong nhiều lĩnh vực khác nhau của toán học. Còn rất nhiều vấn đề quan trọng nó chưa được giải quyết đang hấp dẫn các nhà toán học trên thế giới. Mong các bạn trẻ yêu toán nước ta đến với chúng, nghiên cứu chúng để tăng cường vẻ vang cho Tổ quốc.