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

[khanghaxuan]

Tìm số tập con của tập $S=\begin{Bmatrix} 1;2;...;n \end{Bmatrix}$ mà 2 phần tử bất kì hơn kém nhau ít nhất 3 đơn vị 

[Karl Heinrich Marx]

Có 2 ý tưởng để đếm bài này, đầu tiên dễ thấy là truy hồi. Gọi $S_n$ là tập hợp các tập con thỏa mãn với $n$ thì một tập mà thuộc $S_{n+1}$ nó sẽ là một tập trong $S_n$ còn nếu không thì nó chứa $n+1$ suy ra các phần tử của nó bé hơn hoặc bằng $n-2$ mà thỏa mãn đk bài toán. Vậy $|S_{n+1}|=|S_{n-2}|+|S_n|$.

Ý tưởng thứ hai là lập một song ánh để cố phá cái điều kiện hơn kém ít nhất 3 đơn vị đi. Bây giờ giả sử một tập hợp thỏa mãn đề bài mà có $i$ phần tử là $a_1<a_2<...<a_i$ khi đấy nếu ta chuyển sang cái tập này ${b_j=2(i-j)+a_j, 1 \le j \le i}$ thì đây là một tập con bình thường của tập $S$ mà trong đó các phần tử của nó đều không nhỏ hơn $2i-1$. Ngược lại từ một tập con của $n$ có $i$ phần tử thỏa mãn $b_1<b_2<..<b_i$ và $b_1 \ge 2i-1$ khi đó lật lại ta có tập ${a_j=b_j-2(i-j), 1 \le j \le i}$ đây là một tập con thỏa mãn đề bài, vậy số tập con có $i$ phần tử thỏa mãn đề bài là ${n-2i+2\choose i}$. Cho $i$ chạy từ $0$ đến $n$ tính ra kết quả.

Kể ra ta thu được một đẳng thức tổ hợp bằng 2 cách đếm.

[hxthanh]

Đặt ra những đề toán như thế này không khó, nhưng giải quyết được nó thì lại là cả vấn đề. Không biết tác giả khanghaxuan đã mở rộng từ đâu khi post lên bài toán này? Vấn đề đáng nói ở đây là cái khoảng cách giữa các phần tử là 3 đơn vị này! Nếu khoảng cách chỉ là 2 đơn vị thì dễ dàng lập được dãy truy hồi Fibonacci. Khi khoảng cách là 3 đơn vị thì khác rồi nhé! (Đừng nói đến 4 hay 5 đơn vị).

Như phân tích của Karl Heinrich Marx ở trên, ta có dãy truy hồi:

 

$u_{n+1}-u_{n}-u_{n-2}=0$

Phương trình đặc trưng của nó là $x^3-x^2-1=0$

Phương trình này có nghiệm vô cùng "xấu xí" chưa nói đến việc tìm nghiệm khó khăn thế nào

 

Về cách đếm thứ hai, thì chung quy là thế này:

Nếu gọi tập con có $i$ phần tử sắp thứ tự tăng dần $(a_1,a_2,...,a_i)$ thỏa yêu cầu đề, thì ta có dãy bất đẳng thức:

$1\le a_1<a_2-2<a_3-2.2<...<a_i-2(i-1)\le n+2-2i$

Dãy này sẽ cho ta ${n+2-2i\choose i}$ cách chọn.

Về bản chất của tổng: $\quad S_n=\sum_{0\le i\le \frac{n+2}{2}} {n+2-2i\choose i}$

cũng phải đưa về dãy truy hồi mới có khả năng tính được!

 

Tuy rằng bằng hai cách đếm ta sẽ thu được một đẳng thức tổ hợp, nhưng trong trường hợp này có lẽ ta cũng chẳng thu hoạch được gì!

Thế mới nói, đặt ra đề toán không khó, nhưng để có một bài toán đẹp thì không dễ dàng chút nào!

[Karl Heinrich Marx]

Em cứ nghĩ là sẽ tính được để cho thêm thầy Thanh một đẳng thức vào bộ sưu tập chứ