Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


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
  • Giới tính:Nam
  • Đến từ:Vũ Trụ
  • Sở thích:Mathematics

Đã gửi 19-02-2015 - 00:00

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
  • Giới tính:Nam
  • Đến từ:PTNK - ĐHQG TPHCM
  • Sở thích:wild animal, furry

Đã gửi 15-11-2016 - 22:41

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
  • Giới tính:Nam
  • Đến từ:Nothingness
  • Sở thích:unknown

Đã gửi 27-11-2016 - 10:24

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





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

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