Tìm Số Cách Đi

General method / Cách làm tổng quát

• Đếm số cách đi tới các giao điểm đầu tiên. Thông thường, các điểm cùng hàng hoặc cùng cột với điểm xuất phát mà ta có thể đi đến được sẽ có số cách đi tới là 1.
• Số cách đi tới 1 điểm bất kì sẽ bằng tổng số cách đi tới các điểm liền trước nó.
• Tiếp tục thực hiện bước 2 tới khi đến được đích.

Lưu ý:

• Đối với các điểm chỉ có duy nhất một điểm liền trước thì số cách tới điểm đó giữ nguyên (không cần cộng).
• Trong bài toán trắc nghiệm, để làm nhanh chóng, thuận tiện và chính xác, ta có thể viết luôn số cách lên hình vẽ thay vì đặt tên điểm.

Example / Ví dụ

Given the map below. Andy wants to go from point A to point B. He can only move up or move right along the lines. How many ways are there?

Cho bản đồ dưới đây. Andy muốn đi từ điểm A đến điểm B. Anh ấy chỉ có thể đi lên trên hoặc đi sang phải dọc theo đường thẳng. Hỏi có bao nhiêu cách đi khác nhau?

Cách 1: (Đối với bài tự luận)

Andy chỉ có thể đi lên trên và đi sang phải (KHÔNG THỂ đi xuống hoặc đi xuống trái).

Ta đặt tên cho các điểm như trong hình sau:

Bắt đầu từ diểm A, ta có:

• Số cách đến điểm C là: 1 cách.
• Số cách đến điểm D là: 1 cách.
• Số cách đến điểm G là: 1 cách.
• Số cách đến điểm H là: 1 cách.

Muốn đến điểm F, thì trước đó ta phải ở điểm C hoặc G.

Điểm F có hai điểm LIỀN TRƯỚC là điểm C và điểm G. Số cách tới điểm F bằng tổng số cách đến hai điểm LIỀN TRƯỚC nó, tức là bằng tổng số cách đến điểm C và số cách đến điểm G. Vậy:

• Số cách đến điểm F là: 1 + 1 = 2 cách.

Tương tự, điểm E có hai điểm LIỀN TRƯỚC là điểm D và điểm F nên:

• Số cách đến điểm E là: 1 + 2 = 3 cách.

Điểm K có hai điểm LIỀN TRƯỚC là điểm F và điểm H nên:

• Số cách đến điểm K là: 2+1 = 3 cách.

Điểm B có hai điểm LIỀN TRƯỚC là điểm E và điểm K nên:

• Số cách đến điểm B là: 3+3 = 6 cách.

Đáp số: 6 cách.

Cách 2: (Đối với bài trắc nghiệm)

• Ta đánh dấu số cách đi tới các điểm cùng hàng, cùng cột với điểm A : 1 cách.
• Ta lần lượt đánh số các điểm còn lại theo từng hàng, từ trái qua phải, từ dưới lên trên với quy tắc:
  • Số cách tới mỗi điểm là tổng các số ở các điểm liền trước điểm đó.

Đáp số: 6 cách.