Tháp Hà Nội ngược

Nội dung giống như bài toán tháp Hà Nội cổ chỉ sửa lại quy tắc (2) như sau: (2) Mỗi lần chỉ được chuyển 1 tầng tháp từ một cọc sang cọc sát nó về hướng ngược chiều kim đồng hồ.

Điều kiện này quy định ba phép chuyển 1 tầng tháp như sau:

 3 ¬ 2, hoặc  1 ¬ 2, hoặc  1 ¬ 3.

Hãy tìm cách giải bài toán với số lần chuyển ít nhất.

Bài giải

Bài này tương tự như bài Hà Nội xuôi. Ta chỉ cần xác định điều kiện kề giữa hai cọc tháp và lưu ý đến chiều chuyển các tầng tháp ngược chiều quay của kim đồng hồ.

a) Trường hợp vị trí b đứng sát vị trí a ngược chiều kim đồng hồ:

Theo trường hợp này ta có các cặp (a, b) sau đây: (3, 2), (2, 1) và (1, 3).

Hoán đổi vị trí của hai đại lượng a và b trong điều kiện kề của bài toán Hà Nội xuôi ta thu được điều kiện kề trong trường hợp này là

a = (b mod 3)+1

Tình huống	j	k	l
1	a		b
2	b	a
3		b	a
Tháp Hà Nội ngược Đặc tả a và b kề nhau a = (b mod 3) + 1

Với ý nghĩa là, nếu biết mã số vị trí a thì vị trí b sát sau a ngược chiều kim đồng hồ sẽ được tính theo công thức trên.

Dựa vào các hình trạng buộc phải có ta có thể mô tả việc chuyển tháp trong trường hợp này giống như trong bài toán tháp Hà Nội xuôi, cụ thể là:

Hình trạng	Ý nghĩa	Lệnh
(a: [1..n], b: [ ], c: [ ])	Hình trạng ban đầu với vị trí b sát vị trí a. a = (b mod 3) + 1 Để chuyển n tầng từ a sang b ngược chiều kim đồng hồ ta phải...
...
(a: [n], b: [ ], c: [1..n - 1])	Chuyển (tạm) n - 1 tầng từ a qua c = 6 - a - b.	Hnn(n - 1, a, 6 - a - b)
(a: [ ], b: [n], c: [1..n - 1])	sau đó chuyển tầng còn lại của a qua b.	a ® b
...
(a: [ ], b: [1..n], c: [ ])	Cuối cùng chuyển n - 1 tầng từ c = 6 - a - b qua b là hoàn tất.	Hnn(n - 1, 6 - a - b, b)

Đoạn trình cho trường hợp này sẽ là

if a = (b mod 3)+1 then

begin {b ke a}

hnn(n-1,a,6-a-b);

inc(d);

writeln(f,d,'. ',a,' -> ',b);

hnn(n-1,6-a-b,b);

end…

b) Trường hợp vị trí b không đứng sát vị trí a theo chiều ngược kim đồng hồ:

Các cặp (a, b) khi đó sẽ là: (1, 2), (2, 3) và (3, 1). Đặc điểm chung của các cặp này là: nếu đi từ a đến b ngược chiều kim đồng hồ chúng ta phải vượt qua c là vị trí nằm giữa a và b.

Tình huống	j	k	l
1	a	b
2		a	b
3	b		a
Tháp Hà Nội ngược Đặc tả a và b không kề nhau a ¹ (b mod 3) + 1

       Các hình trạng buộc phải có khi đó sẽ rất giống với tình huống tương tự của bài toán Hà Nội xuôi:

Hình trạng	Ý nghĩa	Lệnh
(a: [1..n], c: [ ], b: [ ])	Hình trạng ban đầu với vị trí b cách a qua c ngược chiều kim đồng hồ. a ¹ (b mod 3) + 1 Để chuyển n tầng từ a sang b cách qua vị trí c = 6 - a - b ta phải...
...
(a: [n], c: [ ], b: [1..n - 1]	Chuyển (tạm) n - 1 tầng từ a qua b.	Hnn(n - 1, a, b)
(a: [ ], c: [n], b: [1..n - 1])	sau đó chuyển (tạm) tầng còn lại của a qua c = 6 - a - b.	a ® 6 - a - b
...
(a: [1..n-1], c: [n], b: [ ])	Rồi lại chuyển (tạm) n - 1 tầng từ b qua a nhằm giải phóng vị trí đích b...	Hnn(n - 1, b, a)
(a: [1..n-1], c: [ ], b: [n])	để chuyển tầng lớn nhất n từ c qua b.	6 - a - b ® b
(a: [ ], c: [ ], b: [1..n])	Cuối cùng chuyển n - 1 tầng từ a qua b là hoàn tất.	Hnx(n - 1, a, b)

(*  Pascal  *)

(**************************************

Hano.pas – Hà Nội Ngược

Chuyển pháp ngược chiều kim đồng hồ.

*************************************)

uses crt;

var d: longint;

f: text;

procedure hnn(n,a,b: byte);

begin

if n = 0 then exit;

if a = (b mod 3)+1 then

begin {b ke a}

hnn(n-1,a,6-a-b);

inc(d);

writeln(f,d,'. ',a,' -> ',b);

hnn(n-1,6-a-b,b);

end

else {b cach a qua vi tri c}

begin

hnn(n-1,a,b);

inc(d);

writeln(f,d,'. ',a,' -> ',6-a-b);

hnn(n-1,b,a);

inc(d);

writeln(f,d,'. ',6-a-b,' -> ',b);

hnn(n-1,a,b);

end;

end;

procedure runhnn(n: byte);

begin

d :=  0;

assign(f,'hnn.out');

rewrite(f);

writeln('-----------------');

hnn(n,1,2);

writeln(f,'Total: ',d,' step(s)');

close(f);

readln;

end;

BEGIN

runHnn(3);

END.

Kết quả:

1. 1 -> 3 2. 3 -> 2 3. 1 -> 3 4. 2 -> 1 5. 3 -> 2 6. 1 -> 3 7. 3 -> 2 8. 1 -> 3 9. 2 -> 1 10. 1 -> 3 11. 2 -> 1

12. 3 -> 2 13. 2 -> 1 14. 3 -> 2 15. 1 -> 3 16. 3 -> 2 17. 1 -> 3 18. 2 -> 1 19. 3 -> 2 20. 1 -> 3 21. 3 -> 2 Total: 21 step(s)

Nhận xét

Mới xem ta có cảm tưởng rằng lời gọi Hnn(3,1,2) và Hnx(3,1,2) để chuyển tháp 3 tầng từ cọc 1 sang cọc 2 phải cho cùng một số bước chuyển các tầng là 15. Tuy nhiên, lời gọi Hnn(3,1,2) cho ta 21 bước chuyển các tầng, trong khi lời gọi Hnx(3,1,2) chỉ cần 15 bước chuyển các tầng.

Suy ngẫm một chút bạn sẽ giải thích được nghịch lí này.

Hãy thử gọi Hà Nội ngược để chuyển tháp 3 tầng từ cọc 3 sang cọc 2:

Hnn(3,3,2)

Ta sẽ thấy chỉ cần 15 bước!!!

Lại gọi Hà Nội xuôi để chuyển tháp 3 tầng từ cọc 1 sang cọc 3:

Hnx(3,1,3)

Ta lại thấy 21 bước.

Như vậy, Hnx và Hnn là đối xứng lệch. Nếu hai cọc, nguồn và đích kề nhau thì số lần chuyển tháp 3 tầng sẽ là 15. Ngược lại, khi hai cọc đó không kề nhau thì số lần chuyển tháp 3 tầng sẽ là 21. Hai cọc 1 và 2 là kề nhau đối với tháp Hà Nội xuôi nhưng không kề nhau đối với tháp Hà Nội ngược. Tương tự, hai cọc 3 và 2 là kề nhau đối với tháp Hà Nội ngược nhưng không kề nhau đối với tháp Hà Nội xuôi.

Ta nhận xét rằng: nếu lấy hai số a, b khác nhau bất kì trong ba số 1, 2 và 3 thì giữa a và b chỉ xảy ra một trong hai trường hợp loại trừ nhau sau đây:

b = (a mod 3) +1, hoặc a = (b mod 3)+1

Do đó, quan hệ kề nhau trong hai bài toán Tháp Hà Nội xuôi và ngược là phủ định đối với nhau.

	Hà Nội xuôi	Hà Nội ngược
b = (a mod 3)+1	a và b kề nhau	a và b không kề nhau
a = (b mod 3)+1	a và b không kề nhau	a và b kề nhau
Quan hệ kề nhau trong hai bài toán tháp Hà Nội xuôi và ngược