Cho tập hợp $V = \{ 1; 2; 3;...; 99; 100 \} $và $A$ là tập hợp con có $11$ phần tử của V. Chứng minh rằng tồn tại hai tập hợp con khác rỗng không giao nhau của $A$ sao cho tổng các phần tử của chúng bằng nhau
Tập hợp
Bắt đầu bởi zaizai, 14-04-2008 - 11:40
#1
Đã gửi 14-04-2008 - 11:40
#2
Đã gửi 15-04-2008 - 18:07
Giải thử xem nào
Từ tập A có 11 phần tủ có thể lập được ( - tập rỗng ) là $ 2^11-1 = 2047 $ tập con
Vì mỗi thằng tập con có max 11 phần tử và tổng của nó phải < $ 100+99+98+....+90= 90.11+ (1+2+...+10)= 990+ 55 = 1045 $
Theo Dirichlet thì t?#8220;n tại ít nhất 2 thằng có tổng số phần tử bằng nhau giả sử là $ A_1 , B_1 $
Nếu 2 thằng đó giao bằng rỗng thì dpcm
Nếu 2 thằng đó giao khác rỗng tức $ A_1= (a_1,a_2,...a_k,d_1,d_2,...d_p) ; A_2=(b_1,b_2,....b_j,d_1,d_2,...d_p) $ với $ \sum\limits_{i=1}^{k}a_i = \sum\limits_{i=1}^{j}b_i $
=> tập $ A_2= A_1 $ \ $ (d_1,d_2,...d_p) $ và $ B_2= \B_1 $ \ $ (d_1,d_2,...d_p) $ là cần tìm
Từ tập A có 11 phần tủ có thể lập được ( - tập rỗng ) là $ 2^11-1 = 2047 $ tập con
Vì mỗi thằng tập con có max 11 phần tử và tổng của nó phải < $ 100+99+98+....+90= 90.11+ (1+2+...+10)= 990+ 55 = 1045 $
Theo Dirichlet thì t?#8220;n tại ít nhất 2 thằng có tổng số phần tử bằng nhau giả sử là $ A_1 , B_1 $
Nếu 2 thằng đó giao bằng rỗng thì dpcm
Nếu 2 thằng đó giao khác rỗng tức $ A_1= (a_1,a_2,...a_k,d_1,d_2,...d_p) ; A_2=(b_1,b_2,....b_j,d_1,d_2,...d_p) $ với $ \sum\limits_{i=1}^{k}a_i = \sum\limits_{i=1}^{j}b_i $
=> tập $ A_2= A_1 $ \ $ (d_1,d_2,...d_p) $ và $ B_2= \B_1 $ \ $ (d_1,d_2,...d_p) $ là cần tìm
Bài viết đã được chỉnh sửa nội dung bởi MyLoveIs4Ever: 15-04-2008 - 18:08
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh