Cho số nguyên dương $n$. Hai bạn $A$ và $B$ cùng tham gia một trò chơi gồm $n$ lượt. Mỗi lượt, họ độc lập giải cùng một câu đố và kết quả là mỗi người chơi hoặc giải được hoặc không giải được. Đặt $c_A(i)$, $c_B(i)$ lần lượt là tổng số câu đố mà $A$, $B$ giải được trong $i$ lượt đầu tiên. Hỏi có bao nhiêu kịch bản có thể xảy ra để $A$ đạt giải đặc biệt, nghĩa là sau khi kết thúc toàn bộ $n$ lượt chơi, $A$ không chỉ giữ được nhiều câu đố hơn $B$ $(c_A(n)>c_B(n))$, mà còn chưa bao giờ để $B$ bỏ xa quá một câu trong suốt quá trình $(\forall i=1,2,\dots ,n:c_B(i)-c_A(i)\le 1)$?

Với mỗi $i=0,1,\dots ,n$, đặt $d_i=c_A(i)-c_B(i)$. Ta xem $(d_i{)}_{i=0}^n$ như một quỹ đạo xuất phát từ $d_0=0$.

Ở mỗi lượt, quỹ đạo có một trong bốn loại bước:



Điều kiện để $A$ đạt giải đặc biệt tương đương với

$$d_i\ge -1(1\le i\le n),d_n>0.$$

Gọi $U_n(r)$ là số quỹ đạo không bị ràng buộc, có độ dài $n$, xuất phát từ $0$ và kết thúc tại $r$.

Ta biến mỗi bước của quỹ đạo thành hai bước lên hoặc xuống như sau:



Đây là một song ánh giữa các quỹ đạo độ dài $n$ kết thúc tại $r$ và các quỹ đạo gồm $2n$ bước lên, xuống, kết thúc tại độ cao $2r$. Nếu quỹ đạo mới có $a$ bước lên và $2n-a$ bước xuống thì

$$a-(2n-a)=2r,$$

suy ra $a=n+r$, do đó $U_n(r)=C_{2n}^{n+r}$.

Bây giờ cố định $r\ge 1$. Xét một quỹ đạo kết thúc tại $r$ nhưng vi phạm điều kiện $d_i\ge -1$.

Gọi $t$ là thời điểm đầu tiên quỹ đạo đạt tới $-2$.

Ta xét phần quỹ đạo từ thời điểm 0 đến thời điểm $t$: đổi mỗi bước 1 thành $-1$, mỗi bước $-1$ thành 1, còn hai loại bước 0 được giữ nguyên. Khi đó, phần quỹ đạo này kết thúc tại 2 thay vì $-2$.

Phần quỹ đạo sau thời điểm $t$ có tổng độ thay đổi bằng $r-(-2)=r+2$.

Vì thế quỹ đạo mới kết thúc tại $2+(r+2)=r+4$.

Ngược lại, mọi quỹ đạo kết thúc tại $r+4$ đều phải đi qua 2. Phần quỹ đạo mới từ đầu đến lần đầu tiên đạt 2, ta thu được một quỹ đạo kết thúc tại $r$ và vi phạm điều kiện $d_i\ge -1$.

Do đó, số quỹ đạo vi phạm kết thúc tại $r$ bằng $U_n(r+4)$.

Bởi vậy, số quỹ đạo hợp lệ kết thúc tại $r$ là $U_n(r)-U_n(r+4)=C_{2n}^{n+r}-C_{2n}^{n+r+4}$.

Cộng theo $r=1,2,\dots ,n$, ta được

$$\sum _{r=1}^n\left(C_{2n}^{n+r}-C_{2n}^{n+r+4}\right)=\sum _{r=1}^{\min \{4,n\}}{C}_{2n}^{n+r}.$$

Vậy số kịch bản cần tính bằng $\sum _{r=1}^{\min \{4,n\}}{C}_{2n}^{n+r}$.

Nhận xét: Bài toán trên liên quan tới bài toán quỹ đạo nổi tiếng sau:

Bài toán bỏ phiếu bầu cử: Cho hai ứng cử viên $A$ và $B$, biết rằng $A$ nhận $a$ phiếu bầu cử, $B$ nhận $b$ phiếu bầu cử và $a>b$. Hỏi có bao nhiêu cách kiểm phiếu sao cho trong suốt quá trình thì số phiếu của $A$ luôn lớn hơn số phiếu $B$? Đáp số: $\frac{a-b}{a+b}{C}_{a+b}^a$.