Dùng nguyên lí Dirichlet để giải bài toán tổ hợp-Phần 1

Bài toán: Gọi $n_1<n_2<..<n_{2000}<10^{100}$ là một số nguyên dương. Chứng minh rằng có thể tìm được hai tập A và B khác nhau không rỗng là tập con của {$n_1,n_2,..n_{2000}$} thỏa cấc điều kiện:

i) $|A|=|B|$

ii) $\sum_{x\in A}x=\sum_{x\in B}x$

iii) $\sum_{x\in A}x^2=\sum_{x\in B}x^2$

Lời giải

Lưu ý: $\binom{2000}{1000}$ là số hạng lớn nhất trong các số hạng $\binom{2000}{k}$.

Gọi S là tất cả tập con của tập {$n_1,n_2,..n_{2000}$} sao cho S có 1000 phần tử, ta có:

$0< \sum_{x\in S}x<1000.10^{100}$

$0< \sum_{x\in S}x^2<1000.10^{200}$

Vậy số các cặp $( \sum_{x\in S}x, \sum_{x\in S}x^2)$ ít hơn $10^{306}$

Mặt khác:

Số tập hợp chứa 1000 phần tử là: $\binom{2000}{1000}>\frac{\sum_{k=0}^{2000}\binom{2000}{k}}{2001}> \frac{2^{2000}}{2001}> \frac{10^{600}}{2001}>10^{306}$ 

Nên theo nguyên lí Dirichlet tồn tại hai tập hợp C và D chứa 1000 phần tử sao cho $( \sum_{x\in C}x, \sum_{x\in C}x^2)=( \sum_{x\in D}x, \sum_{x\in D}x^2)$

Loại bỏ các phần tử chung của C và D ta thu được hai tập A và B thỏa mãn điều kiện đề bài.