2 replies to this topic

[leecom]

Ta sẽ giải quyết bài toán tổng quát: Cho tập $2n+1$ số nguyên dương đầu tiên. Tìm số các tập con $A$ thỏa mãn nếu $2k \in A$ thì $2k-1 \in A$ và $2k+1 \in A$.
Với mỗi $n$, ta đặt $X_{n}$ là số tập con của tập $\{1,2,...,2n+1\}$ thỏa mãn, $Y_{n}$ là số tập con của tập $\{1,2,...,2n\}$ thỏa mãn.
Xét với $n+1$.
+ Xét với tập ${1,2,...,2n+3}$. Phân làm $2$ loại tập con:
- loại tập không chứa $2n+2$ thỏa mãn yêu cầu bài toán là $2X_{n}$
- loại tập chứa $2n+2$ thỏa mãn là $Y_{n}$
Vậy thì: $X_{n+1}= 2X_{n}+ Y_{n}$
+ Xét với tập ${1,2,...,2n+2}$. Cũng phân làm $2$ loại:
- loại tập không chứa $2n+2$ thỏa mãn là $X_{n}$
- loại tập chứa $2n+2$ thỏa mãn là $Y_{n}$
Vậy thì: $Y_{n+1}= X_{n}+Y_{n}$
Và dễ có $X_{1}=5, Y_{1}=3$. Từ đó tìm được $X_{n}= \dfrac{4+2\sqrt{5}}{2\sqrt{5}}(\dfrac{3+\sqrt{5}}{2})^{n}+\dfrac{2\sqrt{5}-4}{2\sqrt{5}}(\dfrac{3-\sqrt{5}}{2})^{n}.$.

Bài toán của ta ứng với TH $n=5$, đáp số lúc này là $233$.

Edited by leecom, 05-01-2007 - 17:51.

[leecom]

Mình nghĩ là với TH riêng như trên còn có lời giải khác ngắn gọn hơn, mọi người thử xem sao!