Trong không gian $Oxyz$ (đơn vị dài trên trục tính bằng mét), một con châu chấu đang ở vị trí $O(0;0;0)$ và dự định nhảy đến $C(6;5;5)$. Con châu chấu chỉ có thể nhảy theo ba hướng $\vec{i}=(1;0;0),\vec{j}=(0;1;0),\vec{k}=(0;0;1)$ và điều đặc biệt là nó sẽ không thể nhảy hai lần liên tiếp theo hướng $\vec{k}=(0;0;1)$. Mỗi lần nhảy của con châu chấu chỉ nhảy được quãng đường bằng $1\text{ m}$. Gọi $T$ là số cách con châu chấu di chuyển từ $O$ đến $C$. Bốn chữ số đầu tiên của $T$ là bao nhiêu?

Con châu chấu di chuyển từ $O(0;0;0)$ đến $C(6;5;5)$ cần thực hiện đúng:
- 6 bước theo hướng $\vec{i}$,
- 5 bước theo hướng $\vec{j}$,
- 5 bước theo hướng $\vec{k}$.
Tổng số bước là: $6+5+5=16$ bước.
Điều kiện: Không có hai bước liên tiếp nào cùng theo hướng $\vec{k}$.
- Trước hết, ta sắp xếp 11 bước gồm 6 bước $\vec{i}$ và 5 bước $\vec{j}$. Số cách sắp xếp là: $C_{11}^6=462$ cách.
- Sau khi sắp xếp 11 bước này, tạo ra 12 khe trống (trước bước đầu, giữa 2 bước bất kỳ và sau bước cuối) để chèn các bước $\vec{k}$.
- Để không có 2 bước $\vec{k}$ nào liên tiếp, mỗi khe được đặt nhiều nhất một bước $\vec{k}$. Số cách chọn 5 trong 12 khe để đặt 5 bước $\vec{k}$ là: $C_{12}^5=792$ cách.
Vậy tổng số cách di chuyển là: $T=C_{11}^6\cdot C_{12}^5=462\cdot 792=365904$ cách.
Bốn chữ số đầu tiên của $T$ là: $3659$.