Thuật toán Frame – Stewart giải bài toán tháp Hà Nội tổng quát

o 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   khi và chỉ khi  2k n , trong đó ( 1) 2 k k k t   là các số Pascal. Chứng minh Ta có  2k n  1 1 2 2 2 k n k     2 21 12 4 4 k k n k k       1 1 1 8 8 k kt n t      1k kt n t   . Dấu bằng trong bắt đẳng thức cuối là do tất cả các số 1, ,k kt n t đều là những số nguyên. Nhận xét rằng từ Bổ đề này suy ra rằng  2n chính là giá trị tối ưu của tham số i trong thuật toán. Định lí 2.1 Giả sử  2 2n n   , tức là 1 1 2 2    . Khi ấy  24( ) 2 1nS n n    , trong đó   1 2 3 2 2 4              và   2 3 4 2 4             . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 69 Chứng minh Giả sử  2 2k n n    . Sử dụng các Hệ quả 1.1 và 1.2. và tính tổng ta có           1 1 1 4 1 2 2 2 2 ( 1 ( ) 2 2 1 2 1 2 2 2 3 4 3 2 3 4 2 1 2 2 1 4 4 4 2 1. k i k k k k i k n n k k S n i t n k n n k k n n                                                    Đây chính là điều phải chứng minh. Mặc dù   1 2 3 2 2 4              và   2 3 4 2 4              có dạng phức tạp, cả hai đều rất gần với 1 khi 1 1 2 2    . Hàm    đạt giá trị cực tiểu bằng 1 khi 1 2    và đạt cự đại bằng 2 1.0615 ln 2e  tại 3 1 0.0573 2 ln 2     . Hàm    giảm chặt từ cực đại bằng 23 2 1.0164 32  tại 1 2    đến cực tiểu bằng 11 2 0.9723 16  tại 1 2   . Nếu kn t là số tam giác thì ta có 1 lim 2n     . Như vậy,  2( ) 2 1 1nM n n   là xấp xỉ tốt nhất cho các số này. Trong mọi trường hợp, ( )M n luôn luôn không xa quá 6.2% so với 22 nn với n đủ lớn. Ta nhận xét rằng 22 nn thật sự tăng nhanh hơn 2 nn , do đó Krishnamoorthy và Biswas đã chứng minh rằng  ( ) 2 nM n O n . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 70 §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 Trong §1 ta đã xét khá tỉ mỉ một thuật toán truy hồi giải bài toán Tháp Hà Nội tổng quát (thuật toán Frame-Stewart, thực ra đó là thuật toán do Stewart đề nghị năm 1942). Frame (1941) cũng đã đưa ra một thuật toán khác với thuật toán Stewart. Sau này, một số tác giả đã đưa ra một số thuật toán truy hôi tương tự các thuật toán của Stewart và Frame. Trong § này chúng ta sẽ trình bày chứng minh trong [11] khẳng định rằng các thuật toán này là tương đương theo nghĩa số lần chuyển đĩa tối ưu trong các thuật toán này là bằng nhau. 3.1 Các thuật toán truy hồi Giả sử ( )pH n là số bước chuyển nhỏ nhất cần thiết để giải bài toán Tháp Hà Nội với n đĩa và p cọc. Chỉ với 4p  và n p đĩa thì bài toán Tháp Hà Nội với nhiều cọc mới không tầm thường, bởi vì ta đã chứng minh được rằng (Chương 2) 3( ) 2 1 nH n   và hiển nhiên ( ) 2 1pH n n  khi n p (lần lượt lấy từng đĩa từ nhỏ tới lớn từ cọc nguồn đặt vào từng cọc, nhấc đĩa cuối cùng từ cọc nguồn đặt vào cọc đích, sau đó lại lần lượt xếp các đĩa vào cọc đích theo thứ tự từ lớn đến bé, xem Nhận xét 2.1 Chương 3). Do đó trong trường hợp tầm thường 3p  hoặc n p ta sẽ kí hiệu tất cả các hàm được xem xét ở đây là được xác định như là ( )pH n . Vì lí do kĩ thuật, ta coi 2(1) 1H  và 2( ) 0H n  khi 2n  . Thuật toán Frame (1941) Đầu tiên tất cả n đĩa đều nằm trên cọc nguồn 1P . Ta chia 1n  đĩa nhỏ nhất thành 2p  nhóm đĩa có kích thước liên tiếp. Chuyển 1n đĩa nhỏ nhất (trên cùng) từ cọc nguồn 1P sang cọc trung gian 2P bằng cách sử dụng tất cả Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 71 p cọc. Chuyển 2n đĩa nhỏ hơn (tiếp theo) từ đĩa nguồn 1P sang đĩa trung gian 3P bằng cách sử dụng 1p  cọc (không sử dụng cọc 2P vì cọc 2P đang chứa 1n đĩa nhỏ nhất). Tiếp tục chuyển các nhóm đĩa từ cọc nguồn sang các cọc trung gian bằng cách tại mỗi bước ta sử dụng ít hơn một cọc so với bước trước. Nhóm đĩa cuối cùng được chuyển từ cọc nguồn 1P sang cọc trung gian 1pP  bằng cách sử dụng ba cọc trung gian còn lại. Đĩa lớn nhất (thứ n ) khi ấy được chuyển từ cọc nguồn 1P sang cọc đích pP . Sau đó ta chuyển tất cả các nhóm đĩa sang cọc đích theo thứ tự ngược lại. Như vậy, bài toán tìm số lần chuyển nhỏ nhất n đĩa từ cọc nguồn sang cọc đích trở thành Bài toán 3.1 Với 4p  và n p tìm cực tiểu ( )pF n của đại lượng      1 1 2 3 22 2 ... 2 1p p pF n F n F n       với điều kiện 1 2 2... 1pn n n n     , in  , ,2,..., 2i p  . Bài toán trên là một dạng nới lỏng của bài toán Frame ban đầu: Bài toán 3.2 Với 4p  và n p , tìm cực tiểu ( )pF n của đại lượng      1 1 2 3 22 2 ... 2 1p p pF n F n F n     với điều kiện 1 2 2... 1pn n n n     , 1 2 2... pn n    , trong đó in  . Như vậy, so với bài toán 3.1, thuật toán Frame (Bài toán 3.2) đòi hỏi thêm một điều kiện đơn điệu của số đĩa: 1 2 2... pn n n    . Dưới đây, để thuận tiện, ta nhắc lại Thuật toán Stewart (1941) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 72 Đầu tiên tất cả n đĩa đều nằm trên cọc nguồn 1P . Chia các đĩa thành hai nhóm. Nhóm thứ nhất gồm 1n đĩa nhỏ nhất và nhóm thứ hai gồm 1n n đĩa còn lại. Chuyển 1n đĩa nhỏ nhất từ cọc nguồn 1P sang cọc trung gian 2P bằng cách sử dụng tất cả p cọc. Chuyển 1n n đĩa còn lại từ cọc nguồn 1P sang cọc đích pP bằng cách sử dụng 1p  cọc (không sử dụng cọc 2P ). Cuối cùng chuyển 1n đĩa từ cọc 1P sang cọc đích pP , sử dụng tất cả p cọc. Bài toán 3.3 Với 4p  và n p , tìm     1 1 2 1 2( ) : min 2p p pS n S n S n n n n    , trong đó in  , 1,2i  . Thuật toán Stewart có thể được tổng quát hóa như sau. Kí hiệu ( )pA n là số bước chuyển cần thiết trong Bài toán 2 theo thuật toán có tính đến tất cả các phép chia n đĩa sau đây. Bài toán 3.4 Với 4p  và n p , giả sử ( )pA n là cực tiểu của số       1 1 2 3 2 1 2 1 1 2 3 2 1 2 1 2 1 2 2 ( ) 2 ( ) ... 2 ( ) 1 ... 1 2 ( ) 2 ( ) ... 2 ( ) ... ... 2 ( ) 2 ( ) , p p p p p p p p p p A A n A n n n n A n A n A n n n n A n A n n n n                                trong đó in  . Một phiên bản của 3.4 nhưng đòi hỏi tính đơn điệu của phép chia n đĩa là Bài toán 3.5 Với 4p  và n p , tìm cực tiểu ( )pA n của số (trong đó in  )       1 1 2 3 2 1 2 1 2 1 1 2 3 2 1 2 1 2 1 1 2 1 2 1 2 2 ( ) 2 ( ) ... 2 ( ) 1 ... 1 , ... 2 ( ) 2 ( ) ... 2 ( ) ... , ... ... ... 2 ( ) 2 ( ) , . p p p p p p p p p p A A n A n n n n n n A n A n A n n n n n n A n A n n n n n n                                   Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 73 Định nghĩa 3.1 Nếu 2,3p  hoặc n p thì đặt (định nghĩa) ( ) ( ) ( ) ( ) ( ) ( )p p p p p pF n F n A n A n S n M n      . 3.2 Chứng minh ( ) ( ) ( )p p pA n F n S n   Chúng ta bắt đầu bằng hai Bổ đề về hàm ( )pA n . Mặc dù Bổ đề 3.1 cũng khá hiển nhiên và Bổ đề 3.2 chủ yếu là xét trường hợp tầm thường, tuy nhiên cũng cần chứng minh hai Bổ đề này, bởi vì một số “điều hiển nhiên” trong bài toánTháp Hà Nội thường đưa đến các kết luận sai lầm. Bổ đề 3.1 Với mọi 3p  và 1n  ta có ( ) 2 1pA n n   . Chứng minh Với n p Bổ dề đúng theo định nghĩa của ( )pA n . Với 3p  và 3n  ta có 3( ) 2 1 2 1 nA n n     . Cuối cùng, với 4p  và n p ta có 1 1 2 1 1( ) 2 ( ) 2 ( ) ... 2 ( ) ( )p p p i p i i p iA n A n A n A n A n             , trong đó 1 2 1... p in n n n     và 2 2i p   . Theo qui nạp ta có               1 1 1 1 1 1 ( ) 2 2 1 ... 2 1 2 1 2 ... 2 ... 2 1 2 2 ... 2 2 1. p p i p i p i p i p i p i p i A n n n n n n n n n n p i n n n p i n                                       Bổ đề được chứng minh. Bổ đề 3.2 Với mọi 1n  , 3p  và 1 1, ,..., p ii n n   với 2 1i p   và 1 2 1... p in n n n      : 1 1 2 1 1( ) 2 ( ) 2 ( ) ... 2 ( ) ( )p p p i p i i p iA n A n A n A n A n             . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 74 Chứng minh Trường hợp 4p  và n p : Khẳng định được suy ra trực tiếp từ định nghĩa số ( )pA n . Trường hợp 3p  : Từ 2 1i p   suy ra 2i  . Ta phải chứng minh 3 3 1 2 2( ) 2 ( ) ( )A n A n A n    , 1 2n n n . (3.1) Nếu 2 2n  thì (3.1) suy biến. Vậy 2 1n  và ta chỉ còn phải chứng minh 3 3 2( ) 2 ( 1) (1)A n A n A     Theo định nghĩa ta có: (3.1)  3 3 1 2 2( ) 2 ( ) ( )M n M n M n     12 1 2 2 1 1nn     . Hiển nhiên đúng. Trường hợp cuối cùng: n p và 4p  . Ta sẽ chứng minh bằng truy hồi theo n . Nếu 2n  thì 1 2 12 ... 1p in n n n p i         (vì 1in  với mọi i ). Như vậy, 1p i  . Mặt khác ta lại có 1p i p n    nên suy ra 1p i  . Do đó 1 2 1n n  . Như vậy chỉ còn phải chỉ ra là 1(2) 2 (1) (1)p p pA A A     , hiển nhiên vì theo định nghĩa khi n p thì (2) (2) 2.2 1 3p pA M     ; (1) (1) 1p pA M   ; 1 1(1) (1) 1p pA M    . Như vậy, trường hợp 2n  được chứng minh. Theo qui nạp ta suy ra:  1 1 2 1 1 1 1 12 ( ) 2 ( ) ... 2 ( ) ( ) 2 ( ) ( ).p p i p i i p i p pA n A n A n A n A n A n n                 Do đó khẳng định được chứng minh nếu ta chỉ ra rằng 1 1 12 ( ) ( ) ( )p p pA n A n n A n     . Do n p nên theo định nghĩa ta có ( ) ( ) 2 1p pA n M n n    . Vậy theo Bổ đề 3.1:         1 1 1 1 1 1 1 1 2 ( ) ( ) 2 2 1 2 1 2 2 3 2 1 ( ). p p p A n A n n n n n n n n n n A n                  Bổ đề 3.2 được chứng minh. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 75 Mệnh đề 3.3 Với mọi 3p  và 1n  ta có ( ) ( )p pA n S n  . Chứng minh Ta sẽ chứng minh bằng qui nạp theo n . Cụ thể hơn, ta sẽ đi chứng minh rằng khẳng định đúng với mọi 4n  và, khi n cố định thì nó đúng với mọi 4 p n  . Với 4n  , ta chỉ cần xét 4p  . Tính toán đơn giản và trực tiếp chỉ ra rằng trong trường hợp này ta có 4 4(4) (4) 9A S   . Bây giờ ta giả sử rằng khẳng định đúng với mọi 4 m n  . Giả sử p là số nguyên bất kì thỏa mãn 4 p n  . Theo giả thiết qui nạp, với mọi 1 2,n n  , 1 2n n n  ta có 1 1 2 1 1 22 ( ) ( ) 2 ( ) ( )p p p pA n A n S n S n     . Như vậy, tập mà theo đó chúng ta xác định ( )pS n (như là cực tiểu của nó) là tập con của tập, mà theo đó chúng ta xác định ( )pA n (như là cực tiểu của nó) . Từ đây suy ra rằng ( ) ( )p pA n S n  . Còn lại cần phải chứng minh rằng ( ) ( )p pA n S n  . Nếu với 1 2,n n  , 1 2n n n  nào đó, ta có 1 1 2( ) 2 ( ) ( )p p pA n A n A n    thì ta có điều phải chứng minh, vì trong trường hợp này ( )pA n là tập mà ( )pS n đạt cực tiểu. Bởi vậy ta giả thiết rằng 1 1 2 1 1( ) 2 ( ) ( ) ... 2 ( ) ( )p p p i p i i p iA n A n A n A n A n             , trong đó 1 2 1... p in n n n     và 2 2i p   . (Nhận xét rằng trong trường hợp riêng 2i  ta có 1 1 1p i pn n    và 2 1( ) 1pA n   .) Khi đó 2 3 1 1... p in n n n n      . Theo Bổ đề 3.2 ta có 1 1 1 2 1 1( ) 2 ( ) ... 2 ( ) ( )p p i p i i p iA n n A n A n A n             , Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 76 Và vì vậy, sử dụng giả thiết qui nạp, ta đi đến kết luận 1 1 1 1 1 1( ) 2 ( ) ( ) 2 ( ) ( ) ( )p p p p p pA n A n A n n S n S n n S n          . Vậy ( ) ( )p pA n S n  . Mệnh đề 3.4 Với mọi 3p  và 1n  ta có ( ) ( )p pA n F n  . Chứng minh Ta sẽ chứng minh bằng qui nạp theo n như trong Mệnh đề 3.3. Với 4n  ta có            4 4 1 3 2 1 2 4 1 3 2 1 2 4 3 4 3 4 (4) min 2 ( ) 2 ( ) 1 1 4 min 2 ( ) 2 ( ) 1 3 min 2 (1) 2 (2) 1;2 (2) 2 (1) 1 min 2 1 3 1,2 3 1 1 9 (4). F F n F n n n A n A n n n A A A A A                              Giả thiết rằng ( ) ( )p pA m F m  với mọi 4 m n  . Tập mà theo đó ta xác định ( )pF n (như là cực tiểu của nó) là tập con của tập theo đó ta xác định ( )pA n (như là cực tiểu của nó), bởi vì với mọi 1 2 2, ,..., pn n n  thỏa mãn 1 2 2... 1pn n n n     ta có 1 3 2 1 3 22 ( ) ... 2 ( ) 1 2 ( ) ... 2 ( ) 1p p p pF n F n A n A n           . Do đó ( ) ( )p pF n A n  . Để chứng minh bất đẳng thức ngược lại, chúng ta sử dụng phương pháp qui hoạch động như sau. Theo Mệnh đề 3.3 ta có thể viết 0 1 1 2( ) 2 ( ) ( )p p pA n A n A n    trong đó 0 1 2n n n  . Áp dụng một lần nữa lý luận này, ta có 0 0 1 2 1 2 2 3( ) 2 ( ) ( )p p pA n A n A n      trong đó 0 0 2 3 2n n n  . Vậy 0 1 1 2 2 3( ) 2 ( ) 2 ( ) ( )p p p pA n A n A n A n       . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 77 Quá trình này có thể thực hiện đến khi nào? Chúng ta phân biệt hai trường hợp. Trƣờng hợp 1 0 1 1 1( ) 2 ( ) ... 2 ( ) ( )p p i p i i p iA n A n A n A n          với 2i  và 0 1 1p in    . Đặt  max 1kr k n  và nhận xét rằng r p i  . Khi ấy ta có:   1 1 1 1 1 1 1 1 1 1 1 1 ( ) 2 ( ) ... 2 ( ) 2 (1) ... 2 (1) 2 (1) 2 ( ) ... 2 2 ( ) ( ) 2 (1) ... 2 (1) (1) 2 ( ) ... 2 ( ) 2 ( ) 2 (1) ... 2 p p i p i p r i i p p r r p r r p r i i p p r r p r r p r A n A n A n A A A A n A n A n A A A A n A n A n A A                                                        1(1) (1) ( ).i i pA A n   Nhận xét rằng trong tính toán trên đổi biến trong đẳng thức thứ hai là có thể bởi vì mọi giá trị của (1),..., (1)p r iA A  cũng như là 1 1(1),..., (1)p r iA A    bằng 1 và 1 2i   . Do đó ta có mâu thuẫn. Chứng tỏ trường hợp này là không thể. Trƣờng hợp 2 0 1 1 1( ) 2 ( ) ... 2 ( ) ( )p p i p i i p iA n A n A n A n          với 2i  và 0 1 1p in    . Ta có 0 0 1 3 2 1 3 2( ) 2 ( ) ... 2 ( ) 1 2 ( ) ... 2 ( ) 1 ( ).p p p p p pA n A n A n F n F n F n               Vậy Mệnh đề 3.4 được chứng minh. Kết hợp Mệnh đề 3.3 và Mệnh đề 3.4 ta có thể phát biểu Hệ quả 3.5 Với mọi 3p  và 1n  ta có ( ) ( ) ( ) ( )p p p pA n F n S n H n    . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 78 KẾT LUẬN Trong luận văn này, ngoài Chương 1 trình bày sơ lược lịch sử phát triển của bài toán Tháp Hà Nội và Chương 2 trình bày chi tiết các lời giải bài toán tháp Hà Nội với ba cọc, chúng tôi tập trung trình bày một vấn đề quan trọng trong bài toán tháp Hà Nội tổng quát, đó là các công thức tính số lần chuyển tối ưu, độ phức tạp tính toán và sự tương đương của các các thuật toán hồi qui dạng Frame-Stewart. Mặc dù còn rất sơ lược và chưa bao quát hết được số lượng lớn các bài viết chỉ riêng về thuật toán Frame-Stewart giải bài toán tháp Hà Nội, hy vọng luận văn cũng đã cho một bức tranh tương đối rõ nét về bài toán này và gợi ý sự quan tâm đến các vấn đề thú vị của bài toán tháp Hà Nội, nhân dịp 1000 năm Thăng Long. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 79 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 Độ 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 năm 2002, trang 10-13. [3] Vũ Đì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] 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. [5] Tạ Duy Phượng, Trò chơi Tháp Hà Nội và những bài toán liên quan (Bản thảo), 150 trang. [6] 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 năm 2002, trang 2-4. [7] Henry Ernest Dudeney, The Canterbury Puzzles (and other curious problems), Thomas Nelson and Sons, Ltd., London, 1907; New York, E. P. Dutton and Company, 1908. [8] Otto Dunkel, Editorial note concerning advanced problem 3918, Amer. Math. Monthly 48 (1941), 219. [9] J. S. Frame, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941), 216-217. [10] P. J. Hilton, private communication. [11] Sandi Klavžar, Uroš Milutinović, 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) [12] Édouard Lucas, L’Arithméique Amusante: Introduction aux Récréations Mathematicques, Gauthier-Villars, Paris, 1895, pp. 179-183. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 80 [13] Sergey Novikov, Upper estimates of complexity of algorithms for multi- peg Tower of Hanoi problem, Annales Academiae Paedagogicae Cracoviensis, Folia 45 Studia Mathematica VI, 2007, pp. 57-66. [14] Henri de Parville, Récréations mathématiques: La tour d ’ Hanoi et la question du Tonkin, La Nature, 12 th year, 1 st semester, no. 565 (March 29, 1884), 285-286. [15] David G. Poole, The towers and triangles of Professor Claus (or, Pascal knows Hanoi), Math. Mag. 67 (1994), 323-344. MR1307797 (95m:05023) [16] Michel Rand, On the Frame-Stewart algorithm for the Tower of Hanoi, pp. 1-13, 2009. [17] B. M. Stewart, Advanced problem 3918, Amer. Math. Monthly 46 (1939), 363. [18] B. M. Stewart, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941), 217-219. [19] Paul K. Stockmeyer, Variations on the four-post Tower of Hanoi puzzle, Congr. Numer. 102 (1994), 3-12. (Proceedings of the 25th Southeastern International Conference on Combinatorics, Graph Theory and computing). [20] Paul K. Stockmeyer: The Tower of Hanoi: A Bibliography, Internet publication, Version 2.2, 22/10/2005, [21] Workshop on the Tower of Hanoi and Related Problems, September 18 - September 22, 2005, Maribor, Slovenia. [22] Các bài trên các trang WEB viết về trò chơi Tháp Hà Nội.