Bài 5 trang 37: Một lưới ô vuông nxm (số hàng m< n số cột). Một con kiến cần leo từ điểm A lên điểm B. Mỗi lần leo chỉ bò dọc theo các cạnh của ô: lên đúng một bậc hoặc sang phải (có thể nhiều ô). Hỏi có bao nhiêu đường có thể xảy ra?
Giải:
Con kiến cần leo đúng m bậc lên và sang phải n bậc để đi từ điểm A đến điểm B. Vì mỗi lần nó chỉ lên đúng một bậc hoặc sang phải (có thể nhiều ô) nên sau mỗi lần lên phải có ít nhất một lần sang phải → Coi một lần lên tương ứng với một lần sang phải thì số lần lên là m, số lần sang phải còn lại là n - m (vì đã gắn m bước sang phải với m bước lên). ta đưa về bài toán 5. Số đường đi có thể xảy ra là số cách chọn m vị trí trong m + (n - m) = n vị trí, không tính đến thứ tự, không lặp. Hay đó chính là C^mn.
TH2: lần cuối cùng chỉ có lên mà không có sang phải. ta còn m -1 lần sang lên phải kèm lần sang phải. tương tự như trên ta có số cách là C^m-1n
Vậy tổng số cách có thể là:
C^mn + C^m-1n = C^mn+1

hienha đã viết:Bài 5 trang 37: Một lưới ô vuông nxm (số hàng m< n số cột). Một con kiến cần leo từ điểm A lên điểm B. Mỗi lần leo chỉ bò dọc theo các cạnh của ô: lên đúng một bậc hoặc sang phải (có thể nhiều ô). Hỏi có bao nhiêu đường có thể xảy ra?
giải:
Con kiến cần leo đúng m bậc lên và sang phải n bậc để đi từ điểm A đến điểm B. Vì mỗi lần nó chỉ lên đúng một bậc hoặc sang phải (có thể nhiều ô) nên sau mỗi lần lên phải có ít nhất một lần sang phải → Coi một lần lên tương ứng với một lần sang phải thì số lần lên là m, số lần sang phải còn lại là n-m (vì đã gắn m bước sang phải với m bước lên). ta đưa về bài toán 5. Số đường đi có thể xảy ra là số cách chọn m vị trí trong m + (n-m) =n vị trí, không tính đến thứ tự, không lặp. Hay đó chính là C^mn

Đ/a: C^mn+1 với m<= n+1

Anh Hưng à, bài này đáp án phải là C^mn (với m< n như đầu bài đã cho), sao lại là C^mn+1 được?

Bài tập ô lưới m * n với m < n
con kiến leo từ A đến B tương ứng với cách đi đường thẳng với m bước lên trên và n bước sang phải. tất cả có m + n bước. Vì trong m bước lên trên không có bước nào đứng gần nhau nên ta xếp n bước sang phải thành một hàng và cách nhau một vị trí. Số cách con kiến leo từ A đến B tương đương với số sắp xếp m bước lên trên vào n + 1 vị trí xen kẽ của n bước sang phải. Vậy số cách mà kiến leo lên được là C(m, n + 1) cách.
Lấy ví dụ m = 2, n = 3 vẽ ô ra tính được là 6 cách
m = 3, n = 4 vẽ ô ra tính được là 10 cách.
Lê Văn Đạt

- em Hiền xét còn chưa tính đến trường hợp bước cuối cùng là bước đi lên, nên kết quả chưa chính xác.
- Cách giải của đồng chí Đạt là đúng.
[You must be registered and logged in to see this image.]

Bài này giải như anh Đạt là đúng rùi!

Hì, đọc con kiến với leo sang trái sang phải leo lên leo xuống có vẻ khó theo dõi và rối đầu.
Em cứ tư duy củ chuối thế này cho đơn giản: việc con kiến leo từ A đến B cần đi hết m+n bước (m lên và n sang phải)coi như là xâu nhị phân độ dài m+n.
Coi mỗi bước lên là một bít 1, mỗi bước sang phải là một bít O.
Việc giải bài toán con kiến giờ trở thành: tìm số xâu nhị phân độ dài m+n có đúng m bít 1 và không có 2 bít 1 nào đứng cạnh nhau.
Xếp n bít 0 trước.
Có n+1 ô trống giữa các bit 0 có thể sắp m bít 1 vào đó
Thế là có C(m,n+1) xâu nhị phân thỏa mãn bài toán tương đương với bằng đấy cách để con kiến leo lên đích!