Bài tập EGO 1

Bài toán

Có bao nhiêu cách chia $n$ điểm trên đường thẳng thành các tập chứa $1$ hoặc $2$ điểm kề nhau?

Giải

Giữa $n$ điểm này có $n-1$ khoảng trống. 

Mỗi khoảng trống, ta đặt một dấu $x$, đánh số $n-1$ dấu $x$ đó là $1,2,...,n-1$. 

Muốn có cách chia thỏa mãn yêu cầu bài toán, ta chỉ cần bỏ đi $k$ dấu $x$, $0\leq k \leq \left [ \frac{n}{2} \right ]$, trong đó không có hai dấu $x$ nào kề nhau.

Xét Bài toán tìm số cách chọn bộ $(x_1,x_2,...,x_k)$ thỏa mãn:

$$\left\{\begin{matrix}1\leq x_1 < x_2 < ... < x_k \leq n-1\\x_{i+1}-x_i > 1, i=\overline{1,k}\end{matrix}\right.$$

Hay:

$$1\leq x_1 < x_2 -1 < x_3-2<... < x_k - k+1 \leq n- k$$

Dễ thấy là có $C_{n-k}^k$ cách.

Tống số cách cần tìm là:

$$\Sum_{k=0}{ \left [ \frac{n}{2} \right ]}C^k_{n-k}=F_{n+1}$$

Trong đó $F_k$ là số Fibonacci thứ $k$.