Tháp Hà Nội và quy tắc chuyển đĩa

Chỉ chuyển đĩa trên cùng

Có ba cọc khác nhau và n đĩa, với n≥1. Đĩa được đánh số từ 1 đến n theo kích thước tăng dần: đĩa 1 nhỏ nhất. Ban đầu tất cả ở cọc nguồn, đĩa nhỏ nằm trên đĩa lớn. Cần đưa cả chồng sang cọc đích, dùng cọc còn lại làm trung gian. Mỗi lần chỉ chuyển **một đĩa trên cùng** của một cọc. Có thể đặt lên cọc rỗng hoặc trên một đĩa lớn hơn; không đặt đĩa lớn lên đĩa nhỏ. Vì vậy không thể lấy đĩa dưới khi đĩa trên chưa được chuyển đi.

Hai đĩa cần ba lần chuyển

Đọc từ trên xuống: ban đầu, sau bước 1, sau bước 2 và sau bước 3. Đĩa 1 luôn được đặt trên đĩa lớn hơn hoặc cọc rỗng.

Để chuyển hai đĩa từ cọc 1 sang cọc 3, trước hết đưa đĩa 1 sang cọc 2 để lộ đĩa 2. Chuyển đĩa 2 sang cọc 3, rồi đưa đĩa 1 từ cọc 2 lên trên đĩa 2. Kí hiệu `d: i → j` nghĩa là chuyển đĩa d từ cọc i sang cọc j. Ba lần chuyển là `1: 1→2`, `2: 1→3`, `1: 2→3`. Hình minh họa gồm trạng thái ban đầu và trạng thái sau mỗi lần chuyển.

Bài luyện

Ban đầu hai đĩa xếp trên cọc 1, đĩa 1 ở trên đĩa 2; cọc 2 và 3 rỗng. Thao tác nào hợp lệ?

AChuyển đĩa 1 từ cọc 1 sang cọc 2.BChuyển đĩa 2 từ cọc 1 sang cọc 3 ngay.CChuyển đồng thời cả hai đĩa sang cọc 3.DChuyển đĩa 2 từ cọc 2 sang cọc 3.

Bài luyện

Dãy nào đưa đúng hai đĩa từ cọc 1 sang cọc 3 theo hình?

A1: 1→3; 2: 1→2; 1: 3→2.B1: 1→2; 2: 1→3; 1: 2→3.C2: 1→3; 1: 1→3.D1: 1→3; 2: 1→3.