Tháp Hà Nội có 3 cái đĩa xếp trên một cọc, cần chuyển sang cọc khác, mỗi lần một đĩa, đĩa lớn không được đặt lên đĩa nhỏ. Cần ít nhất mấy lần chuyển?
Gợi ý
Muốn di chuyển đĩa to nhất, hai đĩa nhỏ phải nằm ở đâu?
Xem đáp án
Đáp án
7 lần
Lời giải
Chuyển 2 đĩa trên sang cọc phụ mất 3 lần, chuyển đĩa lớn nhất sang cọc đích 1 lần, rồi đưa 2 đĩa kia đè lên mất thêm 3 lần: 3 + 1 + 3 = 7. Tổng quát, n đĩa cần 2ⁿ − 1 lần.
Câu tiếp: Bàn cờ 6 × 6 ô có tất cả bao nhiêu hình vuông?