Chủ đề này có 7 trả lời

[khanghaxuan]

Tìm số tập con của tập $\begin{Bmatrix} 1;2;...;n \end{Bmatrix}$ sao cho trong mỗi tập con chứa đúng hai phần tử là hai số nguyên liên tiếp

[Belphegor Varia]

Giải 
Gọi $S_{n}$ là tập hợp các tập con có tính chất đã nêu trên. Ta chia các phần tử của $S_{n}$ thành 3 nhóm : Nhóm 1 gồm các tập chứa n và n-1 , nhóm 2 gồm các tập không chứa n , nhóm 3 gồm các tập chứa n nhưng không chứa n-1 . 
$+)$ Ở nhóm 1 , vì mỗi tập con chứa n và n-1 nên sẽ không chứa n-2 , vậy số các tập con là $\left | S_{n-3} \right |$ 
$+)$ Ở nhóm 2 , hiển nhiên số các tập con là $S_{n-1}$
$+)$ Ở nhóm 3 , số các tập con là $\left | S_{n-2} \right |$
Vậy ta có hệ thức sau $\left | S_{n} \right |= \left | S_{n-1} \right |+\left | S_{n-2} \right |+\left | S_{n-3} \right |$. 
Chứng minh tiếp bằng quy nạp ...

Bài viết đã được chỉnh sửa nội dung bởi Belphegor Varia: 02-06-2015 - 15:46

[ducvipdh12]

Áp dụng kết quả bài tóan phụ sau ( tự chứng minh,bằng phương pháp truy hồi ):

"Cho tập $S=\left \{ 1,2,...,n \right \}$. Số các tập con của $S$ mà không chứa 2 số nguyên dương liên tiếp là $F_{n+2}$"

Trở lại bài tóan:

ta gọi $X_n$ là họ các tập con đã nêu và $\left | X_n \right |=a_n$. Mỗi tập con $A\in X_{n+2}$ là 1 trong 3 loại sau:

+/ Loại 1 gồm các tập chứa $n+2$ và $n+1$:

Nếu $A$ là tập loại 1 thì $A$ không chứa $n$ vì nếu $A$ chứa $n$ sẽ mâu thuẫn với giả thiết là có đúng 2 phần tử liên tiếp.Nếu ta bỏ đi tập $A$ 2 phần tử $n+1,n+2$ thì được 1 tập con $A'$ của $\left \{ 1,2,...,n-1 \right \}$ không chứa 2 phần tử liên tiếp. Ngược lại với mỗi tập con $A'$ của $\left \{ 1,2,...,n-1 \right \}$ thì ta có thể thêm 2 số nguyên dương $n+1,n+2$ vào để được 1 tập thuộc loại 1. Phép tương ứng là song ánh nên theo kết quả bài tóan phụ số tập loại 1 là $F_{n+1}$ 

+/ Loại 2 là các tập chứa $n+2$ nhưng không chứa $n+1$

Nếu $A$ là tập loại 2 thì $A$ không chứa $n+1$. Do đó nếu bỏ đi khỏi $A$ phần tử $n+2$  thì ta sẽ được 1 tập con của $X_n$ và ngược lại. Đây là phép tương ứng song ánh nên số tập loại 2 là $a_n$

+/ Loại 3 gồm các tập không chứa $n+2$

Tương tự như ở loại 2 ta có số tập loại 3 là $a_{n+1}$

Ta có hệ thức sau:

$a_{n+2}=a_{n+1}+a_n+F_{n+1}$

Dễ dàng chứng minh công thức bằng quy nạp:

$a_n=\frac{2n.F_{n+1}-(n+1).F_n}{5}$

nhắc thêm 1 tí là $F_n$ là dãy số Fibonacci nên công thức $F_n=\frac{a^n-b^n}{\sqrt{5}}$ với $a=\frac{1+\sqrt{5}}{2};b=\frac{1-\sqrt{5}}{2}$. Thay vào là được

[ducvipdh12]

Giải 
Gọi $S_{n}$ là tập hợp các tập con có tính chất đã nêu trên. Ta chia các phần tử của $S_{n}$ thành 3 nhóm : Nhóm 1 gồm các tập chứa n và n-1 , nhóm 2 gồm các tập không chứa n , nhóm 3 gồm các tập chứa n nhưng không chứa n-1 . 
$+)$ Ở nhóm 1 , vì mỗi tập con chứa n và n-1 nên sẽ không chứa n-2 , vậy số các tập con là $\left | S_{n-3} \right |$ 
$+)$ Ở nhóm 2 , hiển nhiên số các tập con là $S_{n-1}$
$+)$ Ở nhóm 3 , số các tập con là $\left | S_{n-2} \right |$
Vậy ta có hệ thức sau $\left | S_{n} \right |= \left | S_{n-1} \right |+\left | S_{n-2} \right |+\left | S_{n-3} \right |$. 
Chứng minh tiếp bằng quy nạp ...

Sai rồi,đọc kỹ đề bài nhé

[Belphegor Varia]

Sai rồi,đọc kỹ đề bài nhé

Bạn có thể chỉ ra cho mình được không?

Bài viết đã được chỉnh sửa nội dung bởi Belphegor Varia: 02-06-2015 - 16:07

[ducvipdh12]

Bạn có thể chỉ ra cho mình được không?

Sai ở nhóm 1,đã chứa 2 phần tử n,n-1 rồi.Tức là đã chứa 2 phần tử liên tiếp rồi thì sao có thể là $\left | S_{n-3} \right |$ được em

[Belphegor Varia]

Sai ở nhóm 1,đã chứa 2 phần tử n,n-1 rồi.Tức là đã chứa 2 phần tử liên tiếp rồi thì sao có thể là $\left | S_{n-3} \right |$ được em

Em cảm ơn anh(chị) nha 

[hxthanh]

Áp dụng kết quả bài tóan phụ sau ( tự chứng minh,bằng phương pháp truy hồi ):
"Cho tập $S=\left \{ 1,2,...,n \right \}$. Số các tập con của $S$ mà không chứa 2 số nguyên dương liên tiếp là $F_{n+2}$"
....

Dễ dàng chứng minh công thức bằng quy nạp:
$a_n=\frac{2n.F_{n+1}-(n+1).F_n}{5}$
nhắc thêm 1 tí là $F_n$ là dãy số Fibonacci nên công thức $F_n=\frac{a^n-b^n}{\sqrt{5}}$ với $a=\frac{1+\sqrt{5}}{2};b=\frac{1-\sqrt{5}}{2}$. Thay vào là được

Em giải quyết bài này rất hay và chính xác!
Liên quan chút xíu với bài toán sau! (Em tìm được song ánh thì thật là tuyệt vời!)

Bài toán
$X=\{1,2,...,n\}$
Xét tất cả các tập con của $X$ mà trong đó không chứa hai số liên tiếp. Đếm tổng số các phần tử $S_n$.

Ví dụ $n=4$; $X=\{1,2,3,4\}$
Các tập con của $X$ không chứa hai số liên tiếp gồm $\{\},\{1\},\{2\},\{3\},\{4\},\{1,3\},\{1,4\},\{2,4\}$
Tổng cộng có $10$ phần tử: $S_4=10$