Tháp Hà Nội: lời giải đệ quy, 2ⁿ − 1 nước và câu chuyện cái tên

Tháp Hà Nội là câu đố gồm ba cọc và một chồng đĩa to nhỏ khác nhau; phải chuyển cả chồng sang cọc khác, mỗi lần chỉ chuyển một đĩa, và không bao giờ đặt đĩa lớn lên trên đĩa nhỏ. Với n đĩa, số nước ít nhất là 2ⁿ − 1: 3 đĩa cần 7 nước, 8 đĩa cần 255 nước, 64 đĩa cần hơn 18 tỷ tỷ nước. Câu đố được nhà toán học Pháp Édouard Lucas giới thiệu năm 1883 với tên "Tháp Hà Nội" — cái tên gắn với thủ đô Việt Nam, dù câu đố không có nguồn gốc từ Việt Nam. Nó là ví dụ kinh điển nhất để dạy tư duy đệ quy.

Luật chơi

• Ba cọc: cọc nguồn, cọc trung gian, cọc đích.
• Ban đầu, tất cả đĩa xếp trên cọc nguồn, đĩa lớn nhất ở dưới, nhỏ dần lên trên như một ngọn tháp.
• Mỗi nước chỉ được nhấc đĩa trên cùng của một cọc và đặt sang cọc khác.
• Không bao giờ đặt đĩa lớn lên đĩa nhỏ hơn.
• Mục tiêu: chuyển cả tháp sang cọc đích.

Lucas, giáo sĩ Brahma và cái tên Hà Nội

Năm 1883, câu đố được bán ở Pháp dưới bút danh "giáo sư N. Claus de Siam" — một cách đảo chữ khéo léo: "Claus de Siam" là đảo chữ của "Lucas d'Amiens", tức Édouard Lucas, nhà toán học sinh ra ở Amiens, nổi tiếng với những nghiên cứu về dãy số và số nguyên tố. Hộp câu đố đi kèm một truyền thuyết: trong một ngôi đền lớn, các giáo sĩ không ngừng chuyển 64 chiếc đĩa vàng giữa ba cọc kim cương theo đúng luật; khi họ chuyển xong, thế giới sẽ kết thúc.

Vì sao Lucas đặt tên là Hà Nội? Không có tài liệu nào cho thấy câu đố đến từ Việt Nam. Vào thập niên 1880, Pháp đang mở rộng ảnh hưởng ở Bắc Kỳ, và những cái tên phương Đông như Hà Nội, Xiêm (Siam) mang vẻ huyền bí với công chúng Pháp. Nhiều nhà nghiên cứu cho rằng đó chỉ là cách tạo sự tò mò cho món hàng. Dù vậy, ngày nay khắp thế giới, học sinh học lập trình đều biết tên Hà Nội qua câu đố này.

Lời giải đệ quy: chỉ cần ba bước

Giả sử bạn đã biết cách chuyển một tháp n − 1 đĩa. Vậy muốn chuyển tháp n đĩa từ cọc A sang cọc C:

1. Chuyển n − 1 đĩa phía trên từ A sang B (dùng C làm trung gian).
2. Chuyển đĩa lớn nhất từ A sang C.
3. Chuyển n − 1 đĩa từ B sang C (dùng A làm trung gian).

Bước 1 và bước 3 lại là bài toán tháp Hà Nội, chỉ nhỏ hơn một đĩa. Áp dụng cùng ý tưởng cho chúng, rồi cho các bài toán nhỏ hơn nữa, cho tới tháp 1 đĩa — chỉ cần chuyển thẳng. Đây là đệ quy: giải một bài toán bằng cách quy về chính nó ở kích thước nhỏ hơn.

Điều kỳ diệu là: để giải tháp 10 đĩa, bạn không cần hình dung cả 1.023 nước đi. Chỉ cần tin rằng tháp 9 đĩa giải được, mọi thứ tự lo.

Vì sao cần đúng 2ⁿ − 1 nước

Gọi T(n) là số nước ít nhất để chuyển tháp n đĩa. Theo lời giải đệ quy: T(n) = 2·T(n − 1) + 1, với T(1) = 1.

Không thể làm ít hơn: đĩa lớn nhất phải di chuyển ít nhất một lần; lúc nó di chuyển, mọi đĩa khác phải nằm gọn trên cọc thứ ba; tức là trước đó phải đã chuyển xong n − 1 đĩa, và sau đó phải chuyển chúng thêm một lần nữa. Lập luận này chứng minh 2ⁿ − 1 là tối thiểu.

Với 64 đĩa, kể cả với tốc độ một nước mỗi giây không ngừng nghỉ, các giáo sĩ trong truyền thuyết cần khoảng 585 tỷ năm — gấp hơn 40 lần tuổi hiện tại của vũ trụ (khoảng 13,8 tỷ năm). Thế giới khá an toàn.

Đây cũng là bài học về tăng trưởng theo hàm mũ: thêm một đĩa là gấp đôi công việc. Cùng kiểu tăng trưởng như câu chuyện hạt thóc trên bàn cờ.

Mẹo giải không cần nghĩ đệ quy

Có một quy tắc đơn giản để giải bằng tay mà không cần nhớ "đang ở tầng đệ quy nào":

1. Xếp ba cọc thành vòng tròn trong đầu.
2. Ở các nước lẻ (1, 3, 5...), luôn chuyển đĩa nhỏ nhất sang cọc kế tiếp theo một chiều cố định (với số đĩa chẵn, đi theo chiều A → B → C → A; với số đĩa lẻ, đi theo chiều A → C → B → A).
3. Ở các nước chẵn, thực hiện nước đi hợp lệ duy nhất không dùng đĩa nhỏ nhất.

Quy tắc này luôn cho lời giải ngắn nhất. Một điều thú vị: số thứ tự của đĩa được chuyển ở mỗi nước theo đúng một quy luật liên quan tới hệ nhị phân — đĩa nhỏ nhất di chuyển ở mọi nước lẻ, đĩa thứ hai ở nước 2, 6, 10..., giống cách bit thấp nhất đổi trong phép đếm nhị phân. Tháp Hà Nội gắn với mã Gray, một cách đếm nhị phân mà mỗi bước chỉ đổi một chữ số.

Tháp Hà Nội trong học tập và tâm lý học

• Lập trình: gần như mọi giáo trình nhập môn lập trình đều dùng tháp Hà Nội để giới thiệu đệ quy; lời giải chỉ vài dòng mã.
• Toán học: dùng để dạy quy nạp toán học, hệ thức truy hồi, hàm mũ.
• Tâm lý học thần kinh: các phiên bản tương tự (như bài kiểm tra Tháp London) được dùng trong nghiên cứu khả năng lập kế hoạch của não. Đây là công cụ nghiên cứu của chuyên gia, không phải bài kiểm tra trí thông minh để tự đánh giá.

Góc nhìn hôm nay: làm tháp Hà Nội ở nhà

1. Dùng 3–5 đồng xu khác cỡ, hoặc cắt những tấm bìa tròn to nhỏ dần, hoặc chồng các nắp lọ.
2. Vẽ ba vòng tròn trên giấy làm ba cọc.
3. Bắt đầu với 3 đĩa, đếm số nước. Thử đạt đúng 7.
4. Tăng lên 4 đĩa (15 nước), 5 đĩa (31 nước). Để ý cách giải 4 đĩa chứa bên trong hai lần cách giải 3 đĩa.
5. Hỏi trẻ: "Nếu có 6 đĩa thì cần bao nhiêu nước?" và xem trẻ có tự tìm ra quy luật gấp đôi cộng một không.