Trên một ô lưới hình chữ nhật gồm 9 cột và 5 hàng ô vuông như hình vẽ. Một bé cún xuất phát từ điểm $A$ và chạy đến điểm $B$. Mỗi bước, bé cún chỉ được chạy sang phải hoặc xuống dưới đúng 1 ô (đi theo các cạnh của ô vuông), vì vậy bé cún luôn đi theo đường ngắn nhất. Trong hình có phần tô đậm $CDEG$ và $GHIK$ là những bãi bùn. Bé cún không được chạy vào miền trong của các vùng tô đậm đó, nhưng vẫn được phép chạy trên đường biên của chúng. Hỏi bé cún có bao nhiêu cách chạy từ $A$ đến $B$?

(AI giải đề cho tôi)
Mô hình hóa: lưới 9 cột, 5 hàng, $A=(0,0)$, $B=(9,5)$, mỗi đường đi gồm 9 bước sang phải và 5 bước xuống dưới, tổng số đường ngắn nhất là $\left(\genfrac{}{}{0ex}{}{14}{5}\right)=2002$.

Vị trí các bãi bùn (theo hình): $CDEG$ là hình chữ nhật $[3,5]\times [2,4]$ (đỉnh $C(3,2),G(5,2),D(3,4),E(5,4)$) và $GHIK$ là hình chữ nhật $[5,7]\times [1,2]$ (đỉnh $K(5,1),I(7,1),G(5,2),H(7,2)$).

Đường đi của cún chỉ đi trên các cạnh ô vuông, nên nó 'vào miền trong' của một vùng tô đậm khi và chỉ khi nó đi qua một cạnh của lưới nằm hoàn toàn trong miền trong vùng đó.

1) Miền trong của $CDEG$: các cạnh lưới nằm trong là $(3,3)-(4,3)$, $(4,3)-(5,3)$, $(4,2)-(4,3)$, $(4,3)-(4,4)$ — tất cả đều đi qua điểm $(4,3)$. Vậy đường đi vào miền trong của $CDEG$ khi và chỉ khi đi qua $(4,3)$. Số đường từ $A$ đến $(4,3)$: $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$; từ $(4,3)$ đến $B(9,5)$: $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$. Số đường xấu: $35\cdot 21=735$.

2) Miền trong của $GHIK=[5,7]\times [1,2]$: hình này rộng 2 ô, cao 1 ô nên cạnh lưới duy nhất nằm trong miền trong là cạnh dọc giữa $(6,1)-(6,2)$ (các cạnh còn lại nằm trên đường biên, được phép đi). Số đường đi qua cạnh này: từ $A$ đến $(6,1)$ có $\left(\genfrac{}{}{0ex}{}{7}{1}\right)=7$ cách; từ $(6,2)$ đến $B(9,5)$ có $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ cách. Số đường xấu: $7\cdot 20=140$.

3) Hai tập đường xấu rời nhau (đường qua $(4,3)$ rồi tới $(6,1)$ là không thể vì phải đi lên; tương tự thứ tự ngược cũng vô lý vì đường đi đơn điệu), nên không cần trừ giao.

Kết quả: $2002-735-140=1127$. Khớp với đáp án nguồn 1127.