Câu 2. Cho tứ diện $ABCD$, một con bọ đang đậu ở đỉnh $A$ của tứ diện. Mỗi lần nghe một tiếng trống thì nó nhảy sang một đỉnh bất kì của tứ diện $ABCD$ mà kề với đỉnh nó đang đậu. Hỏi sau 4 tiếng trống nó có bao nhiêu cách trở về đỉnh $A$?

(AI giải đề cho tôi)
Đồ thị các đỉnh của tứ diện là $K_4$: mỗi đỉnh kề với 3 đỉnh còn lại. Đếm số đường đi độ dài 4 từ $A$ về $A$.

Gọi $a_n$ = số cách đi $n$ bước từ $A$ về $A$; $b_n$ = số cách đi $n$ bước từ $A$ đến một đỉnh khác cố định (do đối xứng, số cách đến $B$, $C$, $D$ bằng nhau). Ta có:
$$a_{n+1}=3b_n,b_{n+1}=a_n+2b_n,$$
với $a_0=1,b_0=0$.

- $n=1$: $a_1=3\cdot 0=0$, $b_1=1+0=1$.
- $n=2$: $a_2=3\cdot 1=3$, $b_2=0+2\cdot 1=2$.
- $n=3$: $a_3=3\cdot 2=6$, $b_3=3+2\cdot 2=7$.
- $n=4$: $a_4=3\cdot 7=21$.

Kiểm tra bằng công thức số đường đi đóng độ dài $n$ tại một đỉnh của $K_4$: $\frac{3^n+3(-1{)}^n}{4}=\frac{3^4+3}{4}=\frac{84}{4}=21$ — khớp.

Giải thích trực tiếp: đường đi $A\to x\to y\to z\to A$ với $x,y,z\in \{B,C,D\}$, hai đỉnh liên tiếp khác nhau ($x\ne y$, $y\ne z$). Nếu $x=z$ thì $y$ có 2 cách (dạng $A\to x\to y\to x\to A$: $3\cdot 2=6$ đường); nếu $x\ne z$ thì $x,y,z$ đôi một khác nhau: $3\cdot 2\cdot 1=6$ đường. Tổng $6+6=12$? Cần đếm thêm trường hợp quay lại $A$ ở bước giữa: dạng $A\to x\to A\to z\to A$ với $x,z$ bất kì trong $\{B,C,D\}$: $3\cdot 3=9$ đường. Ba dạng này rời nhau và phủ hết (bước 2 hoặc bước 3 là $A$, hoặc không): $6+6+9=21$ đường.

Vậy sau 4 tiếng trống có $21$ cách trở về đỉnh $A$.