3 replies to this topic

[lehoangvu12]

Cho tập A gồm 6 phần tử của tập $S=\left \{ 0;1;2;...;14 \right \}$. CMR tồn tại hai tập con B và C của A (với B, C khác nhau và khác rỗng) sao cho tổng các phàn tử của B bằng tổng các phần tử của C.

[Phuong Thu Quoc]

Cho tập A gồm 6 phần tử của tập $S=\left \{ 0;1;2;...;14 \right \}$. CMR tồn tại hai tập con B và C của A (với B, C khác nhau và khác rỗng) sao cho tổng các phàn tử của B bằng tổng các phần tử của C.

Nếu chỉ ra $B=\left \{ 0;3 \right \};C=\left \{ 1;2 \right \}$ thì bài toán đã xong..

Nhìn thiếu đề!.

Vì A là tập có 6 phần tử nên có $2^{6}-1=63$ tập con khác rỗng

Mặt khác tập con có tổng phần tử lớn nhất là $9+10+11+...+14=69$ với đó chính là tập A

Loại bỏ tập đó ta còn 62 tập hợp với tổng các phần tử của 1 tập không vượt quá $10+11+...+14=60$

Vậy có 62 tập mà chỉ có 61 giá trị nên tồn tại 2 tập có tổng các phần tử bằng nhau.

Edited by Phuong Thu Quoc, 27-05-2014 - 15:18.

[Kool LL]

Nếu chỉ ra $B=\left \{ 0;3 \right \};C=\left \{ 1;2 \right \}$ thì bài toán đã xong..

Tập A chưa biết gồm 6 phần tử là gì thì sao có thể chỉ ra cụ thể tập B, C gồm những phần tử nào !!

Đây là dạng toán rời rạc, kiểu giống như nguyên lý Dirichlet vậy.

[I Am Gifted So Are You]

Mỗi tập con của A sẽ có tổng các phần tử nhỏ hơn 10+11+12+13+14=60
Mà A có 6 phần tử nên A sẽ có 62 tập con khác rỗng và nó

Nên theo Dirichlet ta có dpcm