Vô Biên – THÁP HÀ-NỘI

 1 – Mở đầu .Theo như « Wikipédia bản tiếng Việt » năm 1883 nhà xuất-bản sách khoa-học « Gauthier-Villars » ở Ba-lê  phát-hành hộp đồ chơi « LA TOUR D’ HANOI  » (CÁI THÁP HÀ-NỘI ) với nhãn-hiệu « Véritable casse-tête des Annamites »  ( Trò đố nát óc thật-sự cuả người Annam ?!) « Các phiên bản đầu tiên được sản xuất, kèm theo tờ minh họa ngoài bìa và hai tờ hướng dẫn. Các tờ hướng dẫn này chứa nhiều thông tin lịch sử quý báu về trò chơi này » ( ? !)

Tờ thứ nhất

Tờ hướng dẫn thứ nhất của trò chơi Tháp Hà Nội được Pháp sản xuất lần đầu.

“THÁP HÀ NỘI
Trò chơi trí tuệ của An nam
Trò chơi được đem về từ Đông Kinh
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à ở Đông Kinh, 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, TOKYO và SÀI GÒN
Trong các hiệu sách và tiểu thuyết
1883

   Cọc :                 A                      B                     C

Một bộ mẫu của Tháp Hà Nội

2 – Đính-chính 

Theo như « Tờ thứ nhất » (bản tiếng Pháp)  trên đây thì « trò chơi  được đem về từ Đông Kinh bởi  ông N. CLAUS DE SIAM, giáo-sư tại trường trung-học LI-SOU-STIAN » !

Thực ra thì tác-giả trò chơi này là nhà toán-học Pháp  Edouard LUCAS (1842-1891) . Ông sinh tại tỉnh AMIENS (Pháp), đã đỗ Thạc –sĩ toán-học và đã tùng làm giáo-sư toán tại trường trung-học SAINT-LOUIS (Ba-lê) .Trên đây, :

–         cái tên N. CLAUS DE SIAM là một « kết-quả đảo-chữ » (anagramme) của  LUCAS D’AMIENS ;

–         cái tên LI-SOU-STIAN  là một « kết-quả đảo chữ » của SAINT LOUIS .

Tóm lại, ông LUCAS đã dùng cách « đảo chữ » mà bày đặt ra những tên nghe lạ tai để tỏ ra trò-chơi ông đã sáng-tác có một nguồn gốc kỳ-lạ và đồng-thời để đùa rỡn với thiên-hạ .

3 – Trò chơi « Tháp Hà-nội »

3.1 – Đồ chơi gồm có –a) một cái đế trên có đóng ba cọc A, B, C (xem hình trên đây)            –b)  « n » cái điã tròn, đường kính khác nhau giữa mỗi điã có đục một lỗ tròn để ta có thể đút một  trong ba cọc trên đây vào .Từ nay, ta gọi những điã đó – theo thứ-tự từ nhỏ đến lớn –  là 1, 2, 3, ….., (n-1), n . Nếu tất cả những đĩa đều ở cọc A, theo thứ-tự từ nhỏ đến lớn, từ trên xuống dưới, thì ta viết : A(1, 2, 3, …,n), B(–), C(–) Thường ra thì n =  6, 7 hoặc 8 .

3.2 – Luật chơi . a) Mỏ đầu thì  tất các đĩa được đặt ở một cọc nào đó,-theo thứ-tự, từ  lớn đến nhỏ, từ dưới lên trên  (thành hình một cái tháp) . Ta gọi cái cọc đó là (cọc Đầu) . Mục đich của cuộc chơi là chuyển từng bước chồng đĩa từ CĐ dến một cọc khác đã định trước  – ta gọi cọc đó là CC (cọc Cuối) . Cọc còn lại, ta gọi nó là CG (cọc Giữa) .Ta phải  làm sao để chuyển  chồng đĩa từ CĐ sang CC bằng một số bước tối thiểu .

b) Mỗi bước thì ta chỉ có thể chuyển một cái đĩa ở ngọn một cọc này sang  thành ngọn một cọc khác .

c) Ta không được đặt cái đĩa ta chuyển lên một cái điã nào nhỏ hơn nó .

4 – Bài toán « Tháp Hà-nội »

Trò chơi trên đây đặt cho ta « Bài toán Tháp Hà-nội » như sau  :

« Làm cách nào để chuyển – theo đúng luật chơi — chồng « n » cái  đĩa từ cọc CĐ tới cọc  CC  bằng một số bước tối-thiểu ?  Số bước tối thiểu đó là gì ? »

4.1 – Cách giải với  số bước tối-thiểu .

Thí- dụ, trước khi bắt đầu cuộc chơi, ta định rằng CĐ = A, CC = C và CG = B .

a) Nếu ta có n = 1 cái  đĩa thì   mở đầu ta có : CĐ =  A(1),  CG = B(–), CC = C(–). Ta chỉ cần một bước để chuyển thẳng « 1 » từ

CĐ = A sang CC = C để có  CĐ  = A(–), CG =  B(–), CC = C(1)

b) Nếu n = 2 thì  mở đầu ta có CĐ = A(1,2), CG = B(–), CC = C(–) .

Ta cần phải 3 bước :

Bước 1– Chuyển « 1 » từ A(1,2) sang B(–)  để có  A(2), B(1),  C(–) .

Bước 2–Chuyển « 2 » từ A(2)    sang C(–)  để có  A(–), B(1),  C(2)

Bước 3–Chuyển « 1 » từ B(1)    sang C(2)   để có  A(–), B(–), C(1, 2)

c) Nếu ta có n = 3 thì mở đầu ta có CĐ = A(1, 2, 3), CG = B(–), CC = C(–) .Cách giải có thể chia làm 3 đoạn :

Đoạn 1 –  Chuyển từng bước (1, 2) từ A(1, 2, 3) sang B(–) . Muốn làm vậy thì ta áp dụng cách giải b) n=2 trên đây với CĐ = A, CC = B, CG = C nghiã là trong b), ta thế B bởi C và C bởi B . Vậy ta có :

Bước 1– Ta chuyển « 1 » từ A(1, 2, 3)  sang C(–) để có A(2, 3), B(–), C(1)

Bước 2– Ta chuyển « 2 » từ A(2, 3) sang  B(–) để có A(3), B(2), C(1)

Bước 3– Ta chuyển « 1 » từ C(1) sang B(2) để ta có   A(3), B(1, 2), C(–)

Đoạn 2– Đoạn 1 xong suôi, ta có A(3), B(1, 2), C(–) Nay :

Bước 4– Ta chuyển « 3 » từ A(3) sang C(–)  để ta có A(–), B(1, 2), C(3) .

Đoạn 3— Đoạn 2 xong suôi, ta có A(–), B(1, 2), C(3) , vậy ta chuyển từng bước (1, 2) từ B(1, 2) sang C(3) , bằng cách áp-dụng b) n = 2 trên đây với CĐ = B, CC = C, CG = A, nghĩa là trong b) ta thế A bởi B và B bởi A :

Bước 5–Ta chuyển « 1 » từ B(1, 2) sang A(–) để ta có A(1), B(2), C(3) .

Bước 6– Ta chuyển « 2 » từ B(2)    sang C(3) để ta có A(1), B(–), C(2, 3) .

Bước 7–Ta chuyển « 1 » từ A(1) sang C(2, 3) để ta có A(–), B(-), C(1, 2, 3) .

d) Ở a) trên đây, ta đã biết giải bài toán khi n = 1 . Ta  hãy lấy giả-thuyết rằng ta biết giải bài toán với « n – 1 » cái điã và  với

CĐ = A, CC = C và CG = B . Ta hãy chứng-minh rằng ta biết giải bài toán khi ta có “n” cái điã . Thật vậy :

Mở đầu thì ta có : CĐ = A(1, 2, 3, ….,n), CG = B(–), CC = C(–) . Ta có thể tiến-hành 3 đoạn  :

Đoạn 1 – Ta chuyển  từng bước  (1, 2, ….., n – 1) từ A(1, 2, 3, ….n) sang B(-) với CĐ = A, CC = B, CT =  C .  Ta  đã lấy giả thuyết rằng ta biết làm như vậy Đoạn 2 — Đoạn 1 xong suôi, ta có A(n), B(1, 2, 3, …,, n – 1), C(-) .

Nay ta chuyển “n” từ A(n) sang C(–) .

Đoạn 3 — Đoạn 2 xong suôi thì ta có A(–), B (1, 2, 3, …, n – 1),  C(n) .

Nay ta chuyển từng bước (1, 2, 3, …, n – 1) từ B(1, 2, 3, …, n – 1) sang C(n) .

Ta đã lấy giả-thuyết rằng ta biết làm như vậy .

Đoạn 3 xong suôi thì ta có A(–), B(–), C(1, 2, 3, …, n – 1, n) .

Tóm lại, với 3 cọc và « n » điã (n > 1) thì ta biết giải bài toán . Cách giải trên đây gọi la « cách giải đệ-quy » (Résolution récursive) .

e) Nay ta gọi  M(n) là  số bước cần thiết để giải bài toán theo cách trên đây .

Theo a) thì ta có : M(1) = 1 . Theo d), nếu ta cộng những số bước cần-thiết của mỗi đoạn thì ta có M(n)  = M(n – 1) + 1 + M(n – 1) vậy  ta có : M(1) = 1,  M(n) = 2M(n -1) + 1 . Giải những phương trình này  thì ta có :

M(n) =  (2**n) – 1 =  (2 lụy-thừa « n » ) — 1 .

f) Số buớc trên đây có phải là số bước tối thiểu cần thiết để chuyển « n » cái điã từ A(1, 2, 3, …, n) sang C(–) không . ?

Khi ta có n = 1 cái điã  thì công thức-trên đây cho ta : M(1) = 2**1 – 1 = 2 – 1 = 1 và đó tất nhiên là một số bước tối thiểu .

Nay ta lấy giả-thuyết rằng  khi  ta có (n – 1) cái điã thì công thức trên đây cho ta số bước tối thiểu : M(n – 1) = 2**(n – 1) – 1 . Ta hãy chứng minh rằng điều đó dẫn tới kết quả là khi ta có « n » cái đĩa thì số bước M(n) =  2**n – 1 cũng là số bước tối thiểu cần thiết .  Thật vậy nếu ta muốn chuyển « n » cái điã thì ta bắt buộc phải trải qua 3 Đoạn trong d) trên đây và vì thế nên M(n) không thể nhỏ hơn : 2M(n – 1) + 1  = 2 x (2**(n – 1)  + 1)  = 2**n –  2 + 1 = 2**n – 1 .

Vậy thì M(n) = 2**n – 1 là số bước tối thiểu để chuyển « n »cái điã từ A sang C .

 

4.5 —  Kết-luận – Bài toán « Tháp Hà-nội » còn có những cách giải khác như cách giải « tiếp tiến » (Résolution itérative ), cách giải dùng « trình bày nhị-phân » v…v … . Tất cả những cách giải đó đều là những cách giải tối ưu vì chúng dùng một số bước tối thiểu M(n) = 2**n – 1 .

Tuy vậy trong trường-hợp ta có  « n » cái đĩa và 4 cọc chẳng hạn, thì bài toán  vẫn còn là một « Bài toán để ngỏ » ( Problème ouvert ) vì tuy ta có những cách giải nhưng ta không biết  những số bước chúng dùng có phải là số bước tối-thiểu hay không ..

 5Nhà toán học  Edouard LUCAS ( 1842 – 1891) tức LUCAS D’AMIENS, tức N. CLAUS DE SIAM  đã  nghiên-cứu  nhiều về Số-học Ngày nay, người ta vẫn dùng « Cách chẩn-đoán tính nguyên-tố của LUCAS-LEHMER » ( Test de primalité de Lucas-Lehmer ) mà ông LUCAS đã  lập ra và sau này (1930) ông Derrick LEHMER đã hoàn-chỉnh. Năm 1876 ông LUCAS đã dùng chẩn-đoán này để chứng-minh rằng M(127) = 2**127 – 1 là một số nguyên-tố . Số này là số nguyên-tố lớn nhất người ta không dùng máy tính mà đã đạt được . Ông LUCAS  trù tính xuất-bản bộ sách « Số-học » gồm bốn quyển . Quyển đầu được xuất-bản năm 1891,  năm mà ông đã từ trần một cách đột-ngột .

Ông LUCAS đã sáng-tác bốn cuốn « Giải trí Toán-học » ( Récréations mathématiques ) nổi tiếng . Trong số những giải-trí đó thì trò chơi « Tháp Hà-nội » là trò chơi nổi tiếng nhất .

Cái chết của ông LUCAS cũng khác thường . Trong một bữa tiệc, ông đánh rơi một cái đĩa . Có tài- liệu thì kể rằng  trên cái điã có một con dao, khi cái đĩa rớt xuống thì con dao đó cắm phập vào cổ họng ông LUCAS . Có tài-liệu khác thì kể rằng  một mảnh cái điã văng vào má ông và vài ngày sau đó thì ông bị chết vì bệnh « viêm da » (Dermite) do « vi-khuẩn » (Bactérie)  Streptocoque gây ra .

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s