Bài 1. Cho A là tập con của {1,2,...,2008}, với mọi a,b thuộc A thì a+b không chia hết cho 1004 ,hỏi A có tối đa bao nhiêu phần tử
Bài 2. Cho A={1,2,...,100} chứng minh tập con gồm 48 phần tủ của A luôn tồn tại 2 phần tủ có tổng chia hết cho 11
Bài 1. Cho A là tập con của {1,2,...,2008}, với mọi a,b thuộc A thì a+b không chia hết cho 1004 ,hỏi A có tối đa bao nhiêu phần tử
Bài 2. Cho A={1,2,...,100} chứng minh tập con gồm 48 phần tủ của A luôn tồn tại 2 phần tủ có tổng chia hết cho 11
Bài 2. Cho A={1,2,...,100} chứng minh tập con gồm 48 phần tủ của A luôn tồn tại 2 phần tủ có tổng chia hết cho 11
Thật vậy, chia tập A thành 11 nhóm.Trong đó nhóm n là nhóm gồm những số chia 11 dư n (n=0,1,2,3..,10)
Nhận thấy nhóm 1 gồm có 10 phần tử, các nhóm còn lại có 9 phần tử.Vậy để không có hai số nào có tổng chia hết cho 11 thì nếu số đầu thuộc nhóm m thì số thứ hai không được thuộc nhóm 11-m.Từ m là các số (2,9);(3,8);(4,7);(5;6) chỉ có thể chọn ra tối đa nhóm.
Tính ra ta cần phải lấy số phần tử nhiều nhất là: 10+9+9+9+9+1 = 47 phần tử.(1 phần tử nhóm 0, 10 phần tử nhóm 1)
Vậy ta lấy được nhiều nhất 47 phần tử sao cho không có hai phần tử nào có tổng chia hết 11
Từ đây suy ra bất kì tập con nào của A có 48 phần tử đều có thể chọn ra 2 số chia hết 11.
Bài viết đã được chỉnh sửa nội dung bởi boyanonymous: 10-06-2017 - 20:22
Plz like for me if it help you. Thank you !
Bài 1. Cho A là tập con của {1,2,...,2008}, với mọi a,b thuộc A thì a+b không chia hết cho 1004 ,hỏi A có tối đa bao nhiêu phần tử
Ta chia tập đã cho thành 1004 tập nhỏ (1, 2007) , (2, 2006) , ( 3,2005) .........................(1003, 1005 ), (1004, 2008 )
Nếu số phần tử của A lớn hơn hoặc bằng 1005 thì theo nguyên lí Dirichlet sẽ có ít nhất 2 phần tử thuộc cùng 1 tập trong số các tập trên .
Giả sử 2 số đó là m và n thì m+n chia hết cho 1004 ( vô lí )
Vậy A có tối đa 1004 phần tử
SÓNG BẮT ĐẦU TỪ GIÓ
GIÓ BẮT ĐẦU TỪ ĐÂU ?
ANH CŨNG KHÔNG BIẾT NỮA
KHI NÀO...? TA YÊU NHAU .
0 thành viên, 1 khách, 0 thành viên ẩn danh