Về Tháp Hà Nội | Luật chơi, 2ⁿ−1 và truyền thuyết

Ba cọc và một chồng đĩa hình nón

Bàn chơi có ba cọc. Các đĩa đều có kích cỡ khác nhau và được xỏ vào cọc. Lúc đầu cả bộ đĩa nằm trên một cọc, xếp theo kích cỡ, đĩa lớn nhất ở dưới và nhỏ nhất ở trên, nên chồng đĩa có hình nón. Mục tiêu là chuyển cả tháp đó sang một cọc khác.

Đồ chơi gỗ Tháp Hà Nội với đĩa xếp trên ba cột — Đồ chơi gỗ Tháp Hà Nội. Ảnh: PranavAmbhore, CC BY-SA 3.0

Ba luật chơi

1. Mỗi lần chỉ chuyển một đĩa. 2. Một nước đi lấy đĩa trên cùng của một chồng và đặt lên chồng khác, hoặc lên một cọc trống. 3. Đĩa lớn hơn không bao giờ được nằm trên đĩa nhỏ hơn. Ba luật đó là toàn bộ trò chơi. Với chúng, mỗi thế hợp lệ là một cách chia các đĩa lên các cọc sao cho mỗi cọc vẫn được xếp theo thứ tự.

Lời giải ngắn nhất là 2ⁿ − 1

Số nước ít nhất để giải một tháp n đĩa là 2ⁿ − 1. Một đĩa cần 1 nước. Hai đĩa cần 3. Ba đĩa cần 7, bốn cần 15 và năm cần 31. Mỗi đĩa mới nhân đôi lời giải trước và thêm một nước để chuyển đĩa lớn nhất: nếu n − 1 đĩa cần T nước thì n đĩa cần 2T + 1. Hệ thức truy hồi đó đúng bằng 2ⁿ − 1. Tám đĩa, tháp cao nhất trong ứng dụng PictorX, cần 255 nước. Không có đường đi hợp lệ nào ngắn hơn.

Phép đệ quy hoạt động thế nào

Để chuyển n đĩa từ cọc xuất phát sang cọc đích, dùng cọc còn lại làm cọc trung gian: 1. Chuyển n − 1 đĩa trên cùng từ cọc xuất phát sang cọc trung gian. 2. Chuyển đĩa lớn nhất từ cọc xuất phát thẳng sang cọc đích. 3. Chuyển n − 1 đĩa từ cọc trung gian sang cọc đích, đặt lên trên đĩa lớn nhất. Bước 2 hợp lệ vì đĩa lớn nhất được đặt trên bất kỳ cọc nào. Bước 1 và 3 là cùng một câu đố, bớt một đĩa. Lời gọi dừng lại ở một đĩa duy nhất, đĩa đó được chuyển một lần. Khai triển ra sẽ được 2ⁿ − 1 nước, và không bước nào đặt đĩa lớn lên đĩa nhỏ.

Tháp Hà Nội khổng lồ ngoài trời tại Domaine de Chanteloup — Tháp Hà Nội khổng lồ tại Domaine de Chanteloup. Ảnh: Als33120, CC BY-SA 4.0

Truyền thuyết về 64 đĩa vàng

Nhà toán học người Pháp Édouard Lucas giới thiệu câu đố này vào năm 1883. Kèm theo đó, ông kể một truyền thuyết về một ngôi đền Ấn Độ ở Kashi Vishwanath, nơi các thầy tu chuyển một chồng 64 đĩa vàng theo đúng những luật này. Truyền thuyết nói rằng khi nước đi cuối cùng hoàn tất, thế giới sẽ tận diệt. Sáu mươi tư đĩa cần 2⁶⁴ − 1 nước: 18.446.744.073.709.551.615. Với mỗi giây một nước hoàn hảo, ngày đêm không nghỉ, sẽ mất khoảng 585 tỷ năm. Các thầy tu sẽ không làm xong.

Chân dung nhà toán học Édouard Lucas — Édouard Lucas (1842-1891), người giới thiệu trò chơi năm 1883. Phạm vi công cộng

Chơi trong PictorX

Mở Tháp Hà Nội và một tháp bốn đĩa đã nằm sẵn trên cọc xuất phát. Tối thiểu là mười lăm nước. Kéo đĩa trên cùng sang cọc khác, hoặc bấm một cọc rồi bấm cọc bạn muốn. Các phím 1, 2 và 3 cũng làm như vậy. Đặt đĩa lớn lên đĩa nhỏ sẽ bị từ chối. Đĩa chạy từ 1 đến 8, nên bạn có thể đối chiếu 1, 3, 7, 15, 31, 63, 127 và 255 với công thức. Bước phát một nước của một lời giải ngắn nhất. Giải phát phần còn lại. Xem 3 đĩa cho thấy chiến lược đệ quy đang chuyển động. Hoàn tác và Làm lại đi qua các nước của bạn. Lưu PNG, hoặc mở bàn chơi trong trình chỉnh sửa PictorX.

Hỏi thường xuyên

Luật chơi Tháp Hà Nội là gì?

Mỗi lần chuyển một đĩa. Lấy đĩa trên cùng của một cọc và đặt lên cọc khác. Không bao giờ đặt đĩa lớn lên đĩa nhỏ. Cả tháp bắt đầu ở một cọc và phải kết thúc ở cọc khác.

Lời giải ngắn nhất cần bao nhiêu nước?

2ⁿ − 1. Một đĩa là 1 nước, hai đĩa là 3, ba đĩa là 7, bốn đĩa là 15 và năm đĩa là 31. Mỗi đĩa thêm vào nhân đôi lời giải trước và cộng thêm một nước.

Ai đã phát minh ra Tháp Hà Nội?

Nhà toán học người Pháp Édouard Lucas giới thiệu nó vào năm 1883. Câu chuyện về các thầy tu và 64 đĩa vàng ở Kashi Vishwanath là truyền thuyết ông gắn với câu đố.

64 đĩa sẽ mất bao lâu?

2⁶⁴ − 1 nước, tức là 18.446.744.073.709.551.615. Với mỗi giây một nước, sẽ mất khoảng 585 tỷ năm.