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

[chien than]

Xét tập $A=\{1;2;...;n\}$. Với bất kì tập con khác rỗng $M$ của $A$,

$$M=\left \{ m_1;m_2,...,m_k \right \}, m_1 > m_2 > ... > m_k$$

Đặt

$$S(M) = m_1 -  m_2 + m_3 +... + (-1)^{k+1}m_k$$

Tính $S = \sum_{M \subset A} S(M)$

 

 

[hxthanh]

Xin phép thầy Thế cho tôi giải bài này

Ta ký hiệu lại như sau:

Tổng cần tính là
$S_n=\sum_{k=1}^n f(k,n)$

với $f(k,n)$ là Tổng đan dấu các phần tử của mỗi tập con, tất cả các tập con có $k$ phần tử của $A$ trong đó phần tử lớn nhất mang dấu (+)

Ta sẽ chứng minh $f(k,n)=\left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}\quad(k\le n)\qquad(1)$
Rồi từ đó suy ra tổng cần tính là:
$$\boxed{\displaystyle S_n=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}=n.2^{n-1}}$$

Ta chứng minh $(1)$ bằng quy nạp theo $k$
Ta có:
$f(1,n)=1+2+...+n=\frac{n(n+1)}{2}=\left\lfloor\frac{1+1}{2}\right\rfloor {n+1\choose 1+1}$
Như vậy $(1)$ đúng với $k=1$
Giả sử $(1)$ đúng đến $k-1$ thỏa $1\le k-1<n$, ta chứng minh $(1)$ cũng đúng với $k$.
Xây dựng phép đếm $f(k,n)$ theo các tập con có phần tử lớn nhất là $j$ với $k\le j\le n$
Do $j$ là số lớn nhất nên
Có ${j-1\choose k-1}$ tập con $k$ phần tử bắt đầu bởi $j$
Bớt đi số hạng $j$ trong các tập con $k$ phần tử, ta được các tập con $k-1$ phần tử với phần tử lớn nhất là $j-1$
Như vậy ta có:

$\begin{align*}f(k,n)&=\sum_{j=k}^n \left(j{j-1\choose k-1}-f(k-1,j-1)\right)\\&=\sum_{j=k}^n \left(k{j\choose k}-\left\lfloor\frac{k}{2} \right\rfloor{j\choose k}\right)\quad\text{(Quy tắc hút + giả thiết quy nạp)}\\&=\left(k-\left\lfloor\frac{k}{2} \right\rfloor\right)\sum_{j=k}^n {j\choose k}\\&=\left\lfloor\frac{k+1}{2}\right\rfloor \sum_{j=k}^n \left[{j+1\choose k+1}-{j\choose k+1}\right]\quad\text{(Hermite và Pascal)}\\&=\left\lfloor\frac{k+1}{2}\right\rfloor{n+1\choose k+1}\end{align*}$

Suy ra điều phải chứng minh!


Sau đây là chứng minh đẳng thức
$\boxed{\displaystyle S_n=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}=n.2^{n-1}}$
Ta có:
$\begin{align*}S_n&=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}&\\&=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor\left[{n\choose k}+{n\choose k+1}\right]&\text{(Pascal)}\\&=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor{n\choose k+1}+\sum_{k=1}^n\left(k-\left\lfloor\frac{k}{2}\right\rfloor\right){n\choose k}&\text{(Hermite)}\\&=S_{n-1}+\sum_{k=1}^n k{n\choose k-1}-\sum_{k=1}^n\left\lfloor\frac{k}{2}\right\rfloor{n\choose k}&\\&=S_{n-1}+n\sum_{k=1}^n{n-1\choose k-1}-\sum_{k=0}^{n-1}\left\lfloor\frac{k+1}{2}\right\rfloor{n\choose k+1}&\text{(Lùi cơ số + Tịnh tiến)}\\&=S_{n-1}+n\sum_{k=0}^{n-1}{n-1\choose k}-S_{n-1}&\text{(Tịnh tiến)}\\&=\boxed{n2^{n-1}}&\end{align*}$

_______________________________
BÌNH LUẬN:
Bài toán này quả thực rất hay và khó! Hy vọng các bạn có thể tìm được lời giải đơn giản hơn!
Về lời giải trên, ta thấy rằng: bài toán là một sự kết hợp tổng thể giữa Tổ hợp, rời rạc với Số học bên cạnh đó còn phải thiết lập công thức truy hồi, kết hợp phán đoán và suy luận quy nạp và cuối cùng là các kỹ thuật tính toán với tổng!

Bên cạnh việc tìm được công thức $f(k,n)=\left\lfloor\frac{k+1}{2}\right\rfloor{n+1\choose k+1}$, ta thấy rằng nếu cho $k=n$ ta thu được đẳng thức:

$f(n,n)=n-(n-1)+(n-2)-...+(-1)^{n+1}.1=\left\lfloor\frac{n+1}{2}\right\rfloor$

Rất thú vị phải không các bạn!

[dark templar]

Bài này em nghĩ chỉ đơn giản thế này thôi

 

Đặt $S_{n}$ là tổng cần tính với tập $A=\{1;2;...;n \}$.

 

Đặt $P_{n}$ là số các tập con khác rỗng của $A=\{1;2;...;n \} \implies P_{n}=2^{n}-1$.

 

Ta thực hiện tính toán tổng $S_{n}$ qua các bước sau:

1. Ta tính tổng con đan dấu qua các tập con không chứa phần tử $n$ của $A$,tức là ta có $S_{n-1}$.
2. Ta tính tổng con đan dấu qua tập con chỉ chứa $n$ làm phần tử,suy ra kết quả là $n$.
3. Ta tính tổng con đan dấu của các tập con chứa $n$ và ít nhất 1 phần tử còn lại của tập $A$.Tổng này cho ta $P_{n-1}n-S_{n-1}$.

 

Như vậy tổng cần tính là $\boxed{\displaystyle S_{n}=S_{n-1}+n+P_{n-1}n-S_{n-1}=n(P_{n-1}+1)=n2^{n-1}}$.

___________________

@hxthanh: Hay quá!

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 22-04-2013 - 10:57

[PSW]

Chấm bài:

Hxthanh: 10 điểm

dark templar: 5 điểm