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
#1
Đã gửi 11-05-2017 - 07:55
- manhhung2013 yêu thích
#2
Đã gửi 14-05-2017 - 19:48
Ta xét bài toán sau:Hãy tìm số phần tử nhiều nhất lấy từ tập A sao cho không có phần tử nào có tổng chia hết 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í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ử.
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.
- manhhung2013 yêu thích
Chỉ có hai điều là vô hạn: vũ trụ và sự ngu xuẩn của con người, và tôi không chắc lắm về điều đầu tiên.
Only two things are infinite, the universe and human stupidity, and I'm not sure about the former.
#3
Đã gửi 14-05-2017 - 23:23
Bạn có thể thích rõ hơn các số 9 trong biểu thức : 10 + 9 + 9 + 9 + 9 + 1 = 47 được không ? Mình đã hiểu ý tưởng của bạn rồi.
#4
Đã gửi 15-05-2017 - 08:54
nhóm 1 có 9 phần tử thôi chứ {11,22,33,44,55,66,77,88,99}
#5
Đã gửi 15-05-2017 - 08:57
nhóm 1 có 9 phần tử thôi chứ {11,22,33,44,55,66,77,88,99}
nhóm 1 là nhóm chia 11 dư 1.
Bài viết đã được chỉnh sửa nội dung bởi Jinbei: 15-05-2017 - 08:58
#6
Đã gửi 15-05-2017 - 09:07
nhóm 1 là nhóm chia 11 dư 1.
ừ nhầm với nhsom dư 0
#7
Đã gửi 15-05-2017 - 09:09
10+9+9+9+9+1 = 47 phần tử. sao lại có số 1 nhỉ,nếu thề thì tồn tại 2 phần tử có tổng chia hết cho 11 rồi (nhóm 10 và nhóm 1)
#8
Đã gửi 15-05-2017 - 09:10
10+9+9+9+9+1 = 47 phần tử. sao lại có số 1 nhỉ,nếu thề thì tồn tại 2 phần tử có tổng chia hết cho 11 rồi (nhóm 10 và nhóm 1)
Mình cũng chưa hiểu chỗ đó lắm.
#9
Đã gửi 15-05-2017 - 09:31
đã hiểu ,chọn phàn tử đầu tiên vào nhóm 1 có nhiều phần tử nhất => có 10 cách chọn,phần tử tiếp theo nhom nào cũng đc vì chúng đều có 9 phần tử (trừ nhóm 10),ví dụ chọn nhóm 2 => có 9 cách chọn, phần tử tiếp theo (trừ nhóm 9) chọn nhóm 3 => có 9 cách chọn, phần tử tiếp theo chọn nhom 4 (trừ nhóm 8) có 9 cách , phần tử tiếp theo chọn nhóm 5 (trừ nhóm 6) có 9 cách,còn lại duy nhất nhom 0 chọn ra 1 phần tử nữa ,=> ở đây các nhóm đc chọn hết mọi phần tử của nhóm luôn=>có 10+9+9+9+9+1=47
#10
Đã gửi 15-05-2017 - 09:44
mọi người ai giải đc bài sau không ạ,mình nghĩ mãi vẫn chưa ra:
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ử
#11
Đã gửi 15-05-2017 - 19:43
làm như trên đó bạn
Chỉ có hai điều là vô hạn: vũ trụ và sự ngu xuẩn của con người, và tôi không chắc lắm về điều đầu tiên.
Only two things are infinite, the universe and human stupidity, and I'm not sure about the former.
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh