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
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ì.
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.
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ố S p (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á S p (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
82 trang |
Chia sẻ: maiphuongtl | Lượt xem: 1780 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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.
Các file đính kèm theo tài liệu này:
- LV2010_SP_NguyenThiHongPhuong.pdf