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ị.
Ưu tiên cách đếm truy hồi ạ.
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ị.
Ưu tiên cách đếm truy hồi ạ.
Ồ,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!Anh cho em lời giải đầy đủ được không ạ
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.
$n=1$:
\[\begin{array}{c}
\left\{ {} \right\}\\
\left\{ 0 \right\}
\end{array}\]
$n=2$:
\[\begin{array}{c}
\left\{ {} \right\}\\
\left\{ 0 \right\}\\
\left\{ 1 \right\},\left\{ {1,0} \right\}
\end{array}\]
$n=3$:
\[\begin{array}{c}
\left\{ {} \right\}\\
\left\{ 0 \right\}\\
\left\{ 1 \right\},\left\{ {1,0} \right\}\\
\left\{ 2 \right\},\left\{ {2,1} \right\}
\end{array}\]
$n=4$:
\[\begin{array}{c}
\left\{ {} \right\}\\
\left\{ 0 \right\}\\
\left\{ 1 \right\},\left\{ {1,0} \right\}\\
\left\{ 2 \right\},\left\{ {2,1} \right\}\\
\left\{ 3 \right\},\left\{ {3,2} \right\},\left\{ {3,0} \right\}
\end{array}\]
$n=5$:
\[\begin{array}{c}
\left\{ {} \right\}\\
\left\{ 0 \right\}\\
\left\{ 1 \right\},\left\{ {1,0} \right\}\\
\left\{ 2 \right\},\left\{ {2,1} \right\}\\
\left\{ 3 \right\},\left\{ {3,2} \right\},\left\{ {3,0} \right\}\\
\left\{ 4 \right\},\left\{ {4,3} \right\},\left\{ {4,1} \right\},\left\{ {4,0} \right\},\left\{ {4,3,0} \right\},\left\{ {4,1,0} \right\}
\end{array}\]
$n=6$
\[\begin{array}{c}
\left\{ {} \right\}\\
\left\{ 0 \right\}\\
\left\{ 1 \right\},\left\{ {1,0} \right\}\\
\left\{ 2 \right\},\left\{ {2,1} \right\}\\
\left\{ 3 \right\},\left\{ {3,2} \right\},\left\{ {3,0} \right\}\\
\left\{ 4 \right\},\left\{ {4,3} \right\},\left\{ {4,1} \right\},\left\{ {4,0} \right\},\left\{ {4,3,0} \right\},\left\{ {4,1,0} \right\}\\
\left\{ 5 \right\},\left\{ {5,4} \right\},\left\{ {5,2} \right\},\left\{ {5,1} \right\},\left\{ {5,0} \right\},\left\{ {5,4,1} \right\},\left\{ {5,4,0} \right\},\left\{ {5,2,1} \right\},\left\{ {5,1,0} \right\},\left\{ {5,4,1,0} \right\}
\end{array}\]
Bạn thử kiểm tra xem có đúng không nhé Công thức tổng quát xin nhường bạn.
Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 30-04-2024 - 03:58
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
2 + 3. Một trong hai phần tử thuộc tập con
Như vậy đáp án bài toán là $3^n$
Mở rộng ra một chút thì:
Mở rộng ra một chút thì:
Em xin đưa ra lời giải tư tưởng như của anh luôn Em nghĩ mình cần thêm điều kiện là $m \in \mathbb{N^*}$ và $m<n-1$
Lời giải:
Xét tập: $\{0,1,\ldots,n-1\}$ và đếm số tập con thỏa mãn đề bài
Đặt $f(n)$ là số lượng tập con cần đếm
Ta đi xây dựng $f(n)$ từ các $f(n-a)$ ($a<n-1$)
Trường hợp 1: Không sử dụng phần tử $(n-1)$
Vậy thì các phần tử trong tập con sẽ không lớn hơn $(n-2)$ hay số tập con trong trường hợp này là $f(n-1)$
Trường hợp 2: Sử dụng phần tử $(n-1)$
Gọi $\mathbb{X}$ là tập con trong trường hợp này
-----------------------------------------------------------------------
Nếu $(n-2) \in \mathbb{X} \Rightarrow (n-2-m) \not \in \mathbb{X}$
Nên với mọi phần tử thuộc $\mathbb{X}$ khác $(n-1)$ đều không vượt quá $(n-3-m)$
Vậy số tập con lúc này thêm là $f(n-2-m)$
-----------------------------------------------------------------------
Nếu $(n-2) \not \in \mathbb{X}$
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ài viết đã được chỉnh sửa nội dung bởi truongphat266: 02-05-2024 - 16:07
Gọi $\mathbb{X}$ là tập con trong trường hợp này
-----------------------------------------------------------------------
Nếu $(n-2) \in \mathbb{X} \Rightarrow (n-2-m) \in \mathbb{X}$
Nên với mọi phần tử thuộc $\mathbb{X}$ khác $(n-1)$ đều không vượt quá $(n-3-m)$
Vậy số tập con lúc này thêm là $f(n-2-m)$
-----------------------------------------------------------------------
Nếu $(n-2) \not \in \mathbb{X}$
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$.
0 thành viên, 1 khách, 0 thành viên ẩn danh