THÁP HÀ NỘI
TRÒ CHƠI TRÍ TUỆ CỦA AN NAM
TRÒ CHƠI ĐƯỢC ĐEM VỀ TỪ BẮC KÌ
BỞI GIÁO SƯ N. CLAUS (CỦA SIAM)
TRƯỜNG CAO ĐẲNG QUAN LI-SOU-STIAN!

Trò chơi này được tìm thấy, lần đầu, trong cuốn sách được minh họa Quan thoại FER-FER-TAM-TAM, đang được xuất bản, trong tương lai gần, bởi chính phủ Trung Hoa. Tháp Hà Nội có các đĩa, nhỏ dần, có số lượng thay đổi, mà chúng tôi làm bằng gỗ, có lỗ ở giữa. Ở Nhật Bản, Trung Quốc, và ở Bắc Kì, chúng được làm bằng sứ.
Trò chơi có mục đích là dỡ bỏ các đĩa, và đặt vào cột bên cạnh, theo các quy tắc nhất định.

Vui và bổ ích, dễ học và dễ chơi trong thành phố, ngoài nông thôn, trên chuyến du lịch, nó được tạo ra để mang đến kiến thức khoa học, giống mọi trò chơi kỳ thú và mới lạ của giáo sư N. CLAUS (của SIAM).

Chúng tôi trao giải thưởng 1000 franc, 100 nghìn franc, một triệu franc, và nhiều hơn, cho ai hoàn thành, bằng việc dùng tay di chuyển tháp Hà Nội với 64 đĩa, theo quy tắc của trò chơi. Chúng tôi nói ngay là cần số lần di chuyển là:
18 446 744 073 709 551 615,
nhiều hơn năm tỷ thế kỷ!

Theo một truyền thuyết Ấn Độ, những người Brahmin đã tiếp nối nhau trong một thời gian dài để thay đổi Đền Bernares, di chuyển 64 đĩa vàng của Tòa tháp Brahma, trạm kim cương từ Golconde. Khi công việc hoàn thành, Tòa tháp và Brahmin sẽ đổ, và lúc đó là thời điểm kết thúc của vũ trụ!

——————–

PARIS, BẮC KINH, Ý ĐÔ và SÀI GÒN
Trong các hiệu sách và tiệm bán hàng mới lạ
1883

Bản quyền đã giữ

Đó là tờ giới thiệu đầu tiên do Pháp sản xuất giới thiệu về trò chơi Tháp Hà Nội, trò chơi được dựa trên bài toán cùng tên. Xung quanh bài toán này là nhiều thứ thú vị khác mà chúng ta sẽ nói tới sau đây.

I – Nội dung bài toán

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). 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, và số lần chuyển là bao nhiêu?

Tổng quát hơn, ta có:

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.

II – Lời giải cho bài toán tổng quát

Chúng ta sẽ bắt đầu phân tích các trường hợp đơn giản để tìm hướng giải.

  • Với n=2 thì ta chỉ việc chuyển đĩa nhỏ sang cột thứ 2, chuyển đĩa to sang cột thứ 3 rồi chuyển đĩa từ cột 2 sang cột thứ 3.

  • Với n=3 ta có cách làm:
Lời giải cho trường hợp n=3.

Điểm chung của hai cách chơi trên là ta đều phải chuyển được tất cả (n-1) đĩa nhỏ qua cột thứ hai, chuyển đĩa to nhất qua cột thứ ba rồi chuyển (n-1) đĩa từ cột thứ hai sang cột thứ ba. Trò chơi sẽ kết thúc!

Nếu gọi S(n) là số bước để di chuyển n đĩa qua cột ta cần thì:

  • Bước 1: Chuyển (n-1) đĩa bé hơn từ cột (1) sang cột (2). Chúng ta có S(n-1) bước di chuyển.

  • Bước 2: Chuyển đĩa to nhất từ cột (1) sang cột (3). Chúng ta có 1 bước di chuyển.

  • Bước 3: Chuyển (n-1) đĩa từ cột (2) sang cột (3). Chúng ta có S(n-1) bước di chuyển.

Vậy, số bước để di chuyển n đĩa từ cột (1) sang cột (3) chính là

\left\{ {\begin{array}{*{20}{c}} {S(n) = 2 S(n - 1) + 1}\\ {S(2) = 3} \end{array}} \right.

và ta dễ dàng rút ra công thức tổng quát:

S(n) = {2^n} - 1.

Với n=64, ta có bài toán Tháp Hà Nội và số lần chuyển thành công là 2^{64}-1=18 446 744 073 709 551 615, đúng là phải hơn năm tỉ thế kỉ (!) mới chuyển xong.

 

III – Chương trình C++ cho bài toán Tháp Hà Nội

#include <bits/stdc++.h>#include <bits/stdc++.h>
using namespace std;

void cach_chuyen(int x, int y, int z, int n){ 
if(n==0)return;
cach_chuyen(x,z,y,n-1);
cout << x << " " << z <<endl; 
cach_chuyen(y,x,z,n-1); return;
}

int main(){ 
int n; cin>>n; 
cach_chuyen(1,2,3,n); 
return 0;
}

Bạn đọc muốn thử sức với trò chơi thú vị này có thể chơi trực tuyến tại địa chỉ https://www.mathsisfun.com/games/towerofhanoi-flash.html

TÀI LIỆU THAM KHẢO