Đến nội dung

Hình ảnh

Chứng minh rằng: $\left | S_1 \right |-\left | S_2 \right |\leq C_{k}^{\frac{k}{2}}$

- - - - - xông đất vmf

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

#1
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

Cho $k$ là số nguyên dương chẵn. $N$ là tích của $k$ số nguyên tố phân biệt $p_1,...,p_k$.  $a,b$ là hai số nguyên dương phân biệt sao cho $a \leq b \leq N$. Gọi $S_1$ và $S_2$ là hai tập thỏa mãn:$ S_1=\{d| $ $ d|N, a\leq d\leq b, d $ có số ước nguyên tố chẵn $\}$, $ S_2=\{d| $ $ d|N, a\leq d\leq b, d $ có số ước nguyên tố lẻ $\}$. Chứng minh rằng: $\left | S_1 \right |-\left | S_2 \right |\leq C_{k}^{\frac{k}{2}}$


Bài viết đã được chỉnh sửa nội dung bởi LNH: 19-02-2015 - 20:10


#2
redfox

redfox

    Trung sĩ

  • Thành viên
  • 100 Bài viết

Ta chuyển bài toán về dạng tổng quát hơn: Cho tập $S$ gồm số chẵn phần tử, mỗi tập con được gán một số từ $1$ đến $2^k$ sao cho nếu $A\subset B$ thì số gán cho $B$ lớn hơn. $S_1$ là tập các tập con được gán số $a\leq x\leq b$ có số phần tử chẵn, $S_2$ định nghĩa tương tự.

Nếu hai tập con chẵn trong $S_1$ thỏa $A\subset B$ thì giữa nó có một tập con lẻ trong $S_2$, nếu ta bỏ một trong hai tập con trên và bỏ phần tử lẻ thì hiệu trên không giảm. Vậy ta chỉ cần chứng minh: Nếu tập $I$ gồm các tập con của $S$ không có tập nào là con của tập kia thì $\left | I \right |\leq C_k^{\frac{k}{2}}$.

Gọi $N_i$ là tập các tập con có $i$ phần tử. Ta sẽ chứng minh tồn tại đơn ánh $f_i$ từ $N_i$ đến $N_{i+1}$ thỏa $A\subset f(A)$với $i<\frac{k}{2}$.

Xét đồ thị lưỡng phân $G=(N_i\cup N_{i+1},E)$, nếu $A\subset B$ thì $A$ nối với $B$. Với $X\subset N_i$, số các cạnh nối với $X$ là $E=(k-i)\left | X \right |$, bậc của các phần tử của $N_{i+1}$ là $i$ nên $E$ không lớn hơn $i\left | G(X) \right |$ mà $k-i>i$ nên $G(X)\geq X$, áp dụng định lí Hall ta có điều phải chứng minh.

Tương tự tồn tại đơn ánh $f_i$ từ $N_i$ đến $N_{i-1}$ với $i>\frac{k}{2}$ và $f(A)\subset A$. Sử dụng các đơn ánh, ta đưa các tập con của $I$ về các tập con có $\frac{k}{2}$ phần tử. Vì không có tập nào là con của tập kia nên các tập con sau khi chuyển đổi phân biệt. Vậy $\left | I \right |\leq\left | N_{\frac{k}{2}} \right |=C_k^{\frac{k}{2}}$.

(Q.E.D)

Có cách nào đơn giản hơn không?


Bài viết đã được chỉnh sửa nội dung bởi baopbc: 16-11-2016 - 09:19


#3
the unknown

the unknown

    Thượng sĩ

  • Thành viên
  • 208 Bài viết

Mình chứng minh tính chất " Nếu $I$ là họ tập con của $S$ sao cho không có tập nào là tập con của tập khác thì $\left | I \right |\leq \binom{n}{\frac{n}{2}}$" theo một cách khác.

Ta sẽ đếm số các chuỗi tập con $B_1,B_2,..,B_n$ của $S$ thỏa $B_1\subset B_2\subset ...\subset B_n$ và $\left | B_i \right |=i $ $\forall i=1,2,...,n$. Dễ thấy rằng từ tập $B_n$, có $n$ cách chọn ra môt phần tử và nếu loại phần tử đó đi thì ta được tập $B_{n-1}$ và tương tự cũng có $n-1$ cách chọn ra tập $B_{n-2}$ và cứ thế. Suy ra rằng số chuỗi các tập con này đúng bằng $n!$ ( do trong cách chọn không có chuỗi nào trùng nhau).

Cố định một tập $A$ có $k$ phần tử, bằng cách tương tự như trên ta thấy rằng số chuỗi các tập con thỏa $B_1\subset B_2\subset ,,,\subset B_{k-1}\subset A\subset B_{k+1}\subset ...\subset B_n$ và $\left | B_i \right |=i$ $\forall i=1,2,...,n$ là $(n-k)!k!$.

Ta thấy rằng với hai tập con khác nhau $A,B$ thuộc $I$ thì do $A,B$ không có tập nào là tập con của tập khác nên chuỗi các tập con lập được từ $A$ và $B$ là phân biệt. Như vậy nếu giả sử rằng $I$ có $k$ tập con là $A_1,A_2,...,A_k$ thì khi đó số chuỗi có thể tạo thành như trên là $\sum _{i=0}^k(n-i)!i!$.

Vậy ta có: 

$\sum _{i=0}^k(n-i)!i!\leq n!\Leftrightarrow \sum _{k=0}^n\frac{1}{\binom{n}{i}}\leq 1$

 

Để ý rằng ta có $\binom{n}{i}\leq \binom{n}{\frac{n}{2}}\forall i=1,2,...,n$. nên ta có $\frac{k}{\binom{n}{\frac{n}{2}}}\leq 1\Leftrightarrow k\leq \binom{n}{\frac{n}{2}}$.

Vậy ta có điều phải chứng minh.


$\texttt{If you don't know where you are going, any road will get you there}$





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

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