Question

[Bloom]

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 đỏ).

ABHình 1 ABHình 2

Bạn hãy tính xem có bao nhiêu đường đi hợp lệ từ A đến B?

Answer 1

[Võ Đông Anh Tuấn]

Bạn không nên đăng bài toán của OLM 

Answer 2

[Bloom]

Ta đặt tên các đỉnh như hình vẽ sau:

ABCDEFGHIJKMNOPQRSTU

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.

ABCDEFGHIJKMNOPQRSTU11111111

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)

ABCDEFGHIJKMNOPQRSTU1111111135

- Đỉ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)

ABCDEFGHIJKMNOPQRSTU11111111357

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:

AB111111113579513254172563129

Số đường đi hợp lệ từ A đến B là 129 đường.