Đến nội dung

Hình ảnh

Chứng minh rằng $2$ tập bất kỳ có đúng $n$ phần tử chung

- - - - -

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

#1
PSW

PSW

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

  • Quản trị
  • 493 Bài viết
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
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:

#2
Karl Heinrich Marx

Karl Heinrich Marx

    Sĩ quan

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

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

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

#3
wallunint

wallunint

    Thượng sĩ

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

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

Hình như sai gì đó rồi anh ơi :D
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
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4990 Bài viết
Hình như anh nhầm từ chỗ suy ra cái $\ge$ thứ 2 rồi ạ. Có dấu - mà anh?
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#5
Karl Heinrich Marx

Karl Heinrich Marx

    Sĩ quan

  • Thành viên
  • 321 Bài viết
Bây giờ xét hàm $f(x)=x^2-(4n+3)x$ thì $f'(x)=2x-(4n+3)$ nên hàm này đồng biến với $x \ge (2n+1)(4n+3)$.

#6
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4990 Bài viế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)$ ạ?
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#7
Karl Heinrich Marx

Karl Heinrich Marx

    Sĩ quan

  • Thành viên
  • 321 Bài viế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)$ ạ?

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ử.




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

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