Tháp Hà Nội – Nơi gặp gỡ giữa toán học và tâm lý học

Các nhà toán học và các nhà tâm lý học không có nhiều điểm chung và họ cũng ít khi gặp nhau. Có lẽ bạn cũng không mong đợi họ hợp tác với nhau trong một bài toán khiêm tốn như “Tháp Hà Nội”. Bài toán này đã thu hút được sự quan tâm của cả hai giới. Trong tâm lý học, nó giúp đánh giả khả năng tư duy của một người, còn trong toán học, đây là một bài toán có nhiều tính chất đẹp, rất hấp dẫn nhưng vẫn chưa thể tìm ra câu trả lời.

Trò chơi tháp Hà Nội có luật chơi rất đơn giản: ta có 3 cây cọc và một số đĩa có kích thước khác nhau, có một lỗ ở giữa, được xếp tất cả vào một cọc với đĩa lớn ở dưới, đĩa nhỏ hơn ở trên. Nhiệm vụ là chuyển toàn bộ đĩa sang một cọc khác cũng với quy tắc đĩa lớn hơn ở dưới.

Nhà toán học Andreas M.Hinz (giáo sư toán tại Đại học Ludwig Maximilian München,Đức ) là một trong những người nhìn trò chơi dưới con mắt của toán học và tâm lý học. Ông sắp xuất bản một quyển sách về “tháp Hà Nội” và cũng cộng tác với các nhà tâm lý học để tạo ra phương pháp mới đánh giá bệnh nhân. Tháp Hà Nội là một trò chơi đơn giản thu hút sự chú ý của các nhà tâm lý học. Ông nói : trò chơi rất dễ giải thích và ta có thể xem người khác nghĩ gì!

Trò chơi có cách đặc biệt có thể đánh giá khả năng lên kế hoạch trước và chia nhỏ vấn đề để giải quyết, cũng dễ dàng thay đổi luật chơi : ta có thể thêm nhiều đĩa, thậm chí thay đổi vị trí bắt đầu và kết thúc. Tính chất đệ quy của trò chơi và khả năng biến đổi của nó cũng dẫn đến nhiều tính chất toán học rất thú vị.

Đồ thị tháp Hà Nội

Cách tốt nhất để bao quát trò chơi là vẽ ra một mạng lưới hay một đồ thị thể hiện tất cả các vị trí có thể. Lấy ví dụ trường hợp có 3 cọc và 3 đĩa, đánh số 3 đĩa là 1, 2 và 3, với đĩa 1 nhỏ nhất và đĩa 3 lớn nhất. Ta có thể mô tả vị trí các đĩa bằng một bộ 3 số , ví dụ (1,3,1), khi đó ta hiểu đĩa 1 ở cột 1, đĩa 2 cột 3 và đĩa 3 ở cột 1.

Xem một bộ 3 như là một điểm và nối 2 điểm lại với nhau nếu từ bộ ba này bằng một thao tác có thể thu được bộ ba kia. Chẳng hạn, bắt đầu với vị trí (1,1,1) (tất cả đĩa đều ở cột 1) ,các bước di chuyển có thể là : chuyển đĩa 1 sang cột 2, hai đĩa còn lại vẫn giữ nguyên (2,1,1) hoặc chuyển đĩa 1 sang cột 3, hai đĩa còn lại giữ nguyên (3,1,1) . Có tất cả 33=27 bộ 3. Liệt kê và sắp xếp tất cả các trường hợp, ta được đồ thị:

Đồ thị trên gọi là “đồ thị Hà Nội” và được ký hiệu là H3 , chỉ số 3 tương ứng với 3 đĩa.

Đồ thị Hà Nội giúp ta dễ dàng theo dõi quá trình một người đang chơi. Giáo sư Andreas M.Hinz nói : lý do chính mà các nhà tâm lý học thích thú với đồ thị Hà Nội là ở chỗ ta có thể biết trước các thao tác của người chơi và dễ dàng nhận ra liệu người chơi có đưa ra các bước di chuyển tối ưu hay không , hay tại vị trí nào gây khó khăn khiến người chơi phải suy nghĩ nhiều…và cũng chính vì thế ta có thể thu được nhiều thông tin từ kết quả kiểm tra trên một hoặc một nhóm người.

Rõ ràng, trò chơi với 3 đĩa khá dễ dàng, nhưng, với 4,5,6 hay n đĩa thì sao? Thử vẽ đồ thị H4 , ta thấy một tính chất rất đẹp, H4 gồm 3 đồ thị H3 ghép lại , mỗi H3 nối với 2 cái còn lại bằng một cạnh.

Tương tự như vậy, H5 cấu thành từ 3 đồ thị H4 , H6 cấu thành từ 3 đồ thị H5 ,vv…v. Tính chất này nhờ vào tính đệ quy của trò chơi. Nếu ta bỏ đĩa lớn nhất ra thì phiên bản trò chơi với n+1 đĩa trở thành bản n đĩa.

Ví dụ với trường hợp 4 đĩa và đĩa 4 (lớn nhất) nằm ở cột 1. Xem như đĩa 4 không tồn tại, rõ ràng các bước di chuyển 3 đĩa còn lại y hệt như phiên bản trò chơi với 3 đĩa , do đó, nhìn vào đồ thị H4, các điểm nút biểu thị đĩa 4 ở cột 1 tạo thành đồ thị y hệt H3 . Tương tự như vậy, các điểm nút biểu thị đĩa 4 nằm ở cột 2, đĩa 4 nằm ở cột 3 cũng tạo thành đồ thị y hệt H3. Ta chỉ có thể di chuyển đĩa 4 nếu 3 đĩa còn lại đều nằm trên cùng một cột trong hai cột còn lại, do đó, bằng phép chuyển đĩa 4 sang cột còn trống đó và tiếp tục di chuyển các đĩa 1,2,3 , ta lại thu được một đồ thị dạng H3 và đồ thị này nối đồ thị (cũng dạng H3 ) lúc nãy tại điểm nút là đỉnh tam giác lớn của H3. Như vậy, các đồ thị dạng H3 từng đôi nối với nhau thông qua một cạnh của tam giác H3. Lý luận tương tự, Hn+1 được cấu thành từ 3 đồ thị y hệt Hn nối với nhau với bất kỳ n đĩa.

Do đã biết thuật toán để chơi trò này, nên có thêm nhiều đĩa hơn thì trò chơi cũng không khó hơn. Tuy nhiên, khi ta thay quy tắc chơi bằng cách thay đổi giá trị ban đầu và kết thúc, tất cả đĩa không phải chỉ trên một cột, có thể nằm ở nhiều cột khác nhau và có thể xếp theo trình tự khác, lúc này, trò chơi thật sự rất khó. Vấn đề đặt ra, đâu là lời giải tối ưu và các bước di chuyển tối thiểu là bào nhiêu? Trong trường hợp thông thường, với các đĩa bắt đầu và kết thúc cùng nằm trên cùng một cột thì số bước di chuyển nhỏ nhất là 2n-1, và trong trường hợp vị trí bắt đầu và kết thúc tùy ý , thì số bước di chuyển nhỏ nhất không vượt quá 2n-1. Ta có thể chứng minh điều này bằng quy nạp!

Khi số lượng đĩa tăng lên vô hạn, hình dạng đồ thị sẽ trông như thế này :

Hình trên là tam giác Sierpiński. Để tạo ra hình trên ta làm như sau: Vẽ một tam giác đều, sau đó tô màu phủ kín tam giác. Dựng một tam giác có 3 đỉnh là trung điểm 3 cạnh của tam giác ban đầu, sau đó xóa tam giác mới dựng này đi. Thực hiện tương tự cho tất cả các tam giác được tạo ra, lặp lại vô hạn các bước như vậy ta được tam giác Sierpiński

Tam giác Sierpiński là một trong những đối tượng phổ biến làm ví dụ cho hình học Fractal, có tính tự đồng dạng – lấy bất kỳ một tam giác nào trong tam giác Sierpiński , phóng to nó lên và ta sẽ nhận được một hình chính là tam giác Sierpiński lớn ban đầu! Rất thú vị ! Điều đáng ngạc nhiên là ở chỗ, khi xây dựng tam giác Sierpiński, các tam giác con nhỏ dần đến diện tích bằng 0, tuy nhiên, lại không phải là đối tượng một chiều. Do đó, các nhà toán học đã tổng quát khái niệm về số chiều để nắm bắt bản chất của các đối tượng như vậy. Theo đó, tam giác Sierpiński có số chiều là log3/log2 ≈1,585.

Nếu ta thêm càng nhiều đĩa vào trò chơi tháp Hà Nội thì đồ thị tương ứng sẽ càng giống tam giác Sierpiński . Khi số đĩa tăng lên vô hạn, cấu trúc đồ thị Hà Nội chính là tam giác Sierpiński!

Chắc ai cũng biết tam giác Pascal. Một điều giống nhau không thể ngờ là, xét 2n dòng đầu tiên của tam giác Pascal, nối các số lẻ với các số lẻ kế tiếp nó (xét theo đường ngang và cả đưởng chéo) bằng một đoạn thẳng thì đồ thị nhận được có cấu trúc y hệt Hn.

Cấu trúc giống nhau của đồ thị Hà Nội, tam giác Sierpiński và tam giác Pascal không chỉ đẹp mà còn rất hữu ích, nếu kết quả trong đối tượng này khó chứng minh, ta có thể chứng minh nó dễ dàng trong đối tượng kia. Tiêu biểu, khoảng cách trung bình của hai điểm trong tam giác Sierpiński là bao nhiêu? Bài toán này rất khó và chưa có câu trả lời cho tới khi GS. Andreas M.Hinz tính được giá trị này nhờ đồ thị Hà Nội. Giả sử độ dài cạnh tam giác ban đầu dùng để xây dựng tam giác Sierpiński là 1, thì khoảng cách trung bình giữa hai điểm của tam giác Sierpiński là 466/885!

Tăng số lượng cột cho trò chơi

Việc thêm nhiều đĩa , ta đã khảo sát, thế nếu thêm nhiều cọc hơn thì trò chơi sẽ như thế nào? Rõ ràng, trò chơi sẽ dễ hơn vì ta có nhiều lựa chọn di chuyển các đĩa. Tuy nhiên, cấu trúc của đồ thị đã không còn giữ được sự đơn giản. Đĩa lớn nhất có nhiều lựa chọn di chuyển hơn trong khi các đĩa còn lại không nhất thiết phải cùng nằm trên một cột nữa, do đó, phần đồ thị khi đĩa lớn nhất nằm ở cột 1 nối với phần đồ thị khi đĩa lớn nhất nằm ở cột 2 không chỉ một đường, mà rất nhiều đường tạo nên một đồ thị phức tạp. Với trường hợp 4 cột, đồ thị không còn phẳng nữa mà nó có dạng 3 chiều ! Sự rắc rối này khiến cho những câu hỏi tưởng chừng đơn giản nhất, hóa ra lại rất khó trả lời! Chẳng hạn như, không ai biết số bước tối ưu là bao nhiêu! Ta chỉ có thể xây dựng lời giải tối ứu giải quyết bài toán với trường hợp nhiều cột dựa vào phỏng đoán Frame-Stewart, nhưng, đã 70 năm mà vẫn chưa giải ra ! Hiện tại, cùng với sự trợ giúp của máy tính, ta chỉ có thể giải quyết bài toán tối ưu cho tới 30 đĩa!

Phương pháp đánh giá mới dựa vào trò chơi tháp Hà Nội đang được các nhà tâm lý học sử dụng để kiểm tra những người mất trí hay những bệnh nhân đột quỵ để xem vùng nào của não đã bị suy yếu.

Nhà toán học Ian Stewart từng nói: mọi người bị hấp dẫn bởi toán học vì đó là niềm vui, là vẻ đẹp và sự hữu ích. GSHinz cũng thêm rằng: điểm thứ tư khiến mọi người thích toán bởi vì sự ngạc nhiên của nó. Một đối tượng toán học thú vị như tháp Hà Nội chắc hẳn đã có đủ 4 điểm trên!

Theo Diendantoanhoc.net