Bài toán 111
Cho bản đồ như Hình 1 dưới đây. Một đường đi hợp lệ từ đỉnh A đến đỉnh B là đường đi thỏa mãn đồng thời hai điều kiện sau:
- Trên đường đi không chứa đoạn nào đi lên
- Trên đường đi không chứa đoạn nào đi từ phải sang trái (hướng từ B sang A)
Hình 2 là một ví dụ về đường đi thỏa mãn hai điều kiện trên (đường màu đỏ).
Bạn hãy tính xem có bao nhiêu đường đi hợp lệ từ A đến B?
---------------------
Bạn trình bày lời giải đầy đủ vào ô Gửi Ý kiến phía dưới. Năm bạn có lời giải hay và sớm nhất sẽ được cộng/thưởng 1 tháng VIP của Online Math. Đáp án và giải thưởng sẽ được công bố vào Thứ Sáu ngày 22/7/2016. Câu đố tiếp theo sẽ lên mạng vào Thứ Bảy ngày 23/7/2016.
---------------------
Tính đến thời điểm công bố đáp án, chỉ có ba bạn sau đây đưa ra đáp số đúng (129 đường), tuy nhiên cả ba bạn đều không có lời giải đầy đủ. Online Math vẫn thưởng 1 tháng VIP cho các bạn có đáp số đúng.
TFBoys, Trường THCS Phan Chu Trinh, Huyện Tân Thành - Bà Rịa - Vũng Tàu
Nguyễn Nho Dũng, Trường THCS Cổ Đông, Thị xã Sơn Tây - Hà Nội
đỗ Hoàng Gia HUy, Trường THCS Nguyễn Trường Tộ, Quận Đống Đa - Hà Nội
---------------------
Đáp án
Ta đặt tên các đỉnh như hình vẽ sau:
Ta có nhận xét sau:
1) Số đường đi hợp lệ từ A đến các đỉnh nằm trên cạnh phía trên của lưới ô vuông C, D, E, F luôn là 1 (ví dụ từ A đến D chỉ có đường duy nhất là A-->C-->D)
2) Số đường đi hợp lệ từ A đến các đỉnh nằm trên cạnh bên trái của lưới ô vuông G, M, R cũng là 1 (Ví dụ từ A đến R chỉ có đúng 1 đường duy nhất là A-->G-->M-->R)
Ta ghi số cách đi hợp lệ từ A đến một đỉnh bằng số màu đỏ như hình vẽ dưới.
3) Ta tính số đường đi từ A đến các đỉnh còn lại theo qui tắc đệ qui (hoặc qui nạp) như sau:
- Đỉnh H: có 3 cách đi: A-->C-->H ; A-->H ; A -->G-->H
- Đỉnh I: Các đường đi từ A đến I được phân thành 3 loại:
+ đi qua đoạn DI: từ là từ A đến D rồi đến DI
+ đi qua đoạn CI: từ A đến C rồi đoạn CI
+ đi qua đoạn HI: từ A đến H rồi đoạn HI
Như vậy
[số đường đi từ A đến I] = [số đường đi từ A đến D] + [số đường đi từ A đến C] + [số đường đi từ A đến H]
= 1 + 1 + 3
= 5
(xem hình vẽ minh hoạ bên dưới)
- Đỉnh J: Tương tự như cách tính đỉnh I:
[số đường đi từ A đến J] = [số đường đi từ A đến E] + [số đường đi từ A đến D] + [số đường đi từ A đến I]
= 1 + 1 + 5
= 7
(xem hình vẽ minh hoạ bên dưới)
Cứ lặp lại tính như vậy cho các đỉnh còn lại. Ta sẽ điền được số đường đi hợp lệ từ A đến các đỉnh khác nhau như hình dưới đây:
Số đường đi hợp lệ từ A đến B là 129 đường.
