Không thấy bạn nào "mở hàng" nên đành "chém" tạm bài 1 vậy. Bạn nào có cách giải hay hơn xin cùng thảo luận.
Bài 1 a) E={1,2,3,4,5,6,7,8}; k=3. Cách "nông dân" nhất là liệt kê các tập con X = {a,b,c} 3 phần tử là các số không liên tiếp nhau
vì nếu có 2 số liên tiếp b=a+1 chẳng hạn thì |b-a|=1<2 không thỏa yêu cầu đề bài
{1,3,5}{1,4,6}{1,5,7}{1,6,8}
{1,3,6}{1,4,7}{1,5,8}
{1,3,7}{1,4,8}
{1,3,8}
{2,4,6}{2,5,7}{2,6,8}
{2,4,7}{2,5,8}
{2,4,8}
{3,5,7}{3,6,8}
{3,5,8}
{4,6,8}
Tất cả là 20 tập con như vậy
$(20=C_6^3)$
Liệt kê ra vậy có lợi ích gì không?Xin trả lời là ít nhất nó cũng gợi ý cho ta giải quyết bài toán tổng quát 1b.
Bài 1 b)E={1,2,...,n}
Xét với k=2. Cần liệt kê ra tất cả các tập con 2 phần tử không liên tiếp nhau
1: từ 3 đến n có n-2 số không liên tiếp với 1
2: từ 4 đến n có n-3 số không liên tiếp với 2
...
n-2: từ n đến n có 1 số không liên tiếp với n-2
Do đó:
$X_n^2=1+2+...+n-2=\dfrac{(n-2)(n-1)}{2}$. ($=C_{n-1}^2$)
Xét với k=3. Cần liệt kê ra tất cả các tập con 3 phần tử không liên tiếp nhau
1: từ 3 đến n chọn 2 số không liên tiếp có $X_{n-2}^2=C_{n-3}^2$ cách
2: từ 4 đến n chọn 2 số không liên tiếp có $X_{n-3}^2=C_{n-4}^2$ cách
...
n-4: từ n-2 đến n chọn 2 số không liên tiếp có $X_3^2=C_2^2$ cách
Do đó:
$X_n^3=\sum\limits_{k=2}^{n-3}C_k^2=\sum\limits_{k=2}^{n-3}(C_{k+1}^3-C_k^3)=C_{n-2}^3$
...
Tổng quát $X_n^k=C_{n-k+1}^k$, với $ 2 \leq k \leq \lfloor\dfrac{n+1}{2}\rfloor$ ( * )
Đến đây dễ dàng CM ( * ) bằng quy nạp.
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 15-12-2010 - 13:05
