Bài toán tổ hợp
Thầy Đức có 12 đồng xu cân đối và đồng chất đang được xếp thành một hàng ngang. Bây giờ thầy tiến hành xung từng đồng xu một và vẫn để các đồng xu xếp thành hàng ngang, sau đó thầy loại bỏ tất cả các đồng xu mà mặt hiện ra giống với một hoặc cả hai đồng xu kề nó. Xác suất sao cho chỉ còn tối đa một đồng xu có thể viết được dưới dạng \(\frac{a}{b}\), với \(a\) và \(b\) là các số nguyên dương nguyên tố cùng nhau. Giá trị của \(a+b\) bằng
Cách 1. Dùng bài toán chia kẹo Euler ta được kết quả là
$$\sum_{k=1}^6\binom{11-k}{k-1}+ \sum_{k=2}^6 k\binom{11-k}{k-2}=329.$$
Cách 2. Không mất tính tổng quát, giả sử lần tung đầu tiên là ngửa. Khi đó, ký hiệu mỗi lần tung tiếp theo là $S$ nếu kết quả giống lần trước, và $D$ nếu khác lần trước.
Gắn thêm một ký hiệu $S$ vào mỗi đầu của dãy thu được, khi đó sẽ còn nhiều nhất một đồng xu nếu trong dãy có nhiều nhất một lần xuất hiện của hai chữ $D$ liên tiếp.
Với một tập gồm $n$ đồng xu, ký hiệu $a_n$ là số dãy (độ dài $n+1$) chứa đúng một lần xuất hiện của hai chữ $D$ liên tiếp, và $b_n$ là số dãy (độ dài $n+1$) không chứa hai chữ $D$ liên tiếp.
Ta có $a_2=0$ và $b_2=1$. Với $n>2$, suy ra
$$
b_n=b_{n-2}+b_{n-3}+\cdots+b_2+1
$$
vì một dãy độ dài $n$ có thể được tạo từ một dãy độ dài $n-k(k \geq 2)$, theo sau bởi $k-1$ chữ $D$ và một chữ $S$; hoặc từ dãy dạng $S D D \ldots D S$.
Tương tự,
$$
a_n=b_{n-1}+a_{n-2}+a_{n-3}+\cdots+a_2+1
$$
vì một dãy có hai chữ $D$ liên tiếp có thể được tạo theo cách như trên, hoặc bằng cách nối thêm một chữ $D$ vào một dãy không có hai chữ $D$ liên tiếp.
Sử dụng các công thức truy hồi này để tính $a_n$ và $b_n$ với $n=3,4, \ldots, 12$, ta thu được $a_{12}=240$ và $b_{12}=89$. Tổng số dãy có thể là $2^{11}$, do đó xác suất là
$$
\frac{329}{2048} .
$$
Chú ý ở đây ta có $b_n=b_{n-1}+b_{n-2}$ và $a_n=a_{n-1}+a_{n-2}+b_{n-3}$. Gọi $F_n$ là số Fibonacci thứ $n$, ta thu được $b_n =F_{n-1}$ và $a_n =F_{n+1}-n$.