Chứng minh rằng $2$ tập bất kỳ có đúng $n$ phần tử chung
#1
Đã gửi 11-07-2012 - 21:57
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!
#2
Đã gửi 16-07-2012 - 07:55
Gọi số tập chứa $x_i$ là $a_i$ thì ta đếm số cặp tập có cùng phần tử. là $$ \sum\limits_{k=1}^{4n+3}C_{a_k}^2=\sum\limits_{k=1}^{4n+3}\frac{a_k^2-a_k}{2} \ge \frac{\left( \sum\limits_{k=1}^{4n+3}a_k \right)^2}{2(4n+3)}-\frac{\sum\limits_{k=1}^{4n+3}a_k}{2} \ge \frac{(4n+3)(2n+1)^2}{2}-\frac{(4n+3)(2n+1)}{2}=n.(4n+3)(2n+1)$$Xét tập hợp $ \mathcal{M} = \{ x_1 ; x_2 ; ...; x_{4n+3} \}$ . $ A_1 ; A_2 ; ... A_{4n+3}$ là các tập con phân biệt của $ \mathcal{M}$ ; mỗi tập này có số phần tử không ít hơn $2n+1$. Đồng thời; với $n+1$ phần tử bất kỳ chọn ra từ $ \mathcal{M}$; có đúng một tập $A_{k} ; 1 \le k \le 4n+3$ chứa $n+1$ phần tử trên. Chứng minh rằng $2$ tập bất kỳ trong $4n+3$ tập hợp trên có đúng $n$ phần tử chung
bất đẳng thức cuối suy ra vì $\sum\limits_{k=1}^{4n+3}a_k \ge (2n+1)(4n+3)$
Tuy nhiên cứ 2 tập bất kì thì được ghép với nhau không quá $n$ lần nên suy ra số cặp này phải không vượt quá:
$nC_{4n+3}^2=n(4n+3)(2n+1)$
Như vậy theo trên thì đẳng thức phải xảy ra khi đó 2 tập bất kì có chung đúng $n$ phần tử.
- perfectstrong, hxthanh, wallunint và 1 người khác yêu thích
#3
Đã gửi 16-07-2012 - 08:31
Hình như sai gì đó rồi anh ơiGọi số tập chứa $x_i$ là $a_i$ thì ta đếm số cặp tập có cùng phần tử. là $$ \sum\limits_{k=1}^{4n+3}C_{a_k}^2=\sum\limits_{k=1}^{4n+3}\frac{a_k^2-a_k}{2} \ge \frac{\left( \sum\limits_{k=1}^{4n+3}a_k \right)^2}{2(4n+3)}-\frac{\sum\limits_{k=1}^{4n+3}a_k}{2} \ge \frac{(4n+3)(2n+1)^2}{2}-\frac{(4n+3)(2n+1)}{2}=n.(4n+3)(2n+1)$$
bất đẳng thức cuối suy ra vì $\sum\limits_{k=1}^{4n+3}a_k \ge (2n+1)(4n+3)$
Tuy nhiên cứ 2 tập bất kì thì được ghép với nhau không quá $n$ lần nên suy ra số cặp này phải không vượt quá:
$nC_{4n+3}^2=n(4n+3)(2n+1)$
Như vậy theo trên thì đẳng thức phải xảy ra khi đó 2 tập bất kì có chung đúng $n$ phần tử.
Nếu như vì $\sum\limits_{k=1}^{4n+3}a_k \ge (2n+1)(4n+3)$ thì chỗ dưới đây sai rồi anh:
\[\frac{{{{\left( {\sum\limits_{k = 1}^{4n + 3} {{a_k}} } \right)}^2}}}{{2(4n + 3)}} - \frac{{\sum\limits_{k = 1}^{4n + 3} {{a_k}} }}{2} \geqslant \frac{{(4n + 3){{(2n + 1)}^2}}}{2} - \frac{{(4n + 3)(2n + 1)}}{2}\]
Bài viết đã được chỉnh sửa nội dung bởi wallunint: 16-07-2012 - 08:48
Vì cuộc sống luôn thay màu .... !!!
#4
Đã gửi 16-07-2012 - 08:32
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#5
Đã gửi 16-07-2012 - 08:37
- perfectstrong yêu thích
#6
Đã gửi 16-07-2012 - 12:04
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#7
Đã gửi 16-07-2012 - 12:11
Mỗi tập có ít nhất $2n+1$ phần tử nên $4n+3$ tập phải có ít nhất là $(4n+3)(2n+1)$ tổng số phần tử, tổng số phần tử cũng chính bằng tổng số lần xuất hiện của các phần tử.Anh giải thích giúp em tại sao $\sum\limits_{k=1}^{4n+3}a_k \ge (2n+1)(4n+3)$ ạ?
- NguyThang khtn, perfectstrong và wallunint thích
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh