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.
Cho tập A gồm 6 phần tử của tập $S=\left \{ 0;1;2;...;14 \right \}$
#1
Đã gửi 23-05-2014 - 09:33
#2
Đã gửi 25-05-2014 - 09:03
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.
Bài viết đã được chỉnh sửa nội dung bởi Phuong Thu Quoc: 27-05-2014 - 15:18
- lehoangvu12 yêu thích
Thà một phút huy hoàng rồi chợt tối
Còn hơn buồn le lói suốt trăm năm.
#3
Đã gửi 25-05-2014 - 17:06
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.
- lehoangvu12 yêu thích
#4
Đã gửi 26-05-2014 - 00:23
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
- lehoangvu12 yêu thích
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh