Đến nội dung

Hình ảnh

Dirichlet và tính chất phần tử tập hợp

- - - - -

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

#1
vanduongts

vanduongts

    Trung sĩ

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

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 



#2
boyanonymous

boyanonymous

    Binh nhì

  • Thành viên mới
  • 14 Bài viế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 

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 !


#3
viet9a14124869

viet9a14124869

    Trung úy

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

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 .





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

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