Cho tập T gồm 11 số nguyên dương đầu tiên .Hỏi có tất cả bao nhiêu tập con A của T mà mỗi tập con A đều thỏa mãn điều kiện sau :Nếu 2k thuộc A thì 2k-1 và 2k+1 cũng thuộc A
Tổ hợp mời vô
Bắt đầu bởi
Khách- lovewin_*
, 03-01-2007 - 20:39
#1
Khách- lovewin_*
Đã gửi 03-01-2007 - 20:39
#2
Đã gửi 04-01-2007 - 18:45
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$.
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$.
Bài viết đã được chỉnh sửa nội dung bởi leecom: 05-01-2007 - 17:51
The Past, The Present, and The Future...
#3
Đã gửi 05-01-2007 - 17:52
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!
The Past, The Present, and The Future...
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh