Đến nội dung

Hình ảnh

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


  • Please log in to reply
Chủ đề này có 10 trả lời

#1
vanduongts

vanduongts

    Trung sĩ

  • Thành viên
  • 113 Bài viết
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

#2
duylax2412

duylax2412

    Trung sĩ

  • Thành viên
  • 191 Bài viết

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.


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.

ALBERT EINSTEIN

 

 


#3
Jinbei

Jinbei

    Binh nhất

  • Thành viên mới
  • 38 Bài viết

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
vanduongts

vanduongts

    Trung sĩ

  • Thành viên
  • 113 Bài viết

nhóm 1 có 9 phần tử thôi chứ {11,22,33,44,55,66,77,88,99}



#5
Jinbei

Jinbei

    Binh nhất

  • Thành viên mới
  • 38 Bài viết

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
vanduongts

vanduongts

    Trung sĩ

  • Thành viên
  • 113 Bài viết

 nhóm 1 là nhóm chia 11 dư 1. 

ừ nhầm với nhsom dư 0



#7
vanduongts

vanduongts

    Trung sĩ

  • Thành viên
  • 113 Bài viết

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
Jinbei

Jinbei

    Binh nhất

  • Thành viên mới
  • 38 Bài viết

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
vanduongts

vanduongts

    Trung sĩ

  • Thành viên
  • 113 Bài viết

đã 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
vanduongts

vanduongts

    Trung sĩ

  • Thành viên
  • 113 Bài viết

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
duylax2412

duylax2412

    Trung sĩ

  • Thành viên
  • 191 Bài viết

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.

ALBERT EINSTEIN

 

 





0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh