Question

[Thầy Cao Đô]

Cho $A$ là tập hợp gồm $6$ phần tử bất kỳ của tập hợp $\{0; \, 1; \, 2; \, ...; \, 14\}$. Chứng minh rằng tồn tại hai tập hợp con $B_1$ và $B_2$ của tập hợp $A$ (với $B_1$, $B_2$ khác nhau và khác rỗng) sao cho tổng tất cả các phần tử của tập hợp $B_1$ bằng tổng tất cả các phần tử của tập hợp $B_2$.

Answer 1

[Nguyễn Minh Châu]

Do \(A\) là tập hợp có \(6\) phần tử nên số tập hợp con khác rỗng và khác \(A\) của tập hợp \(A\) là: \(2^{6} - 2 = 62\) (tập hợp con).

Xét tập hợp \(X\) là tập con bất kì trong \(62\) tập hợp con trên và \(T \left(\right. X \left.\right)\) là tổng các phần tử của \(X\).

Tập hợp \(X\) có nhiều nhất \(5\) phần tử thuộc tập hợp \(\left{\right. 0 ; 1 ; 2 ; . . . ; 14 \left.\right}\) nên ta có:

\(0 \leq T \left(\right. X \left.\right) \leq 10 + 11 + 12 + 13 + 14 = 60\).

Như vậy với \(62\) tập hợp con của \(A\) như trên thì tồn tại \(62\) tổng không vượt quá \(60\).

Theo nguyên lí Dirichlet thì tồn tại hai tổng có giá trị bằng nhau. Điều đó chứng tỏ tồn tại hai tập hợp con \(B_{1}\), \(B_{2}\) của tập hợp \(A\) có tổng các phần tử của chúng bằng nhau.