Tháp Hà Nội là một trò chơi và cũng là một bài toán logic khá nổi tiếng. Hầu như ai học toán và học lập trình cũng biết tới trò chơi này. Tuy vậy, không chỉ có dân toán và dân lập trình mà ngay cả những đứa trẻ khắp nơi trên thế giới cũng biết tới trò chơi này bởi luật để chơi rất đơn giản :
- Khởi đầu có 3 cọc, trong đó có 2 cọc rỗng và một cọc chứa một số lượng nhất định các đĩa khác nhau xếp theo thứ tự bé ở trên, to ở dưới
- Mỗi lần đĩa từ cọc này sang cọc khác chỉ được di chuyển 1 đĩa
- Khi di chuyển phải di chuyển đĩa ở trên cùng
- Không được phép đặt đĩa to hơn lên trên đĩa bé hơn
- Trò chơi kết thúc khi toàn bộ đĩa từ cọc ban đầu được chuyển sang một cọc khác (và theo đúng thứ tự bé ở trên, to ở dưới)
Trò chơi này được một nhà toán học người Pháp có tên Edouard Lucas phát minh ra vào năm 1883. Tương truyền, có một ngôi đền của người Hindu có 3 cọc bằng vàng, trong đó có một chiếc cọc có 64 chiếc đĩa vàng. Nhiệm vụ của các nhà sư ở đó cũng giống hệt như luật của trò chơi vừa kể trên, chuyển 64 đĩa từ cọc này sang cọc khác, mỗi lần một đĩa mà không được phá vỡ quy luật trên bé dưới to. Khi chuyển xong 64 đĩa thì ngôi đền sẽ bị nổ tung và Trái Đất sẽ biến mất. Không rõ truyền thuyết này đúng tới đâu nhưng theo ước tính của các nhà toán học thì các nhà sư cần 18.446.744.073.709.551.615 lần di chuyển mới có thể hoàn thành. Nếu họ làm cả ngày lẫn đêm, mỗi lần chuyển đĩa mất 1 giây thì phải mất tới 580 tỷ năm mới có thể hoàn thành công việc này. Cũng không rõ tại sao trò chơi của nhà toán học người Pháp lại được đặt tên là “Tháp Hà Nội” vì ở Việt Nam không có ngôi đền này.
Nếu rảnh, bạn có thể tự chơi trò chơi này hoặc lập trình để giải bài toán “Tháp Hà Nội” với số lượng đĩa khác nhau. Dưới đây là lời giải của
Wikipedia với 4 đĩa. Không dễ đâu bạn nhé!
Không có nhận xét nào:
Đăng nhận xét