Đề bài: Trên bàn cờ 5 x 4 ô vuông như hình vẽ, người chơi chỉ được di chuyển quân theo các cạnh của hình vuông, mỗi bước đi được 1 cạnh. Có bao nhiêu cách di chuyển quân từ điểm A tới điểm B bằng 9 bước ?
Trả lời
Hướng dẫn giải:
Để đi từ A đến B qua 9 bước thì chỉ có 1 cách đi duy nhất là các bước đi đều phải đi từ dưới lên hoặc đi từ trái qua phải.
Gọi M(i; j) là điểm bất kì nằm ở hàng i cột j với và .
Để đến được điểm M thì chỉ có 3 cách đi đó là từ điểm có tọa độ (i − 1; j) hoặc (i; j − 1) như hình vẽ dưới:
Gọi số cách đi đến M là f(i; j) thì theo quy tắc cộng ta có
Từ đó ta được kết quả sau:
Vậy có 126 cách đi thỏa mãn
