Hãy chứng minh công thức H(n) = 2^n-1  bằng quy nạp toán học. Hãy tính H(64) và so sánh

Hãy chứng minh công thức Hn = 2n1 bằng quy nạp toán học. Hãy tính H(64) và so sánh với con số các bước đã được đưa ra trong tờ quảng cáo của trò chơi vào năm 1883.

Trả lời

- Nếu chỉ có một đĩa (n=1), H(n) = 1.

- Nếu có n đĩa, để chuyển tất cả các đĩa từ tháp ban đầu sang tháp đích, ta phải thực hiện các bước sau:

Chuyển n-1 đĩa từ tháp ban đầu sang tháp trung gian.

Chuyển đĩa cuối cùng (đĩa lớn nhất) từ tháp ban đầu sang tháp đích.

Chuyển n-1 đĩa từ tháp trung gian sang tháp đích.

Số bước chuyển tất cả các đĩa là H(n) = 2 * H(n-1) + 1.

- Ta sẽ chứng minh công thức này bằng phương pháp quy nạp toán học:

Bước 1: Giả sử công thức đúng với n-1, tức là H(n-1) = 2^(n-1) - 1

Bước 2: Chứng minh công thức đúng với n, tức là H(n) = 2^n - 1

Ta có:

H(n) = 2 * H(n-1) + 1 (theo công thức đề bài)

= 2 * (2^(n-1) - 1) + 1 (theo giả sử ở bước 1)

= 2^n - 2 + 1

= 2^n - 1

Vậy ta đã chứng minh được công thức đúng với mọi n.

Để tính H(64), ta áp dụng công thức đã chứng minh:

H(64) = 2^64 - 1

= 18446744073709551615

Vậy H(64) = 18446744073709551615 trùng với con số ở trên bài báo

Câu hỏi cùng chủ đề

Xem tất cả