Trò chơi tháp Hà Nội và một số vấn đề toán học liên quan

Trò chơi tháp Hà Nội và một số vấn đề toán học liên quan Mao Thị Thu Hiền Trường Đại học Khoa học Tự nhiên Luận văn ThS Chuyên ngành: Phương pháp toán sơ cấp; Mã số 60 46 40 Người hướng dẫn: PGS. TS Tạ Duy Phượng Năm bảo vệ: 2013 Abstract. Trò chơi (Bài toán) Tháp Hà Nội được nhà toán học Edouard Lucas phát minh và phổ biến rộng rãi ở Paris năm 1883, là một bài toán nổi tiếng thế giới, hiện nay đang được nghiên cứu và phát triển 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 sách về trò chơi toán học và các giáo trình tin học như một ví dụ điển hình về thuật giải đệ qui và lập trình căn bản. Trò chơi Tháp Hà Nội không chỉ thú vị ở chỗ nó mang tên Hà Nội, thủ đô của Việt Nam. Trò chơi Tháp Hà Nội hấp dẫn các nhà nghiên cứu Toán học và Tin học bởi nó liên quan đến nhiều vấn đề của Toán-Tin học 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 mới trong toán học và khoa học máy tính Keywords. Toán học; Toán sơ cấp; Trò chơi toán học; Bài toán Tháp Hà Nội. MÐ ffi†U Trá chìi (B i to¡n) Th¡p H  Nëi ÷ñc nh  to¡n håc Edouard Lucas ph¡t minh v  phê bi¸n rëng r¢i ð Paris n«m 1883, l  mët b i to¡n nêi ti¸ng th¸ giîi, hi»n nay ang ÷ñc nghi¶n cùu v  ph¡t triºn 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 s¡ch v· trá chìi to¡n håc v  c¡c gi¡o tr¼nh tin håc nh÷ mët v½ dö iºn h¼nh v· thuªt gi£i » qui v  lªp tr¼nh c«n b£n. Trá chìi 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  cán h§p d¨n c¡c nh  nghi¶n cùu bði nâ li¶n quan ¸n nhi·u v§n · cõa To¡n-Tin håc 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 mîi trong to¡n håc v  khoa håc m¡y t½nh. 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 håc v  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 g¦n 200 t¤p ch½ khoa håc uy t½n (xem T i li»u tham kh£o trong [6]). ffiâ 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 ho°c nhúng cuèn s¡ch v· tin håc, trong â câ tr¼nh b y v· trá chìi Th¡p H  Nëi. 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 tin håc ti¸ng Vi»t, nh÷ng 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]-[7]) v  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. Ch½nh v¼ lþ do â, luªn v«n ÷ñc x¥y düng vîi möc ½ch tr¼nh b y v· làch sû ph¡t triºn trá chìi Th¡p H  Nëi còng mët sè v§n · to¡n håc li¶n quan. Luªn v«n gçm Ph¦n mð ¦u v  hai Ch÷ìng nëi dung. Ch÷ìng 1. Têng quan v· làch sû ph¡t triºn trá chìi Th¡p H  Nëi. Ch÷ìng 2. C¡c ph÷ìng ph¡p gi£i b i to¡n Th¡p H  Nëi. 5 Ch÷ìng 1 giîi thi»u têng quan v· làch sû ph¡t triºn 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 b¬ng c¡c cæng cö kh¡c nhau (thuªt gi£i » qui, h» ¸m cì sè 2, ç thà) ÷ñ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 hâa (trá chìi Th¡p H  Nëi vîi nhi·u cåc, trá chìi Th¡p H  Nëi vîi c¡c ¾a m u, trá chìi Th¡p H  Nëi vîi h¤n ch¸ h÷îng chuyºn ¾a, trá chìi Th¡p H  Nëi song song,...). 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. Luªn v«n công sì l÷ñc giîi thi»u c¡c mð rëng v  c£i bi¶n kh¡c nhau cõa b i to¡n Th¡p H  Nëi. T¡c gi£ xin b y tä láng bi¸t ìn s¥u s­c nh§t tîi PGS. TS T¤ Duy Ph÷ñng, ng÷íi ¢ truy·n thö ki¸n thùc v  h÷îng d¨n tªn t¼nh t¡c gi£ º ho n th nh luªn v«n n y. 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· trá chìi Th¡p H  Nëi. T¡c gi£ công xin ch¥n th nh c£m ìn c¡c th¦y cæ gi¡o khoa To¡n - Cì - Tin, tr÷íng ffi¤i håc tr÷íng ffi¤i håc Khoa håc Tü nhi¶n - ffiHQG H  Nëi còng b¤n b± v  ng÷íi th¥n ¢ âng gâp þ ki¸n, gióp ï, ëng vi¶n t¡c gi£ trong qu¡ tr¼nh håc tªp, nghi¶n cùu v  ho n th nh luªn v«n. H  Nëi, ng y 25 th¡ng 12 n«m 2011 Håc vi¶n: Mao Thà Thu Hi·n 6 T i li»u tham kh£o [1] Ph¤m Tr  …n, B i to¡n Th¡p H  Nëi, T¤p ch½ To¡n håc v  Tuêi tr´, sè 280, th¡ng 10-2000. [2] Ph¤m Tr  …n, B i to¡n Th¡p H  Nëi-C¡i nh¼n tø lþ thuy¸t ffië phùc t¤p t½nh to¡n, T¤p ch½ Thæng tin To¡n håc, Tªp 6, Sè 2, th¡ng 8-2002, trang 10-13. [3] Vô ffi¼nh Háa, B i to¡n Th¡p H  Nëi, T¤p ch½ To¡n Tuêi thì 2, Sè 68, th¡ng 10-2008. [4] 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 Cao håc, ffi¤i håc S÷ ph¤m Th¡i Nguy¶n, 2010. [5] T¤ Duy Ph÷ñng, Trá chìi Th¡p H  Nëi-Làch sû v  b i to¡n têng qu¡t, T¤p ch½ To¡n håc v  Tuêi tr´, sè 280, th¡ng 1-2010. [6] T¤ Duy Ph÷ñng, Trá chìi Th¡p H  Nëi: Làch sû v  nhúng v§n · To¡n-Tin håc li¶n quan, (B£n th£o), 150 trang, 2010. [7] Nguy¹n Xu¥n T§n, B i to¡n Th¡p H  Nëi-mët b i to¡n hâc bóa hìn mët tr«m n«m nay, T¤p ch½ Thæng tin To¡n håc, Tªp 6 Sè 1, th¡ng 3, 2002, trang 2-4. [8] E. Allardie and A. Y. Fraser, La Tour d'Hanoi, Proceeding of the Edinburgh Mathematical Society 2 (1884), 50-53. 72 [9] M. Atkinson, The cyclic Towers of Hanoi problem. Information Processing Letters, Vol. 13, No 3 (1981), 118-119. MR0645457 (83f:68004) . [10] W. W. Rouse Ball, Mathematical Recreations and Essays, Macmil- lan and Co., London, Sixth Edition, 1914. [11] Henry Ernest Dudeney, The Canterbury Puzzles (and other curi- ous problems), Thomas Nelson and Sons, Ltd., London, 1907; New York, E. P. Dutton and Company, 1908. [12] Otto Dunkel, Editorial note concerning advanced problem 3918, Amer. Math. Monthly 48 (1941), 219 [13] M. C. Er, The Colour Towers of Hanoi: A Generalization, The Computer Journal, Vol. 27 (1984), No. 1, 80-82. [14] J. S. Frame, Solution to advanced problem 3918. Amer. Math. Monthly 48 (1941), 216-217. [15] Ronal L. Graham, Donal E. Knuth, and Oren Patashnik, Concrete mathematics: A foundation for computer sciences. Addison-Wesley, Reading, MA, 1989. Second Edition, 1994. [16] Andreas M. Hinz, The Tower of Hanoi. Enseign. Math. (2) 35 (1989), 289-321. MR1039949 (91k:05015). [17] Andreas M. Hinz, Pascal's Triangle and the Tower of Hanoi, Amer- ican Mathematical Monthly, Vol. 99 No. 6, p. 538-544, June-July 1992. [18] E. I. Igratiev, Trong v÷ìng quèc s¡ng t¤o hay Sè håc cho måi ng÷íi, Quyºn 1, S.-Peterburg, 1914 (T¡i b£n l¦n thù t÷, ti¸ng Nga). [19] Zolt¡n K¡tai, Lehel Istv¡n Kov¡cs Tower of Hanoi-where program- ming techniques blend Acta Univ. Sapientiae, Informatica 1, 1 (2009), pp. 89-108. 73 [20] Sandi Klavzar, Uros Milutinovi
c, and Ciril Petr, On the Frame- Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Appl. Math. 120 (2002), no. 1-3, 141-157. MR1912864 (2003c:05028). [21] ’douard Lucas, Nouveaux jeux scientifiques de M. ’douard Lucas, La Nature, 17th year, 2nd semester (1889), no. 855 (October 5), 301-303.. [22] ’douard Lucas, L'Arithm²ique Amusante: Introduction aux R²cr²ations Mathematicques , Gauthier-Villars, Paris, 1895, pp. 179-183. [23] Henri de Parville, R²cr²ations math²matiques: La tour d'Hanoi et la question du Tonkin, La Nature, 12th year, 1st semester, no. 565 (March 29, 1884), 285-286. [24] David G. Poole, The towers and triangles of Professor Claus (Pas- cal knows Hanoi), Mathematics Magazine, 67 (1994), 323-344. [25] A. Sapir, The Towers of Hanoi with Forbidden Moves, The Com- puter Journal, 47 (1) (2004), 20-24. [26] R. S. Scorer, P. M. Grundy, and C. A, B. Smith, Some Binary games, Math. Gaz. 28 (1944), No 280 (July), 96-103. [27] B. M. Stewart, Advanced problem 3918, Amer. Math. Monthly 46 (1939), 363. [28] B. M. Stewart, Solution to advanced problem 3918 Amer. Math. Monthly 48 (1941), 217-219. [29] Paul K. Stockmeyer, Variations on the four-post Tower of Hanoi puzzle, Congr. Numer. 102 (1994), 3-12. 74 [30] Paul K. Stockmeyer, The Tower of Hanoi: A Bibliogra- phy, pkstoc/hpapers.html, Version 2.2, 22/10/2005. [31] P.K. Stockmeyer, Fred Lunnon, New Variations on the Tower of Hanoi, Thirteenth International Conference on Fibonaci Numbers and Their Applications, July 7-11, 2008, Patras, Greece. [32] Yu-Kuo Wang, Analysis on an Iterative algorithm of The Tower of Hanoi problem with Parallel Moves, M. Sc. Thesis, Institute of Computer Science and Information Engineering, Chung Hoa Uni- versity, 1999. [33] Derick Wood, Towers of Brahma and Hanoi Revisited, J. Recr. Math. 14(1981), No 1, 17-24. MR 0629340 (82i:68031). 75