Chủ đề này có 1 trả lời

[VMFdiendantoanhoc]

Problem: Cho tập hữu hạn $X$. Ta chọn ra $50$ tập con $A_1$, $A_2$, ..., $A_{50}$, mỗi tập đều chứa quá nửa số phần tử của $X$. Chứng minh rằng tồn tại tập con $A$ của $X$ sao cho số phần tử của $A$ không vượt quá $5$ và $A\cap{A_{i}}\neq{\varnothing}$, $\forall{i}=\overline{1,50}$

Bài viết đã được chỉnh sửa nội dung bởi VMFdiendantoanhoc: 30-10-2012 - 17:20

[The Gunner]

Vì mỗi tập đều chứa quá nửa phần tử của X nên ta có $|A_1|+|A_2|+...+|A_{50}|>\frac{50|X|}{2}=25|X|$ do đó theo Dirichlet phải có một phần tử thuộc ít nhất 26 tập. ta chọn phần tử đó thuộc tập A là $x_1$
Bỏ phần 26 tập trên xét 24 tập còn lại tương tự như trên phải tồn taị một phần tử thuộc ít nhất 13 tập, chọn phần tử này thuộc A là $x_2$
tương tự xét 11 tập còn lại thì phải có một phần tử $x_3$ thuộc ít nhất 6 tập.Lại xét 5 tập còn lại thì phải có $x_4$ thuộc ít nhất 3 tập. Xét 2 tập còn lại chọn phần tử $x_5$ chung của 2 tập này vì hai tập bất kì giao nhau . Do đó tồn tại tập A có $|A|\leq 5$ và $|A \cap A_i | \geq 1$. đpcm

Bài viết đã được chỉnh sửa nội dung bởi The Gunner: 30-10-2012 - 21:10