Cho tập hợp gồm $2n$ số tự nhiên đầu tiên, hỏi có bao nhiêu tập con (tính cả tập rỗng) của tập đó sao cho không có $2$ phần tử nào trong tập con đó cách nhau đúng $2$ đơn vị.
BTW, xin gửi một biến tấu :
Cho tập hợp gồm $2n$ số tự nhiên đầu tiên, hỏi có bao nhiêu tập con (tính cả tập rỗng) của tập đó sao cho không có 2 phần tử nào trong tập con đó hơn kém nhau đúng $n$ đơn vị.
NB: Để được đông đảo các bạn tham gia, nên xin nói rõ: Ở đây không ưu tiên cách giải nào cả do đó mọi cách giải đều được welcome.
Ồ,Tất nhiên rùi. Nhưng mà cách tiếp cận của mình không thuộc diện ưu tiên, miễn cưỡng lắm thì có thể xem là truy hồi hybrid, truy hồi xăng pha nhớt!
******
Lời giải của mình cũng na ná như của bạn dưới đây.
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 30-04-2024 - 13:51
Cho tập hợp gồm $2n$ số tự nhiên đầu tiên, hỏi có bao nhiêu tập con (tính cả tập rỗng) của tập đó sao cho không có $2$ phần tử nào trong tập con đó cách nhau đúng $2$ đơn vị.
Mình không hiểu $2n$ thì khác gì với trường hợp $2n+1$ lắm, nên mình sẽ xét trường hợp tổng quát là $n$.
Để bắt đầu truy hồi, ta luôn đặt $f(n)$ là hàm đại diện cho đại lượng cần đếm. Ở đây là: "số tập con của $S(n)$ sao cho không có $2$ phần tử nào có hiệu bằng $2$" với $S(n)=\{0,1,\ldots,n-1\}$ tập $n$ số tự nhiên đầu tiên.
Sau đó, ta xác định $f(n)$ dựa trên các giá trị có trước (truy hồi): $f(n-1), f(n-2), \ldots$.
Ta thấy rằng để từ $S(n-1)$ lên $S(n)$, ta phải thêm số $n-1$ vào, do đó ta cần tìm hiểu xem con số $n-1$ này sẽ được sử dụng như thế nào để xây dựng các tập con của $S(n)$ mà vẫn thỏa đề.
TH1: Nếu ta không dùng $n-1$, tức là ta chỉ dùng các số tự nhiên không quá $n-2$. Vậy ta đang đếm $f(n-1)$.
TH2: Nếu ta dùng $n-1$: xét một $X$ tập con thỏa đề có chứa $n-1$. Dễ thấy $n-3 \not \in X$.
TH2.1: Nếu $n-2 \not \in X$, thế thì mọi phần tử khác $n-1$ của $X$ đều không vượt quá $n-4$. Vậy ta có thêm $f(n-3)$ tập con thỏa đề.
TH2.2: Nếu $n-2 \in X \Rightarrow n-4 \not \in X$. Suy ra mọi phần tử khác $n-1$ và $n-2$ của $X$ đều không vượt quá $n-5$. Vậy ta có thêm $f(n-4)$ tập.
Tổng cộng, ta sẽ có $$f(n)=f(n-1)+f(n-3)+f(n-4)$$
Ta liệt kê "vài" trường hợp đầu tiên. Với mỗi $n$, ta sẽ liệt kê các tập con thành nhiều hàng, mỗi hàng sẽ có chung phần tử lớn nhất.
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! $$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$ I'm still there everywhere.
Mình xin chia sẻ cách làm của mình.
Ta phân hoạch $2n$ số đó thành $2$ tập, một tập gồm toàn số chẵn, một tập gồm toàn số lẻ.
Như vậy đưa bài toán trở về thành: Đếm số các tập con của tập $n$ sô tự nhiên đầu tiên (tỉnh cả tập rỗng) sao cho trong mỗi tập con thì không có 2 phần từ kế tiếp nhau. $(1)$
Có điều bên trên vì ta quan sát thấy 2 số vi phạm điều kiện đề bài ban đầu phải cùng tính chẵn lẻ. Nên dễ dàng tưởng tượng ra bài toán $(1)$ ở trên. Kết quả của bài toán ban đầu chính là bình phương kết quả bài toán $(1)$.
Để giải quyết bài toán $1$ có rất nhiều cách nhưng có vẻ bạn ưu tiên cách truy hồi nên sau đây sẽ là cách truy hồi.
Đặt $f(n)$ là kết quả cho bài toán $(1)$ với $n$ số tự nhiên đầu tiên.
Xét $f(n+1)$.
Ta thấy có f(n) tập con của tập $n+1$ phần tử không chứa $n+1$ thỏa mãn đề bài
Tương tự nếu tập con có chứa $n+1$ thì sẽ có $f(n-1)$ tập con như vậy.
Khi đó ta có:
$$f(n+1) = f(n) + f(n-1)$$
Tính vài giá trị đầu thấy $f(0) = 1$ , $f(1) = 2$
khi đó khẳng định ngay $f(n) = F_{n+2}$ với $F$ là dãy $\textbf{Fibonacci}$
Như vậy kết quả cuối cùng là $(F_{n+2})^{2}$
Bài viết đã được chỉnh sửa nội dung bởi hovutenha: 30-04-2024 - 09:07
BTW, xin gửi một biến tấu :
Cho tập hợp gồm $2n$ số tự nhiên đầu tiên, hỏi có bao nhiêu tập con (tính cả tập rỗng) của tập đó sao cho không có 2 phần tử nào trong tập con đó hơn kém nhau đúng $n$ đơn vị.
NB: Để được đông đảo các bạn tham gia, nên xin nói rõ: Ở đây không ưu tiên cách giải nào cả do đó mọi cách giải đều được welcome
Phân hoạch $2n$ số tự nhiên đầu tiên thành $n$ tập $2$ phần tử mà $2$ phần tử đó hơn kém nhau đúng $n$ đơn vị.
Với mỗi tập trong $n$ tập đó, chỉ có nhiều nhất một phần tử có thể tham gia vào tập con thỏa mãn đề bài nên có $3$ sự lưa chọn cho mỗi tập như sau:
1. Không phần tử nào thuộc tập con
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! $$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$ I'm still there everywhere.
Nên với mọi phần tử thuộc $\mathbb{X}$ khác $(n-1)$ đều không vượt quá $(n-2-m)$
Vậy số tập con lúc này thêm là $f(n-1-m)$
Kết luận: Số tập con cần đếm là $$f(n) = f(n-1) + f(n-1-m) + f(n-2-m)$$
Bạn hơi vội chỗ này rồi. Lấy $m=3$, thì ta thấy rằng nếu $n-2 \in \mathbb X \Rightarrow n-5 = n-2-3 \not \in \mathbb X$, nhưng chú ý rằng $n-3$ vẫn có thể nằm trong $X$.
Với $m \ge 2$, phải chú ý các phần tử $n-1,n-2, n-3, \ldots, n-2m$.
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! $$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$ I'm still there everywhere.
Đã gửi 29-04-2024 - 21:21
Công thức tổng quát xin nhường bạn.
