Bài toán đếm số đường đi ngắn nhất trên lưới vuông từ điểm $A$ đến điểm $B$ là một bài toán tổ hợp rất đẹp và quen thuộc.

Để đi từ $A$ đến $B$ theo đường ngắn nhất trên một lưới ô vuông, ta chỉ được phép di chuyển theo hai hướng: sang phải (ngang) và lên trên (dọc).

📐 CÔNG THỨC TỔNG QUÁT

Giả sử để đi từ $A$ đến $B$:

• Cần đi qua $m$ bước sang ngang.

• Cần đi qua $n$ bước lên dọc.

1. Tổng số bước đi:

2. Công thức tính số đường đi ngắn nhất:

Mỗi đường đi ngắn nhất là một dãy gồm đúng $(m + n)$ bước, trong đó có đúng $m$ bước ngang và $n$ bước dọc. Việc chọn một đường đi tương đương với việc chọn vị trí cho $m$ bước ngang (hoặc $n$ bước dọc) trong tổng số $(m + n)$ bước.

Do đó, số đường đi ngắn nhất từ $A$ đến $B$ được tính bằng công thức tổ hợp:

💡 VÍ DỤ CỤ THỂ ĐỂ HƯỚNG DẪN CON:

Ví dụ 1: Lưới kích thước $3 \times 2$ (Lưới $3$ ô ngang, $2$ ô dọc)

• Số bước ngang: $m = 3$

• Số bước dọc: $n = 2$

• Tổng số bước: $3 + 2 = 5$ bước.

👉 Số đường đi ngắn nhất từ $A$ đến $B$ là:

Ví dụ 2: Lưới bàn cờ vua $8 \times 8$ (từ góc dưới-trái $A$ đến góc trên-phải $B$)

• Số bước ngang: $m = 8$

• Số bước dọc: $n = 8$

• Tổng số bước: $8 + 8 = 16$ bước.

👉 Số đường đi ngắn nhất là: