Đến nội dung


Hình ảnh
- - - - -

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


  • Please log in to reply
Chủ đề này có 3 trả lời

#1 chien than

chien than

    Thượng sĩ

  • Thành viên
  • 272 Bài viết
  • Đến từ:Lớp 10 toán 1 trường ĐHSPHN

Đã gửi 20-09-2007 - 18:08

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)$

 

 



#2 hxthanh

hxthanh

  • Thành viên
  • 3327 Bài viết
  • Giới tính:Nam

Đã gửi 21-04-2013 - 23:13

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! :))


Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!

#3 dark templar

dark templar

    Kael-Invoker

  • Hiệp sỹ
  • 3788 Bài viết
  • Giới tính:Nam
  • Đến từ:TPHCM
  • Sở thích:Đọc fanfiction và theo dõi DOTA chuyên nghiệp

Đã gửi 22-04-2013 - 10:25

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

 

Đặ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á! :o


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

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#4 PSW

PSW

    Những bài toán trong tuần

  • Thành viên
  • 488 Bài viết
  • Giới tính:Nam

Đã gửi 25-05-2013 - 15:47

Chấm bài:

Hxthanh: 10 điểm

dark templar: 5 điểm


1) Thể lệ
2) Danh sách các bài toán đã qua: 1-100, 101-200, 201-300, 301-400
Còn chờ gì nữa mà không tham gia!  :luoi:
 





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh