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

[bangbang1412]

 Em đọc giải bài này mà không hiểu chi hết ai làm đơn giản giúp em được không

Cho các số nguyên dương $k,n$ thỏa mãn $n>k^{2}-k+1$ giả sử các tập $A_{1},A_{2},.......A_{n}$ thỏa mãn

a) $|A_{i}|=k$ với $1\leq i\leq n$

b) $|A_{i}\cup A_{j}|=2k-1$ 

Tính $|\cup_{i=1}^{n} A_{i}|$

 

[Karl Heinrich Marx]

Bài này nếu không cho điều kiện của $n$ mà bắt chứng minh hợp các tập đấy bé hơn 1 số nào đấy thì nó thuộc mấy bài toán đếm bằng 2 cách, em có thể đọc bài Counting in two ways hoặc xem chuyên đề tổ hợp mathscope (cái này cũng chỉ như người ta tổng hợp dịch các tài liệu tiếng anh sang tiếng Việt cho mình đọc).

Ở đây chỉ giải bằng Dirichlet để chỉ ra tất cả các tập này có chung 1 phần tử duy nhất.

Ta thấy theo đk đề bài thì 2 tập bất kì có chung đúng 1 phần tử. Bây giờ lấy ra 1 tập $A_i$ bất kì do nó chỉ có $k$ phần tử mà còn lại ít nhất $k(k-1)+1$ tập nên phải có 1 phần tử $x_i$ của $A_i$ chung với ít nhất $k$ tập khác. Tức là có ít nhất $k+1$ tập chứa $x_i$

Giờ xét một tập $A_j$ bất kì khác $k+1$ tập này. Nếu mà $A_j$ không chứa $x_i$ thì vì $A_j$ chỉ có $k$ phần tử nên phải có 1 phần tử $x_j$ của $A_j$ chung với ít nhất 2 tập trong $k+1$ tập kia, tức là có 2 tập trong $k+1$ tập kia chứa $x_j$, vậy ra giao của 2 tập này ko bé hơn 2, điều này vô lí. Vậy $A_j$ chứa $x_i$.

Chứng tỏ tất cả các tập đều chứa $x_i$. Vậy đáp án sẽ là $n(k-1)+1$.