Đề tài Thuật toán frame – stewart giải bài toán tháp Hà Nội tổng quát

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC SƢ PHẠM NGUYỄN THỊ HỒNG PHƢỢNG THUẬT TOÁN FRAME – STEWART GIẢI BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC SƢ PHẠM NGUYỄN THỊ HỒNG PHƢỢNG THUẬT TOÁN FRAME – STEWART GIẢI BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Giải tích Mã số: 60 46 01 Người hướng dẫn khoa học: PGS. TS. TẠ DUY PHƢỢNG THÁI NGUYÊN - 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 1 MỤC LỤC Trang MỤC LỤC LỜI NÓI ĐẦU ............................................................................................... 2 Chƣơng 1 ....................................................................................................... 4 TỔNG QUAN VỀ TRÒ CHƠI THÁP HÀ NỘI .......................................... 4 §1. Lịch sử trò chơi Tháp Hà Nội ............................................................ 4 §2. Sơ lược về bài toán tháp Hà Nội tổng quát, các bài toán cải biên và các vấn đề toán học liên quan ................................................................ 15 Chƣơng 2: TRÒ CHƠI THÁP HÀ NỘI..................................................... 21 §1 Trò chơi tháp Hà Nội và thuật giải đệ qui.......................................... 21 §2 Giải bài toán tháp Hà Nội bằng biểu diễn trong hệ đếm cơ số 2 ........ 26 §3 Đồ thị Hà Nội.................................................................................... 34 §4 Giải bài toán Tháp Hà Nội trên máy tính ........................................... 38 Chƣơng 3: BÀI TOÁN THÁP HÀ NỘI VỚI BỐN CỌC (Trò chơi Reve-The Reve’s Puzzle) ............................................................................. 39 §1 Trò chơi Tháp Hà Nội với bốn cọc .................................................... 39 §2 Tính số bước chuyển tối ưu trong trò chơi Tháp Hà Nội với bốn cọc...... 43 Chƣơng 4: BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT............................. 52 §1 Tính số ( )pS n trong thuật toán Frame-Stewart cho trò chơi Tháp Hà Nội tổng quát ................................................................................... 52 §2 Đánh giá ( )pS n ............................................................................... 68 §3 Sự tương đương của một số thuật toán giải bài toán Tháp Hà Nội tổng quát................................................................................................ 70 KẾT LUẬN .................................................................................................. 78 TÀI LIỆU THAM KHẢO ........................................................................... 79 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 2 LỜI NÓI ĐẦU Trò chơi (Bài toán) Tháp Hà Nội được phổ biến rộng rãi ở Paris năm 1883 bởi nhà toán học Edouard Lucas, là một bài toán nổi tiếng thế giới, hiện nay đang được nghiên cứu bởi rất nhiều nhà toán học và khoa học máy tính, các chuyên gia giáo dục và y học, được đưa vào nhiều giáo trình tin học và sách về trò chơi toán học như một ví dụ điển hình về thuật toán đệ qui và lập trình căn bản, nhưng hình như chưa được chú ý nghiên cứu ở Việt Nam. Mặc dù trò chơi Tháp Hà Nội có mặt trên khá nhiều trang WEB và giáo trình tiếng Việt, số lượng bài viết tiếng Việt giới thiệu về trò chơi và bài toán Tháp Hà Nội trên các tạp chí là rất ít và còn rất sơ lược (xem [1]-[6]), hình như chưa có bài nghiên cứu tiếng Việt nào về bài toán Tháp Hà Nội, trong khi đó chỉ tính riêng số bài báo nghiên cứu về bài toán Tháp Hà Nội trong lĩnh vực Toán-Tin học đã có đến hơn 450 bài với khoảng 250 bài với đầu đề có cụm từ "The Tower of Hanoi", đăng trên hơn 100 tạp chí khoa học uy tín (trong [5] thống kê số lượng bài báo khoa học viết về Tháp Hà Nội là 464 bài). Đó là chưa kể đến những bài viết về sử dụng bài toán Tháp Hà Nội trong khoa học giáo dục và y học. Trò chơi Tháp Hà Nội thú vị đến mức nó đã được dùng làm đề tài của một số luận án Tiến sĩ và luận văn cao học. Một hội thảo khoa học quốc tế [21] với tên gọi Workshop on the Tower of Hanoi and Related Problems đã được tổ chức năm 2005. Bài toán Tháp Hà Nội không chỉ thú vị ở chỗ nó mang tên Hà Nội, thủ đô của Việt nam, mà nó hấp dẫn các nhà Toán-Tin học bởi nó liên quan đến nhiều vấn đề như giải thuật đệ qui, hệ đếm, tam giác Pascal, thảm Sierpinski, lý thuyết đồ thị và chu trình Hamilton, ôtômát hữu hạn, độ phức tạp tính toán,.... Bài toán Tháp Hà Nội gợi ý cho nhiều nghiên cứu trong khoa học máy tính và toán học. Luận văn Thuật toán Frame-Stewart giải bài toán Tháp Hà Nội tổng quát có mục đích trình bày tổng quan về một thuật toán quan trọng giải bài toán Tháp Hà Nội với số cọc bất kì. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 3 Luận văn gồm phần mở đầu, bốn Chương và phần tài liệu tham khảo. Chương 1. Tổng quan về trò chơi Tháp Hà Nội. Chương 2. Bài toán Tháp Hà Nội cổ điển. Chương 3. Bài toán Tháp Hà Nội với bốn cọc. Chương 4. Bài toán Tháp Hà Nội tổng quát. Chương 1 giới thiệu tổng quan về Trò chơi Tháp Hà Nội. Lời giải Bài toán Tháp Hà Nội cho ba cọc được trình bày trong Chương 2. Sau hơn 100 năm, trò chơi Tháp Hà Nội đã có những cải biên và tổng quát hoá (trò chơi Tháp Hà Nội xoay vòng, trò chơi Tháp Hà Nội song song, trò chơi Tháp Hà Nội với nhiều cọc,...). Những cải biên và tổng quát hóa này dẫn đến những vấn đề toán học thú vị, thậm chí dẫn tới nhiều bài toán hiện nay chưa có lời giải. Trong luận văn này, chúng tôi tập trung trình bày trong Chương 3 và Chương 4 lời giải của bài toán Tháp Hà Nội, đó là Thuật toán đệ qui dạng Frame-Stewart giải bài toán Tháp Hà Nội tổng quát. Luận văn được hoàn thành dưới sự hướng dẫn tận tình của PGS.TS Tạ Duy Phượng. Em xin bầy tỏ lòng biết ơn sâu sắc nhất đối với Thầy và xin được cảm ơn Thầy đã cung cấp nhiều tài liệu đồng thời cho phép sử dụng Bản thảo cuốn sách của Thầy về Tháp Hà Nội. Em xin cảm ơn các Thầy Cô của Đại học Thái Nguyên và Viện Toán học đã tận tình giảng dạy em trong suốt quá trình học cao học. Tôi xin cảm ơn khoa Toán trường ĐHSP Thái Nguyên, khoa Sau Đại học trường ĐHSP Thái Nguyên đã quan tâm giúp đỡ, tạo điều kiện thuận lợi cho tôi thực hiện kế hoạch học tập của mình. Xin cảm ơn người thân, đồng nghiệp, bạn bè đã cổ vũ động viên tôi trong suốt quá trình làm luận văn. Thái Nguyên, 19.8.2010 Nguyễn Thị Hồng Phượng Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 4 Chƣơng 1 TỔNG QUAN VỀ TRÒ CHƠI THÁP HÀ NỘI §1. Lịch sử trò chơi Tháp Hà Nội Bìa cuốn sách của E. Lucas xuất bản tại Paris năm 1895, trong đó có 4 trang (179-183) viết về trò chơi Tháp Hà Nội. 1.1 Truyền thuyết Theo một truyền thuyết, liên tục suốt ngày đêm, các nhà tu hành của tòa tháp Brahma trong thành Bernares (Ấn Độ) phải chuyển 64 đĩa vàng từ một cọc này sang cọc khác của tòa tháp. Các đĩa có kích thước khác nhau và lúc Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 5 đầu được đặt trên một trong ba cọc của tòa tháp theo thứ tự đĩa nhỏ ở trên, đĩa lớn ở dưới. Đĩa trên cùng được chuyển sang cọc khác, mỗi lần chỉ di chuyển một đĩa. Do tính dễ vỡ, đĩa lớn không được đặt lên trên đĩa nhỏ. Trong quá trình di chuyển, có thể đặt đĩa lên một cọc trung gian. Khi công việc hoàn thành, tòa tháp sẽ đổ, và lúc đó cũng là thời điểm kết thúc của vũ trụ với một tiếng nổ khủng khiếp! 1.2 Lịch sử Dựa trên truyền thuyết về tháp Brahma, và có thể, theo truyền thuyết về sự tồn tại những ngôi tháp cổ đồng dạng với tháp Brahma trong vùng đất phật giáo linh thiêng gần Hà Nội (Bắc Ninh?, Vĩnh Phúc?), Việt Nam, nhà toán học người Pháp Edouard Lucas (quê ở Amiens) đã phổ biến Trò chơi Tháp Hà Nội ở Paris năm 1883 với tên giả là giáo sư N. Claus. Năm 1884, Parvile trong [14] đã trình bày lời giải bài toán Tháp Hà Nội và tiết lộ giáo sư N. Claus chính là tên giả của nhà nghiên cứu lí thuyết số nổi tiếng Eduard Lucas. Trên bìa của hộp đựng trò chơi sản xuất năm 1883 và trong cuốn sách L’Arithméique Amusante, xuất bản tại Paris năm 1895 (sau khi Ông mất), chính Edouard Lucas đã viết ([12], trang 179): “…la Tour d’Hanoi, véritable casse- tête annamite…” (Tháp Hà Nội, một trò chơi trí tuệ của người Annam), nhưng tại sao ông lại gọi trò chơi này là trò chơi Tháp Hà Nội thì chưa có câu trả lời thật rõ ràng. Rất có thể (theo Edouard Lucas), trò chơi Tháp Hà Nội “đã xuất hiện ở Đông Á từ thế kỷ 19 hoặc trước đó. Các đĩa được làm bằng sứ ở Trung Quốc, Nhật Bản và Đông Kinh (Bắc Kì, Việt Nam)”. Tuy nhiên, cho tới nay, các nhà lịch sử có lẽ vẫn chưa tìm thấy các đĩa sứ của trò chơi tháp Hà Nội tại châu Á. Những hộp đựng trò chơi cũ nhất vẫn là hộp đựng các đĩa sản xuất tại Pháp năm 1883. Theo David G. Pool [15], trích dẫn theo P. J. Hilton [10], sự tồn tại những ngôi tháp gần Hà Nội (Việt Nam) là lí do để E. Lucas đã đặt tên cho trò chơi của mình là Trò chơi Tháp Hà Nội. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 6 Có một giả định rằng: “nhà toán học đến thăm Việt Nam, ngắm cảnh Hồ Gươm và bị quyến rũ bởi vẻ đẹp của Tháp Rùa nên đã đặt tên là Bài toán Tháp Hà Nội”. Nếu có tư liệu khẳng định nhà toán học nổi tiếng E. Lucas đã đến Hà Nội từ trước năm 1883 (Pháp chiếm Hà Nội năm 1882) thì thật là thú vị. Tuy nhiên, lúc đó E. Lucas đã ra khỏi quân đội và đang dạy học, vì vậy ít có khả năng ông đã đến Hà Nội. Cũng có lẽ Cột cờ Hà Nội đã gợi ý cho E. Lucas đặt tên trò chơi của mình là Tháp Hà Nội: “The Flag Tower of Hanoi may have served as the inspiration for the name”. Cột cờ Hà Nội có đáy gồm ba khối vuông xây chồng lên nhau. Trò chơi Tháp Hà Nội đơn giản nhất cũng gồm ba đĩa tròn xếp chồng lên nhau. Cột cờ Hà Nội xây năm 1805-1812, Tháp Rùa xây năm 1886, trò chơi Tháp Hà Nội xuất hiện ở Paris 1883. Có thể Pháp chiếm Hà Nội là đề tài thời sự ở Paris vào những năm 1882-1883, và điều này gợi ý E. Lucas đặt tên cho trò chơi của mình là Tháp Hà Nội? Trò chơi Tháp Hà Nội vừa được phổ biến đã được đón nhận rộng rãi vì sự đơn giản và hấp dẫn của nó. Mặc dù chưa có câu trả lời rõ ràng về lí do E. Lucas đặt tên cho trò chơi của mình là trò chơi Tháp Hà Nội, người Việt Nam vẫn có thể tự hào và cần quan tâm về trò chơi này. Dưới đây là bìa của hộp đựng trò chơi Tháp Hà Nội sản xuất lần đầu tiên tại Paris năm 1883 và hai tờ hướng dẫn qui tắc chơi. Đây là những tư liệu quí về lịch sử trò chơi. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 7 Bìa của hộp đựng trò chơi Tháp Hà Nội đƣợc bán lần đầu tại Paris năm 1883. Trên tờ bìa này có một hình tháp 10 tầng, cây tre, người Annam (Việt Nam) và ghi rõ: La Tour d’Hanoϊ, Veritable casse-téte Annamite Jeu, rapporté du Tonkin par le professeur N. Claus (de Siam) du college Mandarin Li-Sou- Sian (Tháp Hà Nội, Trò chơi trí tuệ của người Annam, được giới thiệu bởi giáo sư N. Claus (ở Siam), trường trung học Li-Sou-Sian). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 8 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 9 Bản dịch tờ hướng dẫn thứ nhất giới thiệu trò chơi Tháp Hà Nội được sản xuất lần đầu tiên tại Paris: THÁP HÀ NỘI Trò chơi trí tuệ của người Annam Trò chơi được đem về từ Đông Kinh bởi Giáo sư N. CLAUS (DE SIAM) Trường Cao đẳng 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ỏ từng đĩ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. 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 Bản quyền đã giữ. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 10 Bản dịch tờ hướng dẫn trò chơi Tháp Hà Nội được sản xuất lần đầu tại Paris: Luật chơi và cách chơi trò chơi THÁP HÀ NỘI Đế đặt nằm ngang; các cọc thẳng đứng. Các đĩa đặt theo thứ tự từ lớn đến nhỏ từ thấp lên cao, tạo nên một Tòa tháp. Trò chơi đòi hỏi di chuyển các đĩa, bằng cách đặt chúng vào cọc bên cạnh, mỗi lần chuyển một đĩa, theo luật sau: I. Sau mỗi lần chuyển, các đĩa đều nằm trên một, hai, hoặc ba cọc, theo thứ tự từ lớn đến nhỏ từ thấp đến cao. II. Đĩa trên cùng của một trong ba cọc được đặt vào cọc trống. III. Đĩa trên cùng của một trong ba cọc đĩa được đặt lên một trong hai cọc khác, nếu đĩa này nhỏ hơn các đĩa của cọc đó. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 11 Trò chơi có thể dễ dàng tự khám phá, bằng việc giải quyết dần từ 3, 4, và 5 đĩa. Trò chơi luôn giải được và đòi hỏi thời gian chơi lâu khoảng gấp đôi mỗi khi cho thêm một đĩa vào Tòa tháp. Bất kì ai giải được cho tám đĩa, ví dụ, chuyển các đĩa từ cọc 1 sang cọc 2, cũng sẽ biết cách giải cho chín đĩa. Chỉ cần chuyển tám đĩa sang cọc 3, rồi chuyển đĩa thứ chín sang cọc 2, và mang tám đĩa từ cọc 3 về cọc 2. Bây giờ, khi thêm một đĩa vào trò chơi, tổng số di chuyển tăng gấp đôi, cộng với một, so với trước. Với tháp hai đĩa ba lần chuyển là đủ Số đĩa Số lần chuyển Ba đĩa 7 lần 6 đĩa 63 lần Bốn đĩa 15 lần 7 đĩa 127 lần Năm đĩa 31 lần 8 đĩa 255 lần Với tốc độ một di chuyển mất một giây, cần bốn phút để chuyển tám đĩa. Các biến thể của trò chơi: Có thể thay đổi đến vô cùng điều kiện của bài toán tháp Hà Nội như sau. Khi bắt đầu, xếp các đĩa theo thứ tự bất kỳ lên một, hai, hay cả ba cọc. Sau đó cần xây dựng lại tòa tháp trên một cọc định trước. Với 64 đĩa, số lần di chuyển là khổng lồ, số này dài 50 chữ số. Xem thêm chi tiết trong chương nói về Baguenaudier (trò chơi tháo vòng) ở: TOÁN HỌC GIẢI TRÍ bởi Mr. Édouard Lucas giáo sư toán học cao cấp tại Lycée Saint-Louis Hai tập nhỏ, trong hai màu Paris, 1883, bởi GAUTHER-VILLARS, máy in của Académie des Sciences và Ecole Polytechnique Trên mạng Internet có rất nhiều chương trình hiển thị minh họa và hướng dẫn trò chơi Tháp Hà Nội (với ba cọc). Ngoài ra, có thể tìm mua trò chơi Tháp Hà Nội làm bằng gỗ hoặc sứ tại các cửa hàng Việt Nam hoặc nước ngoài để giải trí. Dưới đây chúng tôi chụp lại bốn trang (179-183) viết về Tháp Hà Nội trong cuốn sách Số học vui của E.Lucas xuất bản năm 1895 (sau khi Ông mất) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 12 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 13 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 14 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 15 §2. Sơ lƣợc về bài toán tháp Hà Nội tổng quát, các bài toán cải biên và các vấn đề toán học liên quan Trò chơi Tháp Hà Nội ngày càng được các nhà toán học quan tâm, Với sự phát triển của tin học, bài toán tháp Hà Nội lại càng thu hút sự chú ý của các nhà toán-tin học. Nó trở thành ví dụ điển hình về phương pháp giải đệ qui và lập trình căn bản. 2.1 Bài toán Tháp Hà Nội tổng quát Bài toán Tháp Hà Nội với ba cọc và n đĩa có thể giải được dễ dàng theo thuật giải đệ qui (xem Chương 2). Hơn nữa, có thể biết chính xác số lần cần chuyển tối ưu cho bài toán với n đĩa là 2 1n  lần. Vì vậy nó thường được dùng làm thí dụ kinh điển về lập trình căn bản và thuật giải đệ qui cũng như minh họa về độ phức tạp tính toán (thời gian mũ) của bài toán với thuật giải đơn giản và tối ưu. Một mở rộng tự nhiên của bài toán Tháp Hà Nội với ba cọc là Bài toán Tháp Hà Nội với bốn (hoặc nhiều) cọc. Theo một số tài liệu, chính tác giả của bài toán Tháp Hà Nội, E. Lucas cũng là người đầu tiên xét bài toán với nhiều cọc vào năm 1899. Năm 1902- 1903 Henry Ernest Dudeney đã viết về bài toán Tháp Hà Nội với bốn cọc trong hai bài báo. Trong hai trang đầu tiên của cuốn sách nổi tiếng của Ông The Canterbury Puzzles (xem [7]) ông đã viết về bài toán này (và gọi là Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 16 Reve's puzzle) với số cọc là 4 và số đĩa là 8, 10 hoặc 21, chỉ có khác là Ông đã thay các đĩa bằng các quân cờ. Trong phần lời giải (trang 131-132), Dudeney đã khẳng định (không chứng minh) rằng số lần chuyển cần thiết tương ứng với 8, 10 hoặc 21 đĩa là 33, 49 hoặc 321. Hơn nữa, Ông còn xét trường hợp với số đĩa là số tam giác, tức là các số ( 1) 2 k k k t   , 1,2,...k  Giả sử ( 1) 2 k k k t   là số tam giác thứ k và giả sử ( )M n là số lần chuyển tối thiểu cần thiết để chuyển xong n đĩa. Dudeney tuyên bố rằng    4 4 12 2 1 k k kM t M t    ,  4 1 1M  . Từ đây ta có  4 3 5M  ;  4 6 17M  ,  4 10 49M  ,… Tuy nhiên Dudeney không cho một thuật toán nào cho phép tìm ra các số này, và cũng không có một gợi ý nào cho trường hợp số đĩa không phải là số tam giác, thí dụ khi 8n  . Bài toán tổng quát với 3p  cọc, p là số bất kì với số đĩa n bất kì được B. M. Stewart đề xuất năm 1939 (Problem 3918 trong tạp chí The Americal Mathematical Montly [17]). Lời giải của bài toán này đã được Stewart [19] và Frame [9] trình bày cũng trong tạp chí này năm 1941. Các thuật toán của Stewart và Frame cùng với một số thuật toán cải biên khác đã được chứng minh là tương đương theo nghĩa số lần chuyển đĩa là bằng nhau (xem [11]). Vì vậy người ta thường gọi thuật toán của hai ông hoặc các thuật toán cải biên tương tự là thuật toán Frame- Stewart. Thuật toán Frame-Stewart cùng các thuật toán tương đương sẽ được trình bày trong Chương 3 và Chương 4. Thuật toán Stewart (1941) Thuật toán truy hồi do Stewart đề xuất 1941, được coi là presumably- optimal solution (lời giải giả định là tối ưu) cho bài toán bốn cọc (hoặc nhiều hơn). Giả sử n là số đĩa và p là số cọc. Để giải bài toán tháp Hà Nội với p cọc, ta thực hiện các bước sau. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 17 Bước 1. Với số l , 1 l n  , chuyển l đĩa trên cùng tới cọc 1, mất ( )pS l lần chuyển. Sử dụng tất cả các cọc trong khi chuyển. Bước 2. Giữ nguyên cọc 1 chứa l đĩa trên cùng. Chuyển n l đĩa tới cọc đích, sử dụng 1p  cọc còn lại (vì cọc 1 đang được dùng để chứa l đĩa nhỏ nhất), mất 1( )pS n l  lần chuyển. Bước 3. Cuối cùng, chuyển l đĩa trên cùng từ cọc 1 tới cọc đích, mất ( )pS l lần chuyển nữa. Được phép sử dụng tất cả các cọc. Như vậy, tổng cộng cần 12 ( ) ( )p pS l S n l  lần chuyển. Bài toán đặt ra là, cần tính số l để tổng này là nhỏ nhất. Thuật toán Stewart nói trên (với cách chọn l như trên) cho phép tìm ra một (một vài) giá trị i sao cho  1 1 1 2 ( ) ( ) min 2 ( ) ( )p p p p l n S i S n i S l S n l         . (1.1) Nói cách khác, các giá trị i thỏa mãn (1.1) là số bước chuyển tối ưu trong lớp các thuật toán đề nghị. Stewart và Frame cũng đã chứng minh rằng, nếu n là số tam giác kn t , thì cách chọn tối ưu nhất cho l là l k , trong khi đó nếu 1k kt n t   thì cả hai giá trị 1k  và k đều là cách chọn tối ưu cho l . Như vậy, Stewart và Frame đã đề xuất thuật toán hiển cho bài toán Tháp Hà Nội với bốn cọc. Thuật toán này trùng với lời giải của Dudeney trong các trường hợp riêng nêu trên. Từ đây ta cũng có nhận xét rằng, khác với trường hợp bài toán với ba cọc, lời giải cho bài toán với bốn cọc có thể là không duy nhất. Otto Dunkel, tổng biên tập của tạp chí The Americal Mathematical Montly khi cho đăng hai lời giải trên đã chỉ ra rằng chứng minh tính tối ưu của Frame và Stewart chỉ áp dụng được cho các thuật toán của một lược đồ chung mô tả bởi Frame và Stewart mà thôi. Nói cách khác, Frame và Stewart mới chỉ chứng minh rằng trong số tất cả các giá trị có thể của l theo thuật Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 18 toán của hai ông phải có ít nhất một giá trị i làm cực tiểu số lần chuyển. Tuy nhiên hai ông chưa chứng minh rằng thuật toán tối ưu bắt buộc phải có dạng trên. Và điều này cho tới nay vẫn chưa chứng minh được. Và lời giải của Frame và Stewart cần phải coi một cách đúng đắn là “lời giải giả định là tối ưu” (presumed optimal solution), chứ chưa chứng minh được là lời giải tối ưu. Từ 1941 đến nay, rất nhiều người khác đã nghiên cứu thuật toán này (xem trích dẫn đầy đủ trong [5]). Gần đây một số tác giả đề nghị một số thuật toán hồi qui tương đương với thuật toán Frame và Stewart (xem [11]). Nhưng tính tối ưu của thuật toán vẫn chưa được chứng minh. Đây là một ví dụ tiêu biểu cho thấy từ một bài toán đơn giản, có thể giải được, nhưng bằng cách nới lỏng một số ràng buộc của nó thì lại trở thành khó hơn rất nhiều do xuất hiện những bài toán mới. Việc chưa chứng minh được lời giải cho bài toán với bốn hoặc nhiều cọc là tối ưu không suy ra rằng không tồn tại thuật toán tìm (tất cả) các nghiệm tối ưu. Mặc dù chưa chứng minh được số lần chuyển đĩa tối ưu chính xác là bao nhiêu, nhưng thuật toán Frame-Stewart và các cải biên của nó cũng đã cho "lời giải được giả định là tối ưu" (presumed-optimal solution). Giả thuyết Frame-Stewart (chưa được chứng minh) nói rằng thuật toán Frame-Stewart luôn cho lời giải tối ưu. Tính tối ưu của thuật toán Frame- Stewart đã được kiểm tra trên máy tính cho số đĩa nhỏ hơn 30. Theo Donald Knuth, nhà tin học nổi tiếng thế giới đã gọi giả thuyết này là “giả thuyết Frame” và Ông đã viết: “Tôi nghi ngờ rằng ai đó đã giải được giả thuyết này. Nó thật sự khó”. 2.2. Bài toán Tháp Hà Nội cải biên Bài toán Tháp Hà Nội có khá nhiều cải biên rất thú vị. Mỗi qui tắc chơi mới lại làm trò chơi Tháp Hà Nội thêm phong phú và lại xuất hiện thêm nhiều vấn đề toán học mới. Dứới đây chúng tôi sơ lược liệt kê một số cải biên của trò chơi Tháp Hà Nội. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 19 2.2.1 Bài toán Tháp Hà Nội với vị trí bất kì Bài toán Tháp Hà Nội với ba cọc và n đĩa đã được E. Lucas cải biên ngay khi phổ biến cách chơi năm 1883. Đó là trò chơi Tháp Hà Nội với vị trí bất kì: có thể coi vị trí của đĩa là bất kì (không nhất thiết phải tất cả các đĩa nằm trên một cọc, mà có thể ở trên các cọc khác nhau, miễn là tuân theo qui tắc “đĩa ở trên nhỏ, đĩa nằm dưới to”). Bài toán đã được Hinz nghiên cứu khá kĩ. 2.2.2 Bài toán Tháp Hà Nội quay vòng (cyclic moving) Có thể đóng ba cọc trên ba đỉnh của một tam giác và chuyển động các đĩa theo chiều quay của kim đồng hồ hoặc ngược lại. 2.2.2 Bài toán Tháp Hà Nội song song (parallel moving) Có thể chuyển các đĩa từ cọc này sang cọc khác trong cùng một thời gian. 2.2.2 Bài toán Tháp Hà Nội hỗn hợp Kết hợp giữa bài toán Tháp Hà Nội quay vòng với chuyển động song song. Các cải biên của bài toán Tháp Hà Nội đặt ra những bài toán mới thú vị, có thể nói khó không kém bài toán ban đầu. 2.3 Một số vấn đề toán học liên quan đến bài toán Tháp Hà Nội Nhiều bài toán của toán học và tin học thú vị xuất hiện trong trò chơi Tháp Hà Nội. Dưới đây liệt kê một vài vấn đề chính. 2.3.1 Đồ thị Hà Nội Các nhà toán học đã phát hiện ra rằng Tháp Hà Nội có cùng bản chất với bài toán tìm đường Hamilton (Hamilton Path) trên một hình giả phương cấp n ( n -Hypercube), một bài toán cũng rất nổi tiếng. Nhà toán học D.G. Poole đã phát hiện ra Lược đồ Hà Nội -một tam giác có các đỉnh tương ứng với các cách sắp xếp đĩa trong Tháp Hà Nội, từ đó tìm ra những liên hệ lý thú giữa Tam giác Pascal với Lược đồ Hà Nội. Liên hệ này đã được công bố trong một công trình mang một cái tên đầy liên tưởng: Pascal biết Hà Nội (Pascal knows Hanoi, [15]). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 20 Có thể biểu diễn trò chơi dưới dạng một đồ thị không có hướng đơn giản. Các nút chính là các phân bố của các đĩa và các cạnh chính là các chuyển động. Nhưng, thậm chí được thực hiện một cách khéo léo thuật toán của Dijkstra để tìm một (hoặc tất cả) các đường ngắn nhất chuyển đĩa từ một cọc này sang cọc khác trên máy tính nhanh nhất hiện nay, thuật toán này không cho một con đường hữu hiệu tính nghiệm của bài toán với số lượng đĩa lớn. Chương trình này đỏi hỏi nhiều thời gian và bộ nhớ hơn là có thể. Do đó, thậm chí có thuật toán, ta vẫn không thể biết cần bao nhiêu lần chuyển đĩa mà lời giải tối ưu đòi hỏi và có bao nhiêu lời giải tối ưu cho bài toán, thí dụ, với 1000 đĩa và 10 cọc. Rất nhiều nghiên cứu bài toán tháp Hà Nội với tên gọi Đồ thị Hà Nội. 2.3.1 Thuật toán giải trò chơi Tháp Hà Nội Trò chơi Tháp Hà Nội và các cải biên của nó đặt ra những câu hỏi khá thú vị: Tìm thuật toán tối ưu giải quyết trò chơi, đánh giá độ phức tạp của thuật toán,… Một thuật toán, có lẽ là quan trọng nhất, được trình bày trong luận văn này (Chương 3 và 4), đó là thuật toán Frame-Stewart và các cải biên của nó. 2.4 Bài toán Tháp Hà Nội trong y học và giáo dục Bài toán Tháp Hà Nội thường được dùng trong nghiên cứu tâm lý về cách giải quyết vấn đề (problem solving). Cũng có những biến thể khác của bài toán này gọi là Tháp Luân Đôn (Tower of London) dùng trong chuẩn đoán và điều trị thần kinh tâm lý đối với các chức năng thực hành. Những vấn đề này không được đề cập trong luận văn này Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 21 Chƣơng 2 TRÒ CHƠI THÁP HÀ NỘI §1 Trò chơi tháp Hà Nội và thuật giải đệ qui Luật chơi của trò chơi Tháp Hà Nội đã được qui định rõ trong tờ hướng dẫn thứ hai khi Trò chơi Tháp Hà Nội được phổ biến lần đầu tại Paris năm 1883 (xem Chương 1). Trong cuốn sách của mình, E. Lucas mô tả trò chơi gồm 8 đĩa ([12], trang 180-181). Dưới đây trình bày lời giải bài toán Tháp Hà Nội với ba cọc và số đĩa n bất kì. Bài toán 1 Có n đĩa kích thước nhỏ dần xếp chồng lên nhau trên một cọc (được gọi là cọc nguồn, cọc A), đĩa lớn ở dưới, đĩa nhỏ ở trên. Ngoài cọc nguồn còn có hai cọc trống khác, được gọi là cọc đích và cọc trung gian (cọc B và cọc C). Hãy chuyển các đĩa này từ cọc nguồn sang cọc đích (một trong hai cọc B hoặc C) tuân theo hai qui tắc sau: Qui tắc 1. Mỗi lần chỉ được chuyển một đĩa từ cọc này sang cọc khác và được dùng cọc thứ ba làm cọc trung chuyển. Qui tắc 2. Không được xếp đĩa lớn nằm trên đĩa nhỏ. Giải Trước tiên ta xét bài toán với 1, 2, 3 đĩa. Bài toán với 1 đĩa: chỉ cần 1 lần chuyển (Hình 1) Lần 1: Chuyển đĩa từ cọc A sang cọc C. Hình 1 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 22 Bài toán với 2 đĩa: cần 3 lần chuyển (Hình 2) Lần 1: Chuyển đĩa số 1 từ cọc A sang cọc B . Lần 2: Chuyển đĩa số 2 từ cọc A sang cọc C. Lần 3: Chuyển đĩa số 1 từ cọc B sang cọc C (lên trên đĩa số 2). Kết thúc. Hình 2 Bài toán với 3 đĩa: cần 7 lần chuyển (Hình 3) Hai đĩa đầu làm như trường hợp 2 đĩa ở trên (ba lần chuyển): Lần 1: Chuyển đĩa số 1 từ cọc A sang cọc C. Lần 2: Chuyển đĩa số 2 từ cọc A sang cọc B. Lần 3: Chuyển đĩa số 1 từ cọc C sang cọc B (lên trên đĩa số 2). Cọc C trống. Lần 4: Chuyển đĩa số 3 từ cọc A sang cọc C. Cọc A trống. Lại chuyển hai đĩa đầu từ cọc B sang cọc C (ba lần chuyển): Lần 5: Chuyển đĩa số 1 từ cọc B sang cọc A. Lần 6: Chuyển đĩa số 2 từ cọc B sang cọc C (chồng lên trên đĩa số 3). Lần 7: Chuyển đĩa số 1 từ cọc B sang cọc C (chồng lên đĩa số 2). Kết thúc. Hình 3 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 23 Bài toán với 4 đĩa: cần 15 lần chuyển (Hình 4) Với 4n  ta minh họa các bước chuyển đĩa như Hình 4 dưới đây. Dòng 1 cột 1 biểu thị cả bốn đĩa nằm trên cọc A. Hình 4 Trước tiên ta giải bài toán ba cọc (mất 7 lần chuyển): Lần 1 (dòng 2 cột 1): Chuyển đĩa trên cùng (số 1) từ cọc A sang cọc C. Lần 2 (dòng 3 cột 1): Chuyển đĩa số 2 từ cọc A sang cọc B. Lần 3 (dòng 4 cột 1): Chuyển đĩa số 1 từ cọc C sang cọc B (cọc C trống). Lần 4 (dòng 5 cột 1): Chuyển đĩa số 3 từ cọc A sang cọc B. Lần 5 (dòng 6 cột 1): Chuyển đĩa số 1 từ cọc C sang cọc A. Lần 6 (dòng 7 cột 1): Chuyển đĩa số 2 từ cọc C sang cọc B (cọc C trống). Lần 7 (dòng 8 cột 1): Chuyển đĩa số 1 từ cọc A sang cọc B. Như vậy, sau 7 lần chuyển, bài toán với 3 cọc và 3 đĩa đã giải xong. Lần 8 (dòng 1 cột 2): Chuyển đĩa số 4 từ cọc A sang cọc C. Tiếp theo lại giải bài toán ba cọc: Chuyển ba đĩa từ cọc B sang cọc C (mất thêm 7 lần chuyển): Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 24 Lần 9 (dòng 2 cột 2): Chuyển đĩa số 1 từ cọc B sang cọc C. Lần 10 (dòng 3 cột 2): Chuyển đĩa số 2 từ cọc B sang cọc A. Lần 11 (dòng 4 cột 2): Chuyển đĩa số 1 từ cọc C sang cọc A. Lần 12 (dòng 5 cột 2): Chuyển đĩa số 3 từ cọc B sang C (cọc B trống). Lần 13 (dòng 6 cột 2): Chuyển đĩa số 1 từ cọc A sang cọc B. Lần 14 (dòng 7 cột 2): Chuyển đĩa số 2 từ cọc A sang C (cọc A trống). Lần 15 (dòng 8 cột 2): Chuyển đĩa 1 từ cọc B sang cọc C (cọc B trống). Tổng cộng sau 15 lần chuyển các đĩa nằm trên cọc C. Từ các trường hợp riêng trên, ta đi tới thuật giải tổng quát cho bài toán Tháp Hà Nội với ba cọc và số đĩa n bất kì như sau. Thuật toán Trước tiên ta giải bài toán Tháp Hà Nội cho ba đĩa: Chuyển đĩa số 1 từ cọc A sang cọc B; chuyển đĩa số 2 sang cọc C; chuyển đĩa số 1 từ cọc B sang cọc C. Khi ấy đĩa số 1 nằm trên đĩa số 2. Vậy ta hiện đã có hai đĩa nằm trên cọc C, cọc B hiện thời trống. Chuyển đĩa số 3 từ cọc A sang cọc B. Lặp lại ba bước trên để giải bài toán cho hai đĩa: chuyển đĩa số 1 và đĩa số 2 cho nằm lên trên đĩa số 3 trên cọc B. Tiếp tục làm như vậy cho bốn, năm,…đĩa. Mỗi lần dựng xong tháp từ đĩa thứ k đến đĩa thứ 1 (trên cọc B hoặc cọc C, một trong hai cọc đó trống), ta chuyển đĩa thứ 1k  từ cọc A sang cọc trống (cọc C hoặc cọc B), rồi lại di chuyển tháp đã dựng lên đĩa thứ 1k  để được tháp với 1k  đĩa. Như vậy, khi đã xây dựng xong tháp thứ k thì ta cũng dễ dàng xây dựng được tháp thứ 1k  sau khi chuyển đĩa thứ 1k  sang cọc trống. Phương pháp trên được gọi là thuật giải đệ qui: Để tiến hành giải bài toán với 1n  đĩa, ta áp dụng lại thuật giải bài toán với n đĩa. Toàn bộ quá trình là một số hữu hạn các bước, vì đến một lúc nào đó thuật giải sẽ được áp dụng cho 1n  . Bước này chỉ đơn giản là chuyển một đĩa duy nhất từ cọc A sang cọc B. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 25 Thuật giải đệ qui bài toán tháp Hà Nội có thể phát biểu nhƣ sau. Nếu 1n  hoặc 2n  thì bài toán giải được ngay. Giả sử đã biết cách giải bài toán với 1n  đĩa. Giải bài toán cho n đĩa như sau: Chuyển 1n  đĩa trên cùng từ cọc A sang cọc B (theo giả thiết đã biết cách giải). Chuyển đĩa thứ n (dưới cùng trên cọc A) từ cọc A sang cọc C (Bài toán 1 đĩa). Chuyển 1n  đĩa từ cọc B sang cọc C (theo giả thiết đã biết cách giải). Như vậy, lời giải bài toán rất đơn giản: giải bài toán n đĩa được đưa về bài toán 1n  đĩa và bài toán một đĩa. Thuật giải đệ qui (có quan hệ mật thiết với phép qui nạp và công thức truy hồi trong toán học) được áp dụng để giải rất nhiều bài toán. Thí dụ, bài toán Josephus; Bài toán tính số Fibonacci;… Kí hiệu ( )L n là số lần chuyển đĩa tối ưu trong bài toán tháp Hà Nội với n đĩa và ba cọc. Khi ấy, để chuyển n đĩa từ cọc A sang cọc C, trước tiên ta phải chuyển 1n  đĩa trên cùng (các đĩa nhỏ) từ cọc A sang cọc B, sau đó chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng, lại chuyển 1n  đĩa từ cọc B sang cọc C. Ta có: (1) 1L  ; (2) 3L  ; ( ) ( 1) (1) ( 1) 2 ( 1) 1L n L n L L n L n        . Theo qui nạp, ta dễ dàng chứng minh được ( ) 2 1nL n   . Một điều thú vị là dãy ( ) 2 1nL n   chính là dãy số Merssen. Thuật toán đệ qui giải bài toán Tháp Hà Nội nêu trên là thuật toán tối ưu (số lần chuyển đĩa ít nhất). Theo công thức trên, nó là thuật toán có thời gian mũ. Giả sử mỗi lần chuyển 1 đĩa hết thời gian 1 giây. Nếu có 64 đĩa thì thời gian chuyển hết 64 đĩa là 642 1 18446744073703551615  giây  50 tỉ năm. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 26 Nếu sử dụng máy tính thực hiện chương trình đệ qui với tốc độ 1 triệu phép toán/giây thì thời gian chạy máy là:  642 1 :1000000 50 000  năm. Như vậy bài toán Tháp Hà Nội, mặc dù có thuật giải đơn giản và tối ưu, nhưng không giải được trong thời gian thực. Ta có thể minh họa bài toán theo cách khác như sau. Cho ba cột và n đĩa. Kí hiệu dãy  i kS a , 1,...,i n là chỉ số của các đĩa cần phải chuyển tại bước thứ k . Dãy  i kS a này được xây dựng theo thuật giải đệ qui đơn giản bắt đầu với  1 1S  cho một đĩa và theo công thức truy hồi  1 1, ,n n nS S n S  . Bảng dưới đây chỉ ra cách xây dựng dãy nS cho các giá trị 1,2,3,4n  . n nS 1 1 2 1,2,1 3 1,2,1,3,1,2,1 4 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 Ta thấy dãy số nS có tính chất đối xứng và lồng nhau. Số ở giữa bao giờ cũng là n , chính là số đĩa. Dãy 1nS  lại có số ở giữa chính là 1n  . Các số trong dãy nS (nhận giá trị từ 1 đến n ) tương ứng với chỉ số của đĩa được chuyển. §2 Giải bài toán tháp Hà Nội bằng biểu diễn trong hệ đếm cơ số 2 Bằng cách chia cho 2, một số tự nhiên bất kì có thể biểu diễn dưới dạng tổng các lũy thừa của 2 với các hệ số bằng 1 hoặc 0. Thí dụ, 10 9 8 7 6 4 3 10 9 8 7 6 5 4 3 2 1 0 2010 2 2 2 2 2 2 2 2 1.2 1.2 1.2 1.2 1.2 0.2 1.2 1.2 0.2 1.2 0.2 .                   Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 27 Như vậy, nếu chọn 2 làm cơ số trong hệ đếm cơ số 2 thì mọi số tự nhiên đều có thể biểu diễn dưới dạng hệ đếm cơ số 2 với các hệ số 1 và 0. Các hệ số trong phân tích số đã cho dưới dạng lũy thừa của 2 được gọi là các chữ số của nó và số đã cho được biểu diễn trong hệ đếm theo vị trí, tương tự như trong hệ đếm cơ số 10. Thí dụ (chỉ số dưới biểu thị cơ số): 10 22010 =11111011010 11111011010 . Sau này, để cho gọn, ta sẽ không viết chỉ số cơ số 2 dưới số đã cho. Ta có thể sử dụng hệ đếm cơ số 2 để giải bài toán Tháp Hà Nội cho ba cọc với n đĩa như sau. Để dễ hiểu, trước tiên ta xem xét trường hợp bài toán Tháp Hà Nội với ba cọc và hai, ba, bốn đĩa hoặc năm đĩa. Giải bài toán Tháp Hà Nội với hai đĩa nhờ hệ đếm cơ số 2 Bước 0: Hai đĩa ở cọc A, kí hiệu là   2 00 . Bước 1: Chuyển đĩa số 1 từ cọc A sang cọc trống B, kí hiệu là   2 01 . Chữ số 1 cuối cùng biểu thị đĩa trên cùng đã được chuyển (   10201 1 ). Bước 2: Chuyển đĩa số 2 từ cọc A sang cọc trống C, kí hiệu là   2 10 . Chữ số 1 thứ hai biểu thị đĩa thứ hai đã được chuyển (   10210 2 ). Hai chữ số 1 và 0 biểu thị hai đĩa ở hai cọc khác nhau. Bước 3: Chuyển đĩa số 1 từ cọc B sang cọc C, kí hiệu là   2 11 . Chữ số 1 thứ hai biểu thị đĩa thứ hai đã được chuyển. Hai chữ số 1 và 1 biểu thị hai đĩa ở trên cùng một cọc (đĩa thứ hai chồng lên đĩa thứ nhất ,   10211 3 ). Giải bài toán Tháp Hà Nội với ba đĩa nhờ hệ đếm cơ số 2 Bước 0: Ba đĩa ở cọc A, kí hiệu là   2 000 . Bước 1: Chuyển đĩa số 1 từ cọc A sang cọc trống C, kí hiệu là   102001 1 . Chữ số 1 ở vị trí thứ nhất (từ bên phải) biểu thị đĩa trên cùng đã được chuyển. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 28 Bước 2: Chuyển đĩa số 2 từ cọc A sang cọc trống B, kí hiệu là   2 010 . Chữ số 1 ở vị trí thứ hai biểu thị đĩa thứ hai đã được chuyển (   10210 2 ). Ba chữ số 0, 1, 0 biểu thị ba đĩa ở ba cọc khác nhau. Bước 3: Chuyển đĩa số 1 từ cọc C sang cọc B, kí hiệu là   2 011 (   102011 3 ). Chữ số 1 ở vị trí thứ nhất (khác với số 0 trong   2 010 ở bước 2) biểu thị đĩa số 1 đã được chuyển. Ba chữ số 0, 1, 1 biểu thị hai đĩa nhỏ ở trên cùng cọc C (đĩa thứ hai chồng lên đĩa thứ nhất), đĩa lớn ở cọc khác (cọc A). Cọc C trống. Bước 4: Chuyển đĩa số 3 từ cọc A sang cọc C, kí hiệu là   2 100 (   102100 4 ). Chữ số 1 thứ ba biểu thị đĩa số 3 đã được chuyển. Ba chữ số 1, 0, 0 biểu thị hai đĩa nhỏ ở trên cùng một cọc B (đĩa thứ hai chồng lên đĩa thứ nhất) và không chuyển, đĩa lớn ở cọc khác (cọc C). Cọc A trống. Bước 5: Chuyển đĩa số 1 từ cọc B sang cọc A, kí hiệu là   2 101 (   102101 5 ). Chữ số 1 thứ ba (khác số 0 trong bước 4) biểu thị đĩa số 3 đã được chuyển. Ba chữ số 1, 0, 1 khác nhau biểu thị ba đĩa ở ba cọc khác nhau. Bước 6: Chuyển đĩa số 2 từ cọc B sang cọc C, kí hiệu là   2 110 (   102110 6 ). Chữ số 1 thứ n (khác số 0 trong bước 4) biểu thị đĩa số 3 đã được chuyển. Ba chữ số 1, 0, 1 khác nhau biểu thị ba đĩa ở ba cọc khác nhau. Lần 6: Chuyển đĩa 2 từ cọc B sang cọc C (chồng lên trên đĩa 3). Lần 7: Chuyển đĩa 1 từ cọc B sang cọc C (chồng lên đĩa 2). Kết thúc. Giải bài toán Tháp Hà Nội với bốn đĩa nhờ hệ đếm cơ số 2 Số lần chuyển cần thiết trong bài toán ba cọc với bốn đĩa là 42 1 15  . Kí hiệu các cọc là cọc A (cọc nguồn chứa 4 đĩa), cọc B và cọc C, các đĩa là 1, 2, 3, 4 theo thứ tự từ nhỏ đến lớn. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 29 Biểu thị vi trí ban đầu, khi tất cả bốn đĩa ở cọc A là số   2 0000 có bốn chữ số 0 . Bước 1: Chuyển đĩa số 1 từ cọc A sang cọc trống C, kí hiệu là   2 0001 . Số 1 ở vị trí cuối cùng biểu thị đĩa số 1 được chuyển (sang cọc trống C). Bước 2: Chuyển đĩa số 2 từ cọc A sang cọc trống B, kí hiệu bởi   2 0010 . Số 1 ở vị trí thứ hai (tính từ bên phải) biểu thị đĩa số 2 được chuyển (sang cọc trống B). Hai số 10 ở vị trí cuối cùng biểu thị hai đĩa được đặt lên hai cọc khác nhau. Bước 3: Chuyển đĩa số 1 từ cọc C sang cọc B, kí hiệu bởi   2 0011 . Cọc C trống. Số   2 0010 ở bước trên trở thành số   2 0011 , biểu thị đĩa số 1 đã được chuyển. Hai số 11 cuối cùng biểu thị đĩa 1 được đặt chồng lên đĩa số 2 trên cọc B. Bước 4: Chuyển đĩa số 3 từ cọc A sang cọc trống C, kí hiệu bởi   2 0100 . Cọc A trống. Số 1 ở vị trí thứ ba biểu thị đĩa số 3 đã được chuyển. Ba số 100 ở vị trí cuối cùng biểu thị đĩa số 3 không nằm trên cùng cọc với hai đĩa đầu tiên. Bước 5: Đưa đĩa số 1 từ cọc B sang cọc A, kí hiệu bởi   2 0101 . Từ   2 0100 đổi thành   2 0101 biểu thị đĩa số 1 đã được chuyển. Ba số 101 cuối cùng biểu thị ba đĩa ở trên ba cọc khác nhau. Bước 6: Đưa đĩa số 2 từ cọc B sang cọc C, kí hiệu bởi   2 0110 . Ba số 110 ở vị trí cuối cùng biểu thị hai đĩa số ba và số 2 trên cùng một cọc. Bước 7: Đưa đĩa số 1 từ cọc A sang cọc C, kí hiệu bởi   2 0111 . Ba số 111 ở vị trí cuối cùng biểu thị ba đĩa trên cùng một cọc (cọc C). Như vậy ta đã giải xong bài toán ba đĩa. Bước 8: Đưa đĩa số 4 từ cọc A sang cọc B, kí hiệu bởi   2 1000 . Cọc A trống. Số 1000 biểu thị đĩa số 4 không trên cùng cọc với ba đĩa nhỏ. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 30 Bước 9: Đưa đĩa số 1 từ cọc C sang cọc B, kí hiệu bởi   2 1001 . Số 1001 biểu thị đĩa số 1 và đĩa số 4 trên cùng một cọc. Bước 10: Đưa đĩa số 2 từ cọc C sang cọc A, kí hiệu bởi   2 1010 . Số 1010 biểu thị đĩa số 4 không trên cùng cọc với đĩa số 2. Bước 11: Đưa đĩa số 1 từ cọc B sang cọc A, kí hiệu bởi   2 1011 . Cọc B trống. Số 1011 biểu thị đĩa số 1 không trên cọc với đĩa số 2. Bước 12: Đưa đĩa số 2 từ cọc C sang cọc A, kí hiệu bởi   2 0110 . Ba số 110 ở vị trí cuối cùng biểu thị đĩa số 1 không trên cùngcọc với đĩa số 3. Bước 13: Đưa đĩa số 2 từ cọc C sang cọc A, kí hiệu bởi   2 0110 . Ba số 110 ở vị trí cuối cùng biểu thị đĩa số 1 không trên cùngcọc với đĩa số 3. Bước 14: Đưa đĩa số 2 từ cọc C sang cọc A, kí hiệu bởi   2 0110 . Ba số 110 ở vị trí cuối cùng biểu thị đĩa số 1 không trên cùngcọc với đĩa số 3. Bước 15: Đưa đĩa số 2 từ cọc C sang cọc A, kí hiệu bởi   2 0110 . Ba số 110 ở vị trí cuối cùng biểu thị đĩa số 1 không trên cùngcọc với đĩa số 3. Bƣớc Cơ số 2 Giải thích 1 0001 Đưa đĩa số 1 từ cọc A sang cọc trống B. 2 0010 Đưa đĩa 2 từ cọc A sang cọc trống C. 3 0011 Đưa đĩa 1 từ cọc B lên trên đĩa 2 của C, cọc B trống. 4 0100 Đưa đĩa 3 từ cọc A lên cọc trống B. 5 0101 Đĩa 1 từ C sang A (KHÔNG chồng lên đĩa 3 của B) 6 0110 Đĩa 2 từ C lên trên đĩa 3 của cọc B (cọc C trống). 7 0111 Đưa đĩa 1 từ cọc A lên trên đĩa 2 của cọc B. 8 1000 Đưa đĩa 4 từ cọc A sang cọc trống C. 9 1001 Đĩa 1 từ cọc B lên trên đĩa 4 của cọc C. 10 1010 Đĩa 2 từ B sang A (KHÔNG chồng lên đĩa 4 của C). 11 1011 Đĩa 1 từ cọc C lên trên đĩa 2 của cọc A. 12 1100 Đĩa 3 từ cọc B lên trên đĩa 4 của C (cọc B trống). 13 1101 Đĩa 1 từ A sang B (KHÔNG chồng lên đĩa 3 của C). 14 1110 Đưa đĩa 2 từ cọc A lên trên đĩa 3 của cọc C. 15 1111 Đĩa 1 từ cọc B lên trên đĩa 2 của C (cọc B trống). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 31 Giải bài toán Tháp Hà Nội với năm đĩa nhờ hệ đếm cơ số 2 Số lần chuyển cần thiết trong bài toán ba cọc với năm đĩa 52 1 31  . Kí hiệu các cọc là cọc A (cọc nguồn chứa 5 đĩa), cọc B và cọc C, các đĩa là 1, 2, 3, 4, 5 theo thứ tự từ nhỏ đến lớn. Bƣớc cơ số 2 Giải thích 1 00001 Đưa đĩa số 1 từ cọc A sang cọc trống B. 2 00010 Đưa đĩa 2 từ cọc A sang cọc trống C. 3 00011 Đưa đĩa 1 từ cọc B lên trên đĩa 2 của C, cọc B trống. 4 00100 Đưa đĩa 3 từ cọc A lên cọc trống B. 5 00101 Đĩa 1 từ C sang A (KHÔNG chồng lên đĩa 3 của B) 6 00110 Đĩa 2 từ C lên trên đĩa 3 của cọc B (cọc C trống). 7 00111 Đưa đĩa 1 từ cọc A lên trên đĩa 2 của cọc B. 8 01000 Đưa đĩa 4 từ cọc A sang cọc trống C. 9 01001 Đĩa 1 từ cọc B lên trên đĩa 4 của cọc C. 10 01010 Đĩa 2 từ B sang A (KHÔNG chồng lên đĩa 4 của C). 11 01011 Đĩa 1 từ cọc C lên trên đĩa 2 của cọc A. 12 01100 Đĩa 3 từ cọc B lên trên đĩa 4 của C (cọc B trống). 13 01101 Đĩa 1 từ A sang B (KHÔNG chồng lên đĩa 3 của C). 14 01110 Đưa đĩa 2 từ cọc A lên trên đĩa 3 của cọc C. 15 01111 Đĩa 1 từ cọc B lên trên đĩa 2 của C (cọc B trống). 16 10000 Đưa đĩa 5 từ cọc A sang cọc trống B (cọc A trống). 17 10001 Đĩa 1 từ cọc C sang A (KHÔNG chồng lên đĩa 5). 18 10010 Đĩa 2 từ cọc C lên trên đĩa 5 của cọc B. 19 10011 Đĩa 1 từ cọc A lên trên đĩa 2 của B (cọc A trống). 20 10100 Đĩa 3 từ cọc C sang A (KHÔNG chồng lên đĩa 5). 21 10101 Đĩa 1 từ cọc B sang C (KHÔNG chồng lên đĩa 3). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 32 22 10110 Đưa đĩa 2 từ cọc B lên trên đĩa 3 của cọc A. 23 10111 Đưa đĩa 1 từ cọc C lên trên đĩa 2 của cọc A. 24 11000 Đĩa 4 từ cọc C lên trên đĩa 5 của cọc B (C trống). 25 11001 Đưa đĩa 1 từ cọc A lên trên đĩa 4 của cọc B. 26 11010 Đĩa 2 từ cọc A sang cọc C (KHÔNG chồng lên 4). 27 11011 Đưa đĩa 1 từ cọc B lên trên đĩa 2 của cọc C. 28 11100 Đưa đĩa 3 từ cọc A lên trên đĩa 4 của B (A trống). 29 11101 Đưa đĩa 1 từ cọc C sang A (KHÔNG chồng lên 3). 30 11110 Đưa đĩa 2 từ cọc C lên trên đĩa 3 của cọc B. 31 11111 Đưa đĩa 1 từ cọc A lên trên đĩa 2 của cọc B. Kết thúc Kết luận Các ví dụ trên (bài toán ba cọc với bốn hoặc năm đĩa) cho thấy: Các vị trí đĩa có thể hoàn toàn xác định được trực tiếp từ biểu diễn nhị phân của số thứ tự di chuyển (viết trong hệ đếm cơ số 2 với một chữ số cho mỗi đĩa), trong đó các dãy 1 và các dãy 0 tượng trưng cho các dãy các đĩa liền nhau trên cùng một cọc, và mỗi khi chữ số có thay đổi thì đĩa kế tiếp sẽ dời sang trái hay phải một cọc (hay chuyển sang cọc ngoài cùng phía đối diện). Ta có qui tắc sau. Dãy bit (dãy chữ số trong cơ số 2) được đọc từ trái sang phải, và mỗi bit (mỗi chữ số) có thể được sử dụng để xác định vị trí của đĩa tương ứng. Bit với cùng giá trị như bước trước có nghĩa là đĩa tương ứng được xếp chồng lên đỉnh của đĩa trước trên cùng một cọc. Bit với giá trị khác trước nghĩa là đĩa tương ứng có vị trí bên trái hoặc bên phải của đĩa trước. Để xác định vị trí bên phải hay bên trái ta phải theo qui tắc sau: 1) Giả thiết cọc đích nằm bên trái và cọc nguồn nằm bên phải. 2) Cũng giả thiết "wrapping" (bao bọc): cọc phải được tính như là cọc “trái” của cọc trái và ngược lại. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 33 3) Giả sử k là số đĩa lớn nhất nằm trên cùng một cọc như là đĩa đầu tiên lớn nhất của nó và thêm 1 nếu đĩa lớn nhất trên cọc trái. Nếu n chẵn, đĩa sẽ được đặt trên một cọc bên trái, nếu n lẻ, đĩa được đặt lên một cọc bên phải. Chữ số ở đầu đại diện cho đĩa lớn nhất và nếu là chữ số 0 thì có nghĩa là đĩa lớn nhất không dời khỏi cọc xuất phát và ngược lại. Chữ số 1 từ bên phải của số trong cơ số 2 biểu thị đĩa đã được chuyển. Nếu không có chữ số 1 nào khác trong số đã cho trong cơ số 2, tức là số có dạng 20...01 , thì nghĩa là đĩa đã được chuyển từ cọc A sang cọc trống. Chữ số 1 thứ hai từ bên phải biểu thị vị trí của cọc mà đĩa được chuyển đến. Nếu không có đĩa nào hoặc có một số chẵn các chữ số 0 giữa hai chữ số 1 (hai chữ số 1 đầu tiên từ bên phải), thì đĩa được đặt lên trên đĩa to hơn nó. Nếu số chữ số 0 giữa hai chữ số 1 là lẻ thì nghĩa là đĩa đang chuyển KHÔNG đặt lên trên đĩa to hơn (mà đặt ở cọc khác). Các chữ số 1 và 0 luân phiên bên dưới các chữ số của một bước chuyển cho phép biết được di chuyển theo một chiều khi nó hợp với chữ số của bước chuyển tại nơi chữ số thay đổi và theo chiều kia khi nó không hợp. Thí dụ, với số đĩa là 8: Bước 0:   2 00000000 : Đĩa lớn nhất là 0, do đó nó nằm trên cọc trái (cọc nguồn). Mọi đĩa khác cũng là 0, do đó chúng được đặt lên trên đĩa lớn nhất. Và mọi đĩa đều nằm trên trên cọc nguồn. Bước 211011000 : Đĩa lớn nhất là 1, do đó nó nằm trên cọc phải (cọc đích). Đĩa thứ hai cũng là 1, do đó nó nằm trên đĩa lớn nhất, trên cọc phải. Đĩa thứ ba là 0, do đó nó nằm trên cọc khác. Bởi vì 3 là số lẻ nên nó nằm trên một cọc phía bên phải, nghĩa là trên cọc trái. Đĩa thứ tư là 1 nên nó nằm trên cọc khác. Vì 4 là chẵn nên nó nằm trên một cọc về bên trái, nghĩa là cọc phải. Đĩa thứ năm cũng là 1, do đó nó nằm bên trên đĩa thứ tư, trên cọc phải. Đĩa thứ 6 là 0, do đó nó nằm trên cọc khác. Do 6 là chẵn nên đĩa nằm trên cọc về bên trái, nghĩa là cọc giữa. Đĩa thứ 7 và đĩa thứ 8 cũng là 0, do đó nó nằm trên đĩa số 6, trên cọc giữa. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 34 Bước 8 22 1 11111111  : Đĩa lớn nhất là 1, do đó nó nằm trên cọc phải (cọc đích). Mọi đĩa khác cũng là 1, do đó chúng được đặt lên trên đĩa lớn nhất. Vậy mọi đĩa nằm trên cọc đích và trò chơi kết thúc. §3 Đồ thị Hà Nội 3.1 Đồ thị Hà Nội Trò chơi Tháp Hà Nội có thể biểu diễn như một đồ thị không có hướng. Các đỉnh biểu thị phân bố của các đĩa và các cạnh biểu thị chuyển động của các đĩa. Với một đĩa, đồ thị là một tam giác: Với hai đĩa, đồ thị là ba tam giác được sắp xếp thành một tam giác lớn: Các nút tại các đỉnh của tam giác phía ngoài cùng biểu thị các phân bố với mọi đĩa trên cùng một cọc. Với 1n  đĩa, ta lấy đồ thị của n đĩa và thay mỗi tam giác nhỏ với đồ thị của hai đĩa. Đồ thị cho ba đĩa có dạng: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 35 1) Gọi các cọc là A, B, C. 2) Liệt kê các vị trí của các đĩa từ trái sang phải theo chiều tăng của kích thước. Các cạnh của các tam giác ngoài biên biểu thị con đường ngắn nhất để chuyển tháp từ một cọc này sang cọc khác. Cạnh ở giữa của các biên của tam giác lớn nhất biểu thị chuyển động của đĩa lớn nhất. Cạnh ở giữa của các biên của mỗi tam giác nhỏ hơn tiếp theo biểu thị chuyển động của mỗi đĩa nhỏ hơn tiếp theo. Các cạnh của tam giác nhỏ nhất biểu thị chuyển động của đĩa nhỏ nhất. Đồ thị của trò chơi tháp Hà Nội có liên quan mật thiết với tam giác Sierpinski (Sierpiński Triangle) hay còn được gọi là thảm Sierpinski. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 36 Đồ thị của trò chơi với n đĩa sẽ có 3n nút. Mỗi nút có ba cạnh đi tới nút khác, ngoại trừ ba nút ở góc chỉ có hai cạnh. Luôn luôn có thể chuyển đĩa nhỏ nhất sang một trong hai cọc khác. Và có thể chuyển một đĩa giữa hai cọc này ngoại trừ trường hợp khi tất cả các đĩa nằm trên một cọc. Các nút góc biểu thị ba trường hợp, khi mọi đĩa nằm trên một cọc. Biểu đồ cho n đĩa nhận được từ biểu đồ cho 1n  đĩa bằng cách copy ba lần-mỗi copy biểu thị mọi trạng thái và chuyển động của các đĩa nhỏ hơn cho một vị trí riêng của một đĩa mới lớn hơn và cùng với chúng tại các góc với ba cạnh mới biểu thị chỉ có ba khả năng chuyển đĩa lớn nhất. Do đó kết quả sẽ có 13n nút và vẫn có ba góc với hai cạnh. Khi số đĩa được thêm vào, đồ thị biểu diễn trò chơi sẽ tạo thành một hình Fractal, thảm Sierpinski. Rõ ràng rằng phần lớn các vị trí trong trò chơi sẽ không bao giờ đạt được nếu sử dụng lời giải ngắn nhất. Thật vậy, nếu các vị thầy tu trong truyền thuyết sử dụng lời giải dài nhất có thể (không trở lại vị trí cũ nào) thì cần 643 1 lần chuyển, nhiều hơn 2310 năm. 3.2 Bài toán Tháp Hà Nội và đƣờng Hamilton Đường Hamilton khép kín cho ba đĩa là: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 37 Đồ thị chỉ ra rằng: • Từ mỗi phân bố bất kì của các đĩa, tồn tại một con đường ngắn nhất chuyển mọi đĩa từ một trong ba cọc sang cọc khác. • Giữa mỗi cặp phân bố bất kì tồn tại một hoặc hai đường ngắn nhất khác nhau. • Từ mỗi phân bố bất kì của các đĩa, tồn tại một hoặc hai đường dài nhất không tự cắt chuyển mọi đĩa tới một trong ba cọc. • Giữa mọi cặp của các phân bố bất kì của các đĩa tồn tại một hoặc hai đường dài nhất không tự cắt. • Gọi nN là số các đường không tự cắt để chuyển tháp n đĩa từ cọc này sang cọc khác. Khi ấy: 1 2N  ; 2 3 1n n nN N N   . Thí dụ, 795 8 1.5656 10N   . Đồ thị nH tương ứng với các chuyển động được phép trong bài toán tháp Hà Nội. Hình trên chỉ ra một số đồ thị Hà Nội với 1,2,3,4n  . Đồ thị Hà Nội có thể xây dựng bằng cách chọn các đỉnh làm các hệ số nhị thức lẻ của tam giác Pascan được tính trên các số nguyên từ 0 đến 2 1n  và vẽ các đỉnh khi các hệ số là kề nhau theo đường chéo hoặc theo chiều ngang (xem Pool, 1994, [15]). Đồ thị nH có 3n đỉnh và  3 3 1 2 n  cạnh. Mỗi đồ thị Hà Nội có duy nhất một đường Hamilton (tương ứng, mỗi đồ thị Hà Nội có chính xác hai đường tròn Hamilton có hướng khác nhau). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 38 §4 Giải bài toán Tháp Hà Nội trên máy tính Code (mã) thể hiện thuật giải đệ qui bài toán Tháp Hà Nội: def Hanoi(n, A, C, B): if n == 1: print 'Move the plate from', A, 'to', C else: Hanoi(n - 1, A, B, C) print 'Move the plate from', A, 'to', C Hanoi(n - 1, B, C, A) Thuật giải đệ qui bài toán Tháp Hà Nội trên ngôn ngữ Pascal: VAR n: Integer; Procedure chuyen(sodia: Integer; CotNguon: Char; CotDich: Char; CotTG: Char); Begin If sodia>0 then begin chuyen(sodia-1, CotNguon, CotTG, CotDich); Writeln(CotNguon,'->',CotDich); { Dia lon nhat hien tai } chuyen(sodia-1, CotTG, CotDich, CotNguon) End; End; BEGIN Write('Hay nhap so dia: '); Readln(n); chuyen(n,'A','C','B');//Thực hiện chuyển từ cột A sang cột C với cột B làm trung gian Readln; END. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 39 Chƣơng 3 BÀI TOÁN THÁP HÀ NỘI VỚI BỐN CỌC (Trò chơi Reve-The Reve’s Puzzle) §1 Trò chơi Tháp Hà Nội với bốn cọc 1.1 Trò chơi Tháp Hà Nội với bốn cọc Trong Chương 2 chúng ta đã giải bài toán Tháp Hà Nội với ba cọc và n đĩa. Nó có thể giải được dễ dàng theo thuật giải đệ qui. Hơn nữa, có thể biết chính xác số lần chuyển tối ưu cho bài toán với n đĩa là 2 1n  . Như vậy, một bài toán với thuật giải đơn giản và tối ưu cũng có thể có độ phức tạp tính toán lớn (thời gian mũ), do đó có thể không giải được trong thời gian thực tế. Một mở rộng tự nhiên của trò chơi Tháp Hà Nội là trò chơi Tháp Hà Nội với bốn hoặc nhiều cọc (bài toán Tháp Hà Nội tổng quát). Như là sự tiếp nối của chương trước và chuẩn bị cho chương sau, chương này nghiên cứu bài toán Tháp Hà Nội cho bốn cọc. Bài toán này lần đầu tiên được Dudeney (1902) đặt ra và gọi tên là The Reve’s Puzzle (xem [7]). Gần đây, nhiều kết quả thú vị cũng đã được phát hiện cho bài toán này, các kết quả này là cơ sở để phát triển nghiên cứu bài toán Tháp Hà Nội tổng quát, vì vậy nó xứng đáng được xem xét tỉ mỉ trong một chương riêng, mặc dù, để thuận tiện, nhiều kết quả trong chương này cũng được trình bày cho bài toán nhiều cọc . Bài toán 2 (Bài toán Tháp Hà Nội với bốn cọc) Có bốn cọc được đánh số 1P , 2P , 3P , 4P . Cọc 1P được gọi là cọc nguồn. Ban đầu cọc nguồn chứa n đĩa có lỗ ở giữa và kích thước to Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 40 nhỏ khác nhau được xếp theo thứ tự “đĩa to ở dưới, đĩa nhỏ ở trên” . Bài toán đặt ra là phải chuyển tất cả n đĩa từ cọc nguồn sang một trong các cọc 2P , 3P , 4P , sắp xếp cũng theo thứ tự “đĩa to ở dưới, đĩa nhỏ ở trên”. Mỗi lần chỉ được chuyển một đĩa (trên cùng của cọc nào đó) từ cọc này sang cọc khác. Khi chuyển có thể sử dụng tất cả các cọc để đặt tạm thời các đĩa. Cọc cuối cùng chứa các đĩa theo thứ tự như trên cọc nguồn được gọi là cọc đích. Các cọc còn lại được gọi là cọc trung gian. Theo một số tài liệu, chính tác giả của bài toán Tháp Hà Nội, E. Lucas cũng là người đầu tiên xét bài toán với nhiều cọc. Năm 1889 Ông đã xét bài toán năm cọc và sắp xếp đĩa theo bốn màu khác nhau. Dudeney đã viết về bài toán Tháp Hà Nội với bốn cọc từ năm 1902. Trong hai trang đầu tiên của cuốn sách nổi tiếng của Ông The Canterbury Puzzle (xuất bản năm 1907 tại London và năm 1908 tại New York), Ông xét trò chơi với số cọc là 4 và số đĩa là 8, 10 hoặc 21, chỉ có khác là Ông đã thay các đĩa bằng các quân cờ (xem [7]) và được Ông gọi là Reve's puzzle. Trong phần lời giải (trang 131- 132), Dudeney đã khẳng định (không chứng minh) rằng số lần chuyển cần thiết tương ứng với 8, 10 hoặc 21 đĩa là 33, 49 hoặc 321. Hơn nữa, Ông còn xét trường hợp với số đĩa là số tam giác. Giả sử ( 1) 2 k k k t   là số tam giác thứ k và giả sử 4( )H n là số lần chuyển tối thiểu cần thiết để chuyển xong n đĩa. Dudeney tuyên bố rằng    4 4 12 2 1 k k kH t H t    ,  4 1 1H  . Từ đây ta có  4 3 5H  ;  4 6 17H  ,  4 10 49H  ,… Dudeney không cho một thuật toán nào cho phép tìm ra các số này, và cũng không có một gợi ý nào cho trường hợp số đĩa không phải là số tam giác, thí dụ như 8n  . Bài toán tổng quát với 3p  cọc, p là số tự nhiên bất kì với số đĩa n bất kì được B. M. Stewart đề xuất năm 1939 (xem [17]). Lời giải của bài toán này đã được Stewart [18] và Frame [9] trình bày đồng thời trong năm 1941. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 41 Bài toán tháp Hà Nội với bốn cọc được nhiều tác giả quan tâm (xem tài liệu đầy đủ trong [5]), Các thuật toán của Stewart và Frame cùng với một số thuật toán cải biên khác đã được chứng minh là tương đương (xem [11]). Vì vậy người ta thường gọi thuật toán của hai ông hoặc các thuật toán cải biên tương tự là thuật toán Frame-Stewart. Thuật toán Stewart-Frame cho bài toán Tháp Hà Nội tổng quát sẽ được nghiên cứu kĩ ở Chương 4. Dưới đây trình bày thuật toán Frame-Stewart cho bài toán bốn cọc (do Stewart đề xuất 1941). 1.2 Thuật toán Frame-Stewart (1941) cho bài toán Tháp Hà Nội với bốn cọc Bƣớc 0 Đánh số cọc là 1P , 2P , 3P , 4P . Mục đích của chúng ta là chuyển tất cả các đĩa từ cọc 1P sang cọc 4P , với qui tắc là mỗi lần chỉ chuyển một đĩa, và đĩa nhỏ không bao giờ nằm dưới đĩa lớn. Bƣớc 1 Chuyển l đĩa nhỏ nhất ( 0 l n  ) từ cọc 1P sang cọc 2P , trong quá trình chuyển có quyền sử dụng tất cả bốn cọc. Kí hiệu số lần chuyển tối ưu là 4( )S l . Bƣớc 2 Chuyển n l đĩa lớn nhất (còn lại) từ cọc 1P sang cọc 4P , không sử dụng cọc 2P (vì cọc 2P đang chứa l đĩa nhỏ). Nói cách khác, chuyển n l đĩa này bằng cách sử dụng phương pháp tối ưu giải bài toán ba cọc trong Chương 2, số lần chuyển tối ưu n l đĩa từ cọc 1P sang cọc 4P , không sử dụng cọc 2P là 2 1n l  . Bƣớc 3 Chuyển l đĩa nhỏ nhất từ cọc 2P sang cọc 4P , sử dụng tất cả bốn cọc. Như vậy, gọi 4( )S n là số lần chuyển tối ưu n đĩa trong bài toán Tháp Hà Nội với bốn cọc theo thuật toán Frame-Stewart thì với mỗi l , số lần chuyển tối ưu n đĩa từ cọc 1P sang cọc 4P phụ thuộc vào l và bằng 42 ( ) 2 1 n lS l   . Số lần chuyển tối ưu n đĩa trong bài toán Tháp Hà Nội với bốn cọc theo thuật toán Stewart là  4 4 4 0 ( ) 2 ( ) 2 1 min 2 ( ) 2 1n i n l l n S n S i S l          . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 42 1.3 Thuật toán Frame-Stewart cho bài toán Tháp Hà Nội với nhiều cọc Với 3p  , kí hiệu ( )pS n số lần chuyển ít nhất giải bài toán Tháp Hà Nội với p cọc và n đĩa theo thuật toán Frame-Stewart. Thí dụ, 3( ) 2 1 nS n   và 4(5) 13S  . Tương tự như trong bài toán bốn cọc, ta cũng có thuật toán Frame- Stewart cho bài toán với số cọc bất kì như sau. Nếu số cọc 3p  thì sử dụng thuật toán tối ưu cho bài toán Tháp Hà Nội với ba cọc trong Chương 2. Với 3p  và 0n  chọn số 0 i n  làm cực tiểu số lần chuyển các đĩa theo qui tắc (thuật toán Frame-Stewart) sau.  Chuyển l đĩa nhỏ trên cùng từ cọc nguồn sang cọc 1 ( n l đĩa dưới cùng vẫn ở trên cọc nguồn). Trong quá trình chuyển sử dụng tất cả các cọc. Điều này có thể làm được với số lần chuyển ít nhất được kí hiệu là ( )pS l .  Chuyển n l đĩa dưới cùng từ cọc nguồn sang cọc đích mất 1( )pS n l  lần chuyển (vì cọc 1 đang được sử dụng chứa các đĩa nhỏ nên chỉ còn sử dụng được 1p  cọc).  Chuyển l đĩa từ cọc 1 sang cọc đích. Trong quá trình chuyển sử dụng tất cả các cọc. Để làm được điều này cần ( )pS l lần chuyển. Công thức truy hồi cho lời giải bài toán Tháp Hà Nội dựa trên thuật toán Frame-Stewart là:  1 0 0 khi 0; ( ) 2 1 khi 3, 0; min 2 ( ) ( ) khi 3, 0. n p p p l n n S n p n S l S n l p n               (1.1) Như vậy, Bài toán Tháp Hà Nội với nhiều cọc trở thành bài toán tối ưu rời rạc: Tìm  1 0 ( ) min 2 ( ) ( )p p p l n S n S l S n l      . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 43 Nhận xét 1.1 Một điều thú vị là ta có thể nhận được kết quả của bài toán Tháp Hà Nội với ba cọc từ trường hợp hai cọc theo thuật toán Frame-Stewart như sau. Xuất phát từ thực tế, theo logic, ta đặt (khi số cọc 2p  và số đĩa 2n  thì bài toán không giải được): 2(0) 0S  , 2(1) 1S  , 2( )S n  với mọi 1n  . Với 3p  , 1n  ta chỉ có thể đặt 1l n  (để thành phần thứ hai 1 2( ) ( )pS n l S n l    là hữu hạn. Khi ấy công thức (1.1) trở thành: 3 3 2 3( ) 2 ( 1) (1) 2 ( 1) 1S n S n S S n      . Đây chính là công thức truy hồi tính số làn chuyển tối ưu khi 3p  . Như vậy, tổng cộng cần 12 ( ) ( )p pS l S n l  lần chuyển cho bài toán p cọc. Bài toán đặt ra là, cần tính số l để tổng này là nhỏ nhất. Thuật toán Frame-Stewart nói trên (với cách chọn l như trên) cho phép tìm ra một (một số) giá trị i sao cho  1 1 1 1 ( ) 2 ( ) ( ) min 2 ( ) ( )p p p p p l n S n S i S n i S l S n l           . (1.2) Nói cách khác, các giá trị i thỏa mãn (1.2) là số bước chuyển tối ưu trong lớp các thuật toán đề nghị. Stewart và Frame cũng đã chứng minh rằng, nếu n là số tam giác kn t , thì cách chọn tối ưu nhất cho l là l k , trong khi đó nếu 1k kt n t   thì cả hai giá trị 1k  và k đều là cách chọn tối ưu cho l . Như vậy, Stewart và Frame đã đề xuất các thuật toán hiển cho bài toán Tháp Hà Nội với bốn cọc. Từ đây ta cũng có nhận xét rằng, khác với trường hợp bài toán với ba cọc, lời giải cho bài toán với bốn cọc có thể là không duy nhất. §2 Tính số bƣớc chuyển tối ƣu trong trò chơi Tháp Hà Nội với bốn cọc Như đã thấy trong mục trước, bài toán tìm số bước chuyển đĩa ít nhất trong trò chơi tháp Hà Nội được đưa về bài toán tối ưu rời rạc. Trong mục này chúng tôi trình bày các đánh giá bước chuyển tối ưu cho bài toán Tháp Hà Nội theo [13]. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 44 2.1 Tính số bƣớc chuyển tối ƣu trong trò chơi Tháp Hà Nội với p cọc và n đĩa. Trƣờng hợp ( 1) 2 p p n   . Trước tiên ta xét các trường hợp đơn giản sau. Vì các nhận xét dưới đây đúng cho số cọc p bất kì nên ta phát biểu cho bài toán với số cọc bất kì. Nhắc lại rằng ( )pH n là kí hiệu số bước chuyển tối thiểu cần thiết để chuyển n đĩa từ cọc nguồn sang cọc đích trong bài toán tháp Hà Nội với p cọc và ( )pS n là kí hiệu số bước chuyển tối thiểu cần thiết để chuyển n đĩa từ cọc nguồn sang cọc đích trong bài toán tháp Hà Nội với p cọc theo thuật toán Frame-Stewart. Ta có Nhận xét 2.1 Dễ dàng thấy rằng (2) 3PH  với mọi 3p  và (3) 5PH  với mọi 4p  .Với 3p  và 1n p  thì ( ) 2 1pH n n  . Chứng minh Hiển nhiên vì 1n p  nên có thể chuyển mỗi đĩa từ số 1 đến số n từ cọc 1P sang mỗi cọc 2 1,..., nP P  tương ứng, mất n lần chuyển. Sau đó lại chuyển các đĩa từ số 1n  đến số 1 (đĩa to trước) từ các cọc tương ứng 2,...,nP P sang cọc 1nP  , mất 1n  lần chuyển. Như vậy, tổng cộng mất 2 1n  lần chuyển hay ( ) 2 1pH n n  . Nhận xét 2.2 Với 3p  và n p thì ( ) 2 1pH n n  . Chứng minh Trước tiên xây dựng tháp gồm 2 đĩa (đĩa số 1 và đĩa số 2) trên cọc nP , mất ba lần chuyển (xem §1 Chương 2). Sau đó lại chuyển các đĩa từ số 3 đến số n (tổng cộng 2n  đĩa) từ cọc 1P sang các cọc 2 1,..., nP P  tương ứng, mất 2n  lần chuyển. Sau đó chuyển 3n  đĩa từ số 1n  đến số 3 từ các cọc tương ứng 2 2,...,nP P sang cọc 1nP  , mất 3n  lần chuyển. Lại chuyển tháp Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 45 gồm 2 đĩa (đĩa số 1 và đĩa số 2) trên cọc nP sang cọc 1nP  , mất ba lần chuyển. Như vậy, tổng cộng mất    3 2 3 3 2 1n n n       lần chuyển hay ( ) 2 1pH n n  . Bây giờ ta xét trường hợp p n . Ta có Nhận xét 2.3 Ta luôn có: 1) ( 1) ( )p pH n H n  với mọi 1n  , 3p  ; 2) 1( ) ( )p pH n H n  với mọi 1n  , 3p  . Ta có Định lí 2.1 Với 3p  và ( 1) 2 p p p n    thì ( ) 4 2 1pH n n p   . Chứng minh Xét các trường hợp sau đây. Trƣờng hợp 1 2 3p n p   . Đặt 1n p l   , 0 2l p   . Thực hiện thuật toán sau. Bƣớc 1 Lần lượt chuyển 1p  đĩa nhỏ nhất từ cọc 1P sang các cọc 2,..., pP P tương ứng sao cho mỗi cọc có một đĩa và đĩa số 1 nằm trên cọc 2P . Còn lại  1n p l   đĩa nằm trên cọc 1P . Đã sử dụng hết p cọc. Bƣớc 2 Lần lượt chuyển l đĩa nhỏ nhất (đĩa số 1 đến đĩa số l ) từ các cọc 1 2,...,lP P (đĩa to nằm trên cọc 1lP chuyển trước) sang cọc 2lP . Như vậy, cọc 2lP chứa 1l  đĩa nhỏ nhất. Các cọc 2 1,..., lP P được giải phóng; Các đĩa số 2l  đến số 1p  ( 2p l  đĩa) vẫn nằm trên các cọc 3,...,l pP P tương ứng. Bƣớc 3 Lần lượt chuyển l đĩa còn lại (đĩa số p đến đĩa số  1p l n   ) từ cọc 1P sang các cọc tự do 1 2,...,lP P sao cho mỗi cọc có một đĩa và đĩa lớn nhất (số n ) nằm trên cọc 2P . Cọc 1P được giải phóng. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 46 Bƣớc 4 Lần lượt chuyển 1l  đĩa lớn (đĩa số 1n l p   đến đĩa số 1n  ) từ các cọc 3 1,..., lP P sang cọc 2P . Như vậy, cọc 2P chứa l đĩa lớn nhất. Các cọc 3 1,..., lP P được giải phóng. Bƣớc 5 Lần lượt chuyển 2p l  đĩa tiếp theo (còn lại trên các cọc 3,...,l pP P , đĩa số 1p  đến đĩa số 2l  ) sang cọc 2P . Như vậy, cọc 2P chứa 2p  đĩa lớn nhất. Các cọc 3,...,l pP P được giải phóng. Bƣớc 6 Lần lượt chuyển l đĩa nhỏ nhất (đĩa số 1 đến đĩa số l ) từ cọc 2lP sang cọc 1 3 4 1, , ,..., lP P P P tương ứng sao cho mỗi cọc có một đĩa và đĩa số 1 nằm trên cọc 1P , đĩa số 2 nằm trên cọc 3P ,…, đĩa số l nằm trên cọc 1lP . Sau đó chuyển đĩa 1l  từ cọc 2lP sang cọc 2P và chuyển l đĩa nhỏ nhất từ các cọc 1 4 3 1, ,..., , ,l lP P P P P sang cọc 2P . Tổng cộng số lần chuyển mất là:           ( ) 1 1 2 1 2 4 3 2 4 1 3 4 2 1. pH n p l l l p l l l p l p n p n p                        Trƣờng hợp 2  1 2 p p n   . Thực hiện thuật toán sau. Bƣớc 1 Lần lượt chuyển 2p  đĩa nhỏ nhất từ cọc 1P sang các cọc 2 1,..., pP P  sao cho mỗi cọc có một đĩa, đĩa nhỏ nhất nằm trên cọc 2P . Sau đó chuyển đĩa số 1p  từ cọc 1P sang cọc pP và lần lượt chuyển 2p  đĩa từ các cọc 1 2,...,pP P sang cọc pP . Mất tất cả    2 1 2 2 3p p p      lần chuyển 1p  đĩa từ cọc 1P sang cọc pP . Các cọc 2 1,..., pP P  được giải phóng (các đĩa lớn từ số p trở đi vẫn nằm trên cọc 1P , các đĩa nhỏ từ số 1 đến số 1p  nằm trên cọc pP ). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 47 Bƣớc 2 Lần lượt chuyển 3p  đĩa tiếp theo (các đĩa số p đến 2 4p  ) từ cọc 1P sang các cọc 2 2,..., pP P  tương ứng sao cho mỗi cọc có một đĩa. Sau đó chuyển đĩa số 2 3p  sang cọc 1pP  và lần lượt chuyển 3p  đĩa từ các cọc 1 2,...,pP P sang cọc 1pP  . Như vậy, để chuyển 2p  đĩa từ cọc 1P sang cọc 1pP  mất tất cả    3 1 3 2 5p p p      lần chuyển. Các cọc 2 2,..., pP P  được giải phóng. Bƣớc 3 Lần lượt chuyển 4p  đĩa tiếp theo (đĩa số 2 2p  đến đĩa số 3 5p  ) từ cọc 1P sang các cọc 2 3,..., pP P  sao cho mỗi cọc có một đĩa. Sau đó chuyển đĩa số 3 4p  sang cọc 2pP  và lần lượt chuyển 4p  đĩa từ các cọc 3 2,...,pP P sang cọc 2pP  . Như vậy, mất tất cả    4 1 4 2 7p p p      lần để chuyển 3p  đĩa từ cọc 1P sang cọc 2pP  . Các cọc 2 3,..., pP P  được giải phóng. Tương tự cho các bước tiếp theo. Bƣớc cuối cùng (bƣớc thứ 1p  ) Chuyển đĩa cuối cùng (đĩa thứ n ) từ cọc 1P sang cọc 2P . Như vậy, cọc kP , 2,3,...,k p có 1k  đĩa, cọc 1P trống. Tổng cộng số lần chuyển 1p  đĩa từ cọc 1P sang cọc pP , 2p  đĩa từ cọc 1P sang cọc 1pP  ,…, đến đĩa cuối cùng (thứ n ) từ cọc 1P sang cọc 2P mất là:           2 1 2 3 1 1 2 3 2 5 ... 1 1 2 p p p p p p              . Tổng số đĩa đã chuyển từ cọc 1P sang các cọc pP , 1pP  ,…, 3P là:          1 1 1 1 1 2 ... 1 2 2 p p p p p p n             . Lại lần lượt chuyển 1n  các đĩa từ các cọc 3,..., pP P sang cọc 2P như sau. Vì cọc 1P trống, cọc 2P chứa đĩa số n , cọc 3P chứa hai đĩa số 1n  , 2n  nên chuyển đĩa số 2n  từ cọc 3P sang cọc 1P , đĩa số 1n  từ cọc 3P Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 48 sang cọc 2P và lại chuyển đĩa số 2n  từ cọc 1P sang cọc 2P . Mất 3 lần chuyển. Và được 3 đĩa to nhất trên cọc 2P . Cọc 1P và 3P trống. Vì cọc 1P và 3P trống, cọc 2P chứa 3 đĩa to nhất n , 1n  , 2n  , cọc 4P chứa ba đĩa số đĩa số 3, 4, 5n n n   nên chuyển đĩa số 5n  sang cọc 1P , 4n  sang cọc 3P và 3n  sang cọc 2P , sau đó lại chuyển đĩa số 4n  từ cọc 3P sang cọc 2P và chuyển đĩa số 5n  từ cọc 1P sang cọc 2P . Mất 5 lần chuyển. Và được thêm 3 đĩa (thành 1+2+3=6) to nhất trên cọc 2P . Cọc 1P , 3P , 4P trống. Tương tự, đến bước cuối cùng ta có: Các cọc 1P , 3P ,…, 1pP  trống, cọc 2P chứa các đĩa từ có số từ n đến p , cọc pP chứa các đĩa có số từ 1p  đến số 1. Chuyển các đĩa có số 1 đến 2p  sang các cọc 1P , 3P ,…, 1pP  tương ứng. Sau đó chuyển đĩa số 1p  từ cọc pP sang cọc 2P . Lại chuyển các đĩa có số 2p  đến số 1 từ các cọc 1pP  ,…, 3P , 1P sang cọc 2P . Mất    2 1 2 2 3p p p      lần chuyển. Tất cả các đĩa ở trên cọc 2P . Công việc hoàn thành. Tổng số lần chuyển đĩa từ các cọc 3,..., pP P sang cọc 2P mất:         2 2 3 3 2 3 5 ... 2 3 2 2 p p p p p p             . Vậy tổng số lần chuyển đĩa là:       2 21 2 2 4 1 2 1 2 1 4 2 1p p p p p p p p n p             . Nhận xét 2.4 Ta cũng có thể viết số lần chuyển đĩa trên bằng       2 221 2 2 4 1 2 1 1p p p p p p         . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 49 Trƣờng hợp 3  1 2 3 2 p p p n     . Đặt  1 2 p p i n    . Thực hiện thuật toán như trên, nhưng số lần chuyển đĩa lúc này giảm đi 4i và bằng      2 2 1 ( ) 2 1 1 4 2 1 1 4 4 2 1 2 p p p S n p i p n n p                  . Định lí 2.1 chứng minh xong. Như vậy, nếu  1 2 p p n   thì ta có công thức hiển tính số bước chuyển tối ưu giải bài toán Tháp Hà Nội. Trường hợp  1 2 p p n   với số cọc p bất kì sẽ được xem xét trong Chương 4. Dưới đây chúng ta xét trường hợp 4p  . 2.2 Tính số bƣớc chuyển tối ƣu trong trò chơi Tháp Hà Nội với bốn cọc và n đĩa Định lí 2.2 Giả sử n là số đĩa cố định và    1 1 2 2 x x x x n     . Số bước chuyển tối ưu theo thuật toán Frame-Stewart là   224( ) 2 2 2 1xS n n x x     . (2.1) Chứng minh Xét các trường hợp sau. Trƣờng hợp 1  1 2 x x n   ( n là số tam giác) Thuật toán Frame-Stewart chuyển n đĩa từ cọc 1P sang cọc 4P như sau: Bước 1: Với 0 l n  chọn trước, chuyển l đĩa nhỏ nhất (trên cùng) từ cọc 1P sang cọc 4P (sử dụng tất cả bốn cọc). Số lần chuyển tối ưu là 4( )S l . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 50 Bước 2: Chuyển n l đĩa lớn nhất (dưới cùng) từ cọc 1P sang cọc 2P , sử dụng ba cọc (vì cọc 4P đang chứa l đĩa nhỏ nhất). Số lần chuyển tối ưu là 2 1n l  . Bước 3: Lại chuyển l đĩa nhỏ nhất (trên cùng) từ cọc 4P sang cọc 2P (sử dụng tất cả bốn cọc). Số lần chuyển tối ưu là 4( )S l . Như vậy, với mỗi 0 l n  chọn trước, số lần chuyển tối ưu là 4 4( ) 2 ( ) 2 1 n lS n S l    . (2.2) Rõ ràng, vì cọc 3P trống nên trong Bước 1, để chuyển l đĩa từ cọc 1P sang cọc 4P , ta có thể áp dụng thuật toán Frame-Stewart chuyển j đĩa nhỏ nhất (trên cùng, 0 j l  ) từ cọc 1P sang cọc 3P (sử dụng bốn cọc) và l j đĩa lớn hơn từ cọc 1P sang cọc 4P (sử dụng ba cọc mất 2 1l j  lần chuyển), sau đó lại chuyển j đĩa nhỏ nhất từ cọc 3P sang cọc 4P (sử dụng bốn cọc). Như vậy, để chuyển l đĩa từ cọc 1P sang cọc 4P sẽ mất 42 ( ) 2 1 l jS j   bước chuyển. Do đó, với mỗi l và j chọn trước, cần  4 42 ( ) 2 1 2 2 ( ) 2 1 2 1n l l j n lS l S j         bước để chuyển n đĩa từ cọc 1P sang cọc 2P . Sử dụng thuật toán Frame-Stewart và công thức (2.2) nhiều lần, chúng ta nhận được công thức sau đây tính số bước chuyển tối ưu cho bài tóan tháp Hà Nội với bốn cọc và    1 1 ... 1 2 x x n x x        là số tam giác:    1 2 24( ) 2 1 2 2 1 2 2 1 ... 2 2 1 2.1 ...x x xS n            . (2.3) Số đĩa cần thiết để chuyển ba đĩa nhỏ nhất từ cọc 1P sang cọc trung gian ( 3P hoặc 4P ) được thể hiện trong ngoặc trong cùng. Mở ngoặc trong công thức (2.3) ta nhận được 1x  số hạng có tổng bằng 2x , và một số hạng bằng 12x . Các số hạng còn lại có tổng bằng Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 51    2 11 2 4 ... 2 2 1x x         . Vậy, khi  1 2 x x n   là số tam giác, ta có      1 14( ) 1 2 2 2 1 1 2 1x x x xS n x x         . (2.4) Trƣờng hợp 2    1 1 2 2 x x x x n     ( n không phải là số tam giác) Ta tính số 4( )S n như sau. Quan sát công thức (2.3) ta thấy, nếu thiếu một đĩa (nhỏ nhất), tức là  1 1 2 x x n    thì trên cọc 1P cho phép tiết kiệm 12m lần chuyển để đưa các đĩa từ cọc 1P sang cọc 2P so với trường hợp n là số tam giác. Nếu ta cần chuyển  1 2 x x n   từ cọc 1P sang cọc 2P và  1 2 x x n   thì số lần chuyển “tiết kiệm” được sẽ là     1 2 1 2 1 2 2 2 x xx x n x x n           . Cuối cùng, ta nhận được                2 2 2 2 4 22 2 2 ( ) 1 2 1 1 2 2 1 2 .2 1 1 2 2 2 4 4 2 1 2 2 2 1. x x x x x x S n x x x n x x x n x x x n n x x                             Nhận xét rằng, khi  1 2 x x n   thì hai công thức (2.3) và (2.4) trùng nhau và trùng với công thức (2.1). Định lí chứng minh xong. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 52 Chƣơng 4 BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT §1 Tính số ( )pS n trong thuật toán Frame-Stewart cho trò chơi Tháp Hà Nội tổng quát Trong §2 Chương 3 chúng tôi đã trình bày kết quả của Novikov, 2007 [13] tính giá trị tối ưu ( )pS n của bài toán tháp Hà Nội cho trường hợp bốn cọc và cho một số trường hợp với số cọc bất kì. Trong § này chúng tôi trình bày nghiên cứu của Rand (2009, [16]) về số lần chuyển tối ưu theo thuật toán Frame-Stewart cho bài toán tháp Hà Nội với số cọc bất kì. Kết quả của Rand là sự phát triển của hàng loạt các kết quả của các tác giả trước (S. Novikov, 2007; Petr, 2002; Maujumdar, 1996,…) và bổ sung cho kết quả của Novikov trong chương trước. 1.1 Số chia tối ƣu Ta cần kết quả bổ trợ sau trong các chứng minh định lí. Nhận xét 2.1 Ta có công thức tính toán tổ hợp sau. 1 1 1 k k k m m mC C C     . trong đó   ! : ! ! k m m C k m k   ; : 0kmC  nếu m k ; ,m k . Chứng minh Theo định nghĩa ta có                            1 1 1 ! 1 !! ! ! ! 1 ! 1 ! 1 ! 1 ! 1 ! ! 1 ! . 1 ! 1 1 ! k k m m k m m k m m km m C C k m k k m k k m k m k m C k m k                          . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 53 Định nghĩa 2.1 Giả sử :pD   là hàm số xác định bởi công thức ( ) ( ) ( 1)p p pD i S i S i   . Như vậy, ( )pD i miêu tả số chuyển động đòi hỏi phải thực hiện theo thuật toán Stewart khi thêm một đĩa (từ 1i  đến i đĩa), khi số cọc vẫn là p . Định lí 1.1 Giả sử , ,n p x , 1n  , 3p  . Khi ấy ta có đánh giá sau cho bài toán Tháp Hà Nội với p cọc: Với mọi 0x  , ( ) 2xpD n   2 2 3 2 p p p x p xC n C        . Điều này tương đương với: nếu ta kí hiệu pD là dãy  ( )p iD i  thì dãy pD sẽ chứa 3 3 p pC   phần tử có giá trị 02 , tiếp theo 3 3 1 p pC    phần tử có giá trị 12 , 3 3 2 p pC    phần tử có giá trị 22 ,v.v. Ví dụ 1.1 Với 5p  dãy  5D là như sau:         3 3 1 3 0 3 1 5 0 1 2 0 1 1 1 2 2 2 2 2 2 phan tu gia tri 2 ; phan tu gia tri 2 ;... 1phan tu gia tri 2 ;3 phan tu gia tri 2 ;6 phan tu gia tri 2 ... 2 , 2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ... 1, 2,2,2,4,4,4,4,4,4,8,8,8,8,8,8,8,8,8,8,. p p p pC C         .. Chứng minh Định lí 1.1 Để chứng minh Định lí 1.1 ta sẽ sử dụng hai lần qui nạp theo số đĩa và theo số cọc. Chứng minh gồm các bước sau.  Chứng minh Định lí 1.1 đúng cho mọi n nếu 3p  .  Chứng minh Định lí 1.1 đúng cho mọi p nếu 1n  . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 54  Giả sử Định lí 1.1 đúng với mọi 0p p và 0n n , khi ấy Định lí 1.1 đúng cho 0p p và 0n n . Trƣờng hợp cơ bản 1 Định lí 1.1 đúng cho mọi n nếu 3p  . Chứng minh Chúng ta cần chỉ ra rằng 3( ) 2 xD n   1 11x xC n C   . Vì 1 1 1x xC n C       1 !! 1! 1 ! 1! ! xx n x x      1x n x    1x n  , nghĩa là ta phải chứng minh 1 3( ) 2 nD n  . Vì 3( ) 2 1 nS n   nên    1 13 3 3( ) : ( ) ( 1) 2 1 2 1 2n n nD n S n S n          . Trƣờng hợp cơ bản 2 Định lí 1.1 đúng cho mọi p nếu 1n  . Chứng minh Khẳng định của Định lí 1.1 dẫn đến (1) 2xpD   2 2 3 21 p p p x p xC C        . Vì 2 2 3 21 p p p x p xC C        nên 2 3 0 p p xC     hay 3 2p x p    . Suy ra 0x  . Vậy (1) 1 (1) (0)p p pD S S   . Điều này hiển nhiên đúng vì (1) 1pS  ; (0) 0pS  . Bƣớc qui nạp Giả sử Định lí 1.1 đúng với mọi 0p p và 0n n , khi ấy Định lí 1.1 đúng cho 0p p và 0n n . Để chứng minh bước qui nạp, ta cần các định nghĩa sau. Định nghĩa 1.2 Trong bài toán Tháp Hà Nội với p cọc, ta gọi số đĩa n là hoàn hảo ứng với p , nếu có thể biểu diễn n dưới dạng 2 2 p p xn C    cho một số 0x  nào đó. Khi p cố định, để ngắn gọn, ta chỉ nói n là hoàn hảo. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 55 Định nghĩa 1.3 Trong bài toán Tháp Hà Nội với p cọc và n đĩa, ta gọi số i là số chia tối ưu nếu 1( ) 2 ( ) ( )p p pS n S i S n i   . Nhận xét rằng i là số chia tối ưu nếu và chỉ nếu: Với mọi l mà 0 l n  thì 1 12 ( ) ( ) 2 ( ) ( )p p p pS i S n i S l S n l      , tức là  1 1 0 ( ) 2 ( ) ( ) min 2 ( ) ( )p p p p p l n S n S i S n i S l S n l          . Nói cách khác, số chia tối ưu i làm cực tiểu số lần chuyển đĩa theo thuật toán Frame-Stewart. Chứng minh bƣớc qui nạp Giả sử Định lí 1.1 đúng với mọi số cọc nhỏ hơn p và mọi số đĩa nhỏ hơn n , khi ấy Định lí 1.1 đúng cho p và n . Hơn nữa,  Ta sẽ xác định một đánh giá trên và đánh giá dưới cho số chia tối ưu i của n .  Trong khoảng đánh giá ấy, mọi i đều là những số chia tối ưu. Sau đó, sử dụng thông tin này, ta có thể tính trực tiếp ( )pD n cho số n liên quan bằng cách sử dụng giả thiết qui nạp. Bổ đề 1.1 Giả sử Định lí 1.1 đúng cho mọi số đĩa nhỏ hơn n . Khi ấy với n thỏa mãn bất đẳng thức 2 2 3 2 p p p x p xC n C        thì số chia tối ưu i nằm trong khoảng 2 2 4 3 p p p x p xC i C        . (1.1) Nhận xét rằng trong trường hợp cơ bản 1n  thì bất đẳng thức 2 2 3 21 p p p x p xC C        thỏa mãn cho duy nhất 0x  . Bất đẳng thức (1.1) trở thành 4 3 2 2 p p p pC i C      nên 0i  , tức là khi 1n  không có (không cần) phép chia tối ưu (chỉ cần một lần chuyển đĩa). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 56 Chứng minh Bổ đề 1.1 Nếu i là số chia tối ưu thì theo định nghĩa, với mọi l thỏa mãn 0 l n  ta có 1 12 ( ) ( ) 2 ( ) ( )k k k kS i S n i S l S n l      . Với n thỏa mãn bất đẳng thức 2 2 3 2 p p p x p xC n C        , ta sẽ chứng minh rằng nếu i nằm ngoài khoảng đánh giá (1.1), thì tồn tại số l sao cho 1 12 ( ) ( ) 2 ( ) ( )k k k kS l S n l S i S n i      , (1.2) tức là nó không phải là số chia tối ưu. Đầu tiên giả sử rằng, 2 4 p p xi C    . Đoạn 241, pp xC   được chia bởi các số   2 2 2 2 2 2 2 1 5 41 1 ... ...p p p p p p pk x xkC C C C C C C                     . Như vậy,   2 2 2 2 1 p p p k p k C i C       với  0,1,..., 3k x  nào đó. Ta sẽ chứng minh 1l i  thỏa mãn bất đẳng thức (1.2). Vì l n (do 2 4 p p xi C    nên 2 2 4 31 1 1 p p x xl i C C n           ) nên kết hợp với bất đẳng thức     2 2 3 1 2 1 p p p k p k C l C          (do   2 2 2 2 1 p p p p k C i C       và 1l i  ) và chú ý rằng 3k x  , theo giả thiết qui nạp, ta suy ra 1 2( ) 2 2k xpD l    . Do 2 4 p p xi C    nên 2 2 4 41 1 p p x xl i C C             . Vì 2 3 p p xn C    nên sử dụng Nhận xét 1.1 ta có 2 2 3 3 4 4 p p p p x p x p xn l C C C          . Hơn nữa, do 1i  nên 2l  và 2 2 2 p p xn l C      (do 2 2 3 2 p p p x p xC n C        ). Lập luận tương tự như trên, chia khoảng  3 24 2,p pp x p xC C     bởi các điểm     3 3 2 33 1 3 1 ...p p pp xp x p xC C C           hay                      1 2 1 2 1 2 1 2 1 1 ... ... p p p p x x x k x k C C C C                      Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 57 thì n l nằm một trong các khoảng        1 2 1 2 1 2 1 1 2 p p p k x p x k C n l C                 với  0,1,...k thì theo qui nạp của định lí ta có 1( ) 2 2 x k x pD n l      . Bây giờ, nhắc lại rằng ( ) ( ) ( 1)p p pD k S k S k   và 1l i  , ta có          1 1 1 1 1 2 1 1 2 ( ) ( ) 2 ( ) ( 1) ( 1 ) ( ) 2 ( ) 2 ( ) ( ) ( ) 2 ( ) 2.2 ( ) 2 2 ( ) ( ). p p p p p p p p p p x x p p p p S l S n l D l S l S n l D n l S i D l S n i D n l S i S n i S i S n i                                 Như vậy, nếu 2 4 p p xi C    thì i không phải là số chia tối ưu. Bây giờ giả sử 2 3 p p xn i C     và chọn 1l i  (nhắc lại rằng ta đòi hỏi i n để có thể sử dụng giả thiết qui nạp cho i và l . ) Bởi vì 2 3 p p xi C    và 2 2 p x pn C    nên ta có 2 2 3 2 3 3 p p p p x p x p xn i C C C          và 3 31 p p xn l n i C        . Tương tự như chứng minh trường hợp trên, vì giả thiết qui nạp của Định lí 1.1 đúng với 2 3 p p xn i C     nên ta suy ra rằng ( ) 2xpD i  . Với 3 3 k x kn l C     theo qui nạp ta cũng suy ra 1( ) 2 x pD n l   . Do 1l i  nên         1 1 1 1 1 1 1 2 ( ) ( ) 2 ( 1) ( 1) ( 1 ) ( ) 2 ( ) 2 ( ) ( ) ( ) 2 ( ) 2.2 ( ) 2 2 ( ) ( ). p p p p p p p p p p x x p p p p S l S n l S l D l S n l D n l S i D i S n i D n l S i S n i S i S n i                                 Như vậy, i không phải là số chia tối ưu. Bổ đề chứng minh xong. Bổ đề 1.2 Giả sử Định lí 1.1 đúng cho mọi số đĩa nhỏ hơn n . Khi ấy với n thỏa mãn bất đẳng thức 2 3 p p xC    2 2 p p xn C     , và với mọi số chia tối ưu i ta có 3 3 4 3 p p p x p xC n i C         . (1.3) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 58 Chứng minh Tương tự như trong Bổ đề 1.1. Đầu tiên ta giả sử 3 4 p p xn i C     . Khi ấy   3 2 3 2 2 4 3 4 4 3 1 p p p p p x x x x x i n C C C C C               . Do đó theo giả thiết qui nạp của Định lí 1.1 ta có 1( ) 2xpD i  . Đặt 1l i  thì      1 23 4 1 2 1 1 pp x p x n l n i C C            vì 3 4 p p xn i     . Theo giả thiết qui nạp của Định lí 1.1 ta lại có 1 1( ) 2 x pD n l     . Khi ấy         1 1 1 1 1 1 1 1 1 2 ( ) ( ) 2 ( 1) ( 1) ( 1) ( ) 2 ( ) 2 ( ) ( ) ( ) 2 ( ) 2.2 ( ) 2 2 ( ) ( ). p p p p p p p p p p x x p p p p S l S n l S l D l S n l D n l S i D i S n i D n l S i S n i S i S n i                                   Vậy i không thể là số chia tối ưu hay nếu i là số chia tối ưu thì 3 4 p p xn i C     . Bây giờ giả sử      1 23 3 1 3 1 pp p x p x n i C C            . Khi ấy lại theo giả thiết qui nạp của Định lí 1.1 ta có 1 1( ) 2 x pD n i     . Mặt khác,    2 13 2 3 3 p xp p p x p x x xi n C C C C C                . Do đó nếu đặt 1l i  thì    2 1 2 1 p x p x l C        . Lại theo giả thiết qui nạp của Định lí 1.1 ta có 1( ) 2xpD l  . Bây giờ ta có thể tính         1 1 1 1 1 1 1 1 1 2 ( ) ( ) 2 ( 1) ( ) ( 1) ( ) 2 ( ) 2 ( ) ( ) ( ) 2 ( ) 2.2 ( ) 2 2 ( ) ( ). p p p p p p p p p p x x p p p p S l S n l S l D l S n l D n l S i D l S n i D n l S i S n i S i S n i                                  Vậy i không phải là số chia tối ưu. Do đó ta đi đến kết luận rằng nếu i là số chia tối ưu thì 3 3 k k xn i C     . Kết hợp hai trường hợp ta đí đến kết luận của Bổ đề 1.1. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 59 Nhận xét 1.2 Nhận xét rằng với mọi số hoàn hảo 2 2 p p xn C    , Bổ đề 1.1 nói rằng mọi số chia tối ưu i phải thỏa mãn bất đẳng thức 2 3 p p xi C    và Bổ đề 1.2 nói rằng 3 3 p p xn i C      3 2 3 2 3 p p p p x x x xi n C C C C             . Do đó chúng ta đã chứng minh rằng từ Định lí 1.1 suy ra nếu 2 2 p p xn C    thì số chia tối ưu 3 3 p p xi C    là duy nhất. Nói cách khác, khi n là số hoàn hảo ( 2 2 p p xn C    ) thì số chia tối ưu i cũng là số hoàn hảo ( 3 3 p p xi C    ), và là duy nhất. Ta cũng dễ dàng tính được i . Ta sẽ có các hệ quả từ nhận xét thú vị này ở cuối mục. Bổ đề 1.3 Giả sử Định lí 1.1 đúng cho mọi số đĩa nhỏ hơn n . Khi ấy với n thỏa mãn bất đẳng thức 2 2 3 2 p p p x p xC n C        , nếu số nguyên i thỏa mãn điều kiện phát biểu trong Bổ đề 1.1 và Bổ đề 1.2 (thỏa mãn các bất đẳng thức (1.1) và (1.3)) thì i là số chia tối ưu. Chứng minh Ta sẽ chỉ ra rằng với mọi cách chọn i đồng thời thỏa mãn các bất đẳng thức (1.1) và (1.3) thì biểu thức 12 ( ) ( )p pS i S n i  là không đổi. Vì 2 2 3 2 p p p x p xC n C        nên ta có thể đặt 2 3 p p xn C a     , trong đó 3 2 2 30 p p p x x xa C C C          . Vì i thỏa mãn bất đẳng thức (1.1), tức là 2 2 4 3 p p p x p xC i C        nên ta có thể đặt 2 4 p p xi C b     . Hơn nữa, ta có thể viết bất đẳng thức 2 2 4 3 p p p x p xC i C        dưới dạng     2 2 3 1 2 1 p p p x p x C i C          . Áp dụng giả thiết qui nạp của Định lí 1.1 ta có     2 2 3 1 2 1 p p p x p x C i C           1( ) 2xpD i  . Từ Định nghĩa của ( )pD i và Bổ đề 1.1: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 60             1 1 1 1 ( ) 1 ( ) 1 2 2 ( 1) 2 3 ( 2) 2.2 ... 2 . x x p p p p p p x x p p p S i S i D i S i S i D i S i D i S i b b                         (1.4) Hoàn toàn tương tự, do n i thỏa mãn bất đẳng thức (1.3), tức là 3 3 4 3 p p p x p xC n i C         nên ta có thể đặt 3 4 p p xn i C c      . Hơn nữa, bất đẳng thức 3 3 4 3 p p p x p xC n i C         có thể viết dưới dạng        1 2 1 2 1 3 1 2 p p p x p x C n i C              . Áp dụng giả thiết qui nạp của Định lí 1.1, ta có        1 2 1 2 1 3 1 2 p p p x p x C n i C               1( ) 2 x pD n i   . Theo Định nghĩa của ( )pD i , Bổ đề 1.2 và theo giả thiết qui nạp của Định lí 1.1:          1 1 1 1 1 1 1 1 ( ) ( 1) ( 1) 1 2 2 ( 1) 2 2 2.2 ... .2 . x p p p p x x p p p x p S n i S n i D n i S n i S n i D n i S n i S n i c c                                    (1.5) Do 2 4 p p xi C b     và 3 4 p p xn i C c      nên      2 3 24 4 3p p px x xn i n i C b C c C b c              . Mà 2 3 p p xn C a     nên a b c  . Do   2 2 3 2 1 p p p x p x n a C C        là số hoàn hảo (theo Định nghĩa 1.2) nên theo Nhận xét 1.2, số   3 3 43 1 p p p xp x i C C      là số chia tối ưu duy nhất cho n a . Do đó theo Định nghĩa số chia tối ưu và Định nghĩa của ( )pD i ta có: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 61     1 1 1 1 1 1 1 1 ( ) 2 ( ) ( ) 2 ( 1) ( ) ( 1) ( 1) 2 ( 1) 2.2 ( 1) 2 2 ( 1) ( 1) ... 2 ( ) ( ) 2 ( ) ( ). p p p p p p p x x p p p p p p p p S n a S i S n a i S i D i S n a i D n a i S i S n a i S i S n a i S i b S n a i b S i b S n c i                                                   (1.6) Từ (1.4), (1.5) và (1.6) ta có     11 12 ( ) ( ) 2 2 .2 ( ) 2 . x x p p p p x p S i S n i S i b b S n i c c S n a a               (1.7) Biểu thức trên không phụ thuộc vào cách chọn i (hay cách chọn b và c , miễn là chúng thỏa mãn các bất đẳng thức (1.1), (1.3) và a b c  ). Hơn nữa giá trị 12 ( ) ( )p pS i S n i  là nhỏ nhất (trong tất cả các số 12 ( ) ( )p pS l S n l  , 0 l n  ), từ đó suy ra rằng mọi i đồng thời thỏa mãn các bất đẳng thức (1.1) và (1.3) là số chia tối ưu. Đẳng thức (1.7) cũng kết thúc chứng minh Định lí 1.1. Từ Định lí 1.1 ta có Hệ quả 1.1 Nếu n là một trong k số trong khoảng 1k kt n t   thì 1 4 4 4( ) ( ) ( 1) 2 kD n M n M n     . 1.2 Công thức tính ( )pS n Mục 1.1 đã cung cấp cho ta khá nhiều thông tin về các giá trị của ( )pS n , do đó có thể tính giá trị của ( )pS n theo n và p mà không cần dùng công thức đệ qui. Định lí 1.2 Với 3k  và 2 2 3 2 p p p x p xC n C        với một 0x  nào đó, ta có .   1 3 3 3 3 0 ( ) 2 2 x p i p x p p x p x i S n C n C            . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 62 Chứng minh Đây là hệ quả trực tiếp từ Định lí 1.1, bởi vì       2 2 2 2 3 3 1 1 0 1 1 1 1 2 2 3 3 3 2 3 3 3 3 0 0 ( ) (0) ( ) 0 2 2 2 2 2 2 . p p i p p p i p i Cn x n i x p p p i i j C i C x x p p i p x p i p x p i p i p x p i p x i i S n S D i C C n C C n C                                                      Hệ quả 1.2 Nếu 1k kt n t   thì  1 14 1 ( ) 2 2 k i k k i S n i t n      . Trƣờng hợp số hoàn hảo Nhắc lại Nhận xét 1.2, nếu n là số hoàn hảo, 2 2 p p xn C    thì tồn tại duy nhất số chia tối ưu 2 3 p p xi C    và do đó 2 2 3 2 3 3 p p p p x p x p xn i C C C          . Như vậy,   2 2 3 2 1 p p p x p x i C C       là số hoàn hảo cho bài toán với p cọc,    1 2 1 2 p p x n i C        là số hoàn hảo cho bài toán với 1p  cọc. Do đó mỗi ( )pS i và 1( )pS n i  trong công thức truy hồi 1( ) 2 ( ) ( )p p pS n S i S n i   cũng là hoàn hảo và dễ dàng tính được nếu sử dụng tam giác Pascal. Sử dụng tam giác Pascal, ta dễ dàng tính được ( )pS n cho mọi số hoàn hảo n như sau. Nhắc lại rằng các số tham gia trong tam giác Pascal có công thức là 1, 1, 1 1 khi 0 0 khi 0, 0 khi 0, 0 j ij i i j i j j P C i j P P i j              trong đó ijP là số Pascal tại dòng thứ i và cột thứ j , chỉ số bắt đầu tính từ 0. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 63 Đầu tiên xây dựng tam giác Pascal P với các cột được đánh số bên ngoài theo 2, nghĩa là ijP chỉ được xác định khi 0i  , 2j  và , 2ij i jP P   , do đó 2 1iP  với mọi 0i  . Điều này cho phép chúng ta ánh xạ x và p qua số hoàn hảo p xn C như sau: p xp xP C n   . Sau đó chúng ta xây dựng tam giác thứ hai P với cột ngoài rìa cũng như vậy, nhưng thay vì các số Pascal 1, 1, 1ij i j i jP P P    ta đặt 1, 1, 12ij i j i jP P P      . Khi ấy ta có thể ánh xạ x và p qua      1 1 12p p pxp p x p x p xP S C S C S C      . Bây giờ, sử dụng P để tính x dựa trên n , và sử dụng P để tính ( )pS n dựa trên x , ta có thể dễ dàng và thuận tiện tính được ( )pS n cho mọi số đĩa là số hoàn hảo và mọi số cọc p (xem Bảng dưới đây). P p x 2 3 4 5 6 7 8 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 P p x 2 3 4 5 6 7 8 0 1 1 1 1 2 1 3 1 3 1 7 5 1 4 1 15 17 7 1 5 1 31 49 31 9 1 6 1 63 129 111 49 11 1 Để tìm ( )pS n cho một số hoàn hảo p xn C nào đó, đầu tiên ta nhìn vào cột p trong P . Khi đó ta có thể tìm được x bằng cách nhìn vào chỉ số của dòng chứa n . Cuối cùng, nhìn sang ,x k của bảng P để tính được ( )xp pP S n  . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 64 Ví dụ 1.2 Với 15n  Để tính 4(15)S ta nhìn vào cột 4p  , thấy số 15, ứng với 6x  . Bảng P cho 6,4 129P  . Như vậy, 4(15) 129S  . Số 15n  nằm trong bảng Pascal vì nó là số hoàn hảo: 4 4 6 415 xn C C    . Ví dụ 1.3 Để tìm 5(10)S ta chỉ cần nhìn trên bảng P , ứng với cột 5p  , 10P  sẽ là 5x  . Bảng P cho 5,5 31P  . Như vậy, 5(5) 31S  . 1.3 Tính trực tiếp số chia tối ƣu i Bài toán 1.1 Giả sử số cọc p cố định. Tính số chia tối ưu i theo số đĩa n . Từ các Định lí 1.1, 1.2 và các hệ quả của nó, ta có thể giải quyết bài toán này cho trường hợp bốn cọc. Định lí 1.3 Cho bài toán bốn cọc, với mọi số đĩa n . Nếu 2 2 1 2x xC n C   thì 1i n x   là số chia tối ưu. Chứng minh Ta nhắc lại các Bổ đề 1.1 và 1.2: Nếu 2 2 3 2 p p p x p xC n C        thì mọi số i thỏa mãn hai bất đẳng thức (1.1) và (1.3) 2 2 4 3 p p p x p xC i C        và 3 3 4 3 p p p x p xC n i C         sẽ là số chia tối ưu. Với 4p  các bổ đề này có thể phát biểu lại như sau: Nếu 2 2 1 2x xC n C   thì mọi số i thỏa mãn hai bất đẳng thức 2 2 1x xC i C   và 1 1 1x xC n i C    (1.8) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 65 hay 2 2 1x xC i C          1 !! 2! 2 ! 2! 1 ! xx i x x          1 1 2 2 x x x x i     (1.8a) và 1 1 1x xC n i C     1x n i x    . (1.8b) Ta có 2 2 1 2x xC n C         1 ! 2 ! 2! 1 ! 2! ! x x n x x           1 1 2 2 2 x x x x n      . (1.9) Vì i phải thỏa mãn (1.8b) nên n i chỉ có thể là: n i x  hoặc 1n i x   hay i n x  hoặc 1i n x   . Chọn 1i n x   thì ta có đánh giá sau đây cho i : (1.9)      1 1 2 1 1 1 2 2 x x x x x n x x             2 22 2 2 x x x x i         21 1 2 2 x x x x i      . .Do i nguyên nên    1 1 2 2 x x x x i     . Chứng tỏ i thỏa mãn bất đẳng thức (1.8a). Vậy theo Bổ đề 1.3, 1i n x   là số chia tối ưu. Nhận xét 1.3 Nếu chọn i n x  thì vì     1 1 2 2 2 x x x x n      nên ta có đánh giá sau đây cho i : (1.9)      1 1 2 2 2 x x x x x n x x            21 2 2 2 x x x x i      . Bất đẳng thức (1.8a) không thỏa mãn khi 2 2 2 x x i    hay 2 2 2 x x n x       2 1 ( 2)3 2 2 2 x xx x n      . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 66 Vì vậy i n x  có thể không phải là số chia tối ưu. Bổ đề 1.4 Với mọi ,a b , 0 a b  ta có a ab    . Bổ đề 1.5 Cho  1 ( ) 2 x x f x   và 3 ( ) 2 2 g y y        . Khi ấy ( ( ))g f x x với mọi x R . Chứng minh Theo Bổ đề 1.5 ta có     3 ( ( )) 2 ( ) 1 1 1 1 2 g f x f x x x x x                . Mặt khác, do x nên 1 0x x   . Do đó theo bất đẳng thức Cauchy ta có    1 1 2 x x x x        3 1 3 1 1 2 2 2 x x x x       . Suy ra   3 1 1 2 x x x          . Vậy   3 1 1 2 x x x x           . Chứng tỏ   3 1 ( ( )) 1 2 x g f x x x x            hay ( ( ))g f x x . Bổ đề 1.6 Cho 3 ( ) : 2 2 g y y        . Khi ấy 2 2 1( ) x xg y x C y C    . Chứng minh Ta có 2 2 1x xC y C        1 2 1 2 2 x x x x y      . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 67 Trước tiên ta chứng minh rằng,   1 2 2 x x y    suy ra  g y x . Thật vậy, do cả hai số y và   1 2 2 x x  đều là những số nguyên nên từ   1 2 2 x x y    suy ra    2 2 3 1 2 3 4 2 1 2 2 2 x x x x x y            .  2 3 2 2 y x         3 2 2 y x   3 2 2 y x        (do x là số tự nhiên), hay  g y x . Bây giờ giả sử  1 ( ) 2 x x y f x    . Vì 3 ( ) 2 2 g y y        là hàm tăng và theo Bổ đề 1.5 ta có ( ( ))g f x x nên ( )y f x suy ra ( ) ( ( ))g y g f x x  . Kết hợp cả hai bất đẳng thức trên ta có 2 2 1( ) x xg y x C y C    Hệ quả 1.4 Trong bài toán Tháp Hà Nội với bốn cọc và với n đĩa bất kì, số chia tối ưu là 1 2 2 i n n         . Chứng minh Xây dựng hàm :g   sao cho 2 2 1( ) x xg y x C y C    . Khi ấy 2 2 1 2( ) 2 x xg y x C y C      . Theo Định lí 1.3 ta có thể tìm được số i xác định bởi       3 11 2 1 2 1 2 2 2 i n x n g n n n n n                       là số chia tối ưu. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 68 §2 Đánh giá ( )pS n Như ta đã biết, số lần chuyển đĩa cho bài toán ba cọc là 3( ) 2 1 nS n   , nên sẽ tăng theo hàm mũ khi n tăng. Tuy nhiên, trong trường hợp số cọc 4p  , phân tích thuật toán Frame- Stewart, Stockmeyer 1994 [19] phát hiện ra rằng, thật đáng ngạc nhiên, là độ phức tạp của thuật toán là dưới mũ (sub- exponential), cỡ  2 nn cho 4k  . Đánh giá dưới đã được Xiao Chen và Jian Shen (2004) và Szegedy (1999) xét. Dưới đây chúng tôi trình bày kết quả của Stockmeyer [19]. Bổ đề 2.1 Kí hiệu  x là số nguyên gần số thực x nhất. Khi ấy 1k kt n t 