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

[hxthanh]

Kỳ thi chọn đội tuyển Việt nam năm 2010 ngày thứ nhất có bài toán:

Cho $n$ là một số nguyên dương và tập hợp $A=\{1,2,...,2n\}$. Một tập con của $A$ được gọi là tốt nếu nó gồm đúng hai phần tử $x,\; y$ sao cho $|x-y|\in\{1,n\}$. Tìm số các tập hợp $\{A_1,A_2,...,A_n\}$ thỏa mãn $A_i$ là tập con tốt của $A$ với mọi $i=1,2,...,n$ và
$$A_1 \cup A_2 \cup ...\cup A_n=A$$

Trong tài liệu: "Chuyên đề Toán học số 9 - Trần Nam Dũng" thầy có đưa ra đáp án như sau:

Số các bộ $\{A_1,A_2,...,A_n\}$ thỏa mãn yêu cầu đề bài là
$$\left\{\begin{align*}&1 &&\text{nếu } n = 1 \\ &\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right] &&\text{nếu } n \text{ chẵn} \\ &1+\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right] &&\text{nếu } n \text{ lẻ và } n >1\end{align*}\right.$$

Hình như đáp án như vậy vẫn "hơi dài" thì phải?
Bạn nào có thể đưa ra đáp án của bài này ngắn gọn hơn không? Hoặc nếu không, bạn hãy giúp tôi gộp ba nhánh đáp án trên thành một công thức duy nhất!

[hxthanh]

Ví dụ ta có thể gộp công thức trên thành:

$$\boxed{f(n)=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right]+\left\lfloor\dfrac{1-n}{1+n}\right\rfloor\left(2\left\lfloor\dfrac{n}{2}\right\rfloor-n\right);\;\;\forall n \in \mathbb{N}^*}$$
...

Dùng khai triển nhị thức, biến đổi thêm một chút thì ta được:

$$\boxed{f(n)=\dfrac{1}{2^{n}} \sum\limits_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} 5^kC_{n+1}^{2k+1}+\left\lfloor\dfrac{1-n}{1+n}\right\rfloor\left(2\left\lfloor\dfrac{n}{2}\right\rfloor-n\right);\;\;\forall n \in \mathbb{N}^*}$$


Ý nghĩa của công thức đã được sáng tỏ hơn nhiều. Từ công thức gợi ý ở trên, bạn hãy đưa ra một lời giải khác (lời giải của thầy Trần Nam Dũng) xem nào!