các bác giúp em với 1.Cho X={1,2,3,..,p} với p là số nguyên tố .có bao nhiêu tập con A của X thoả /A/=p và tổng các phần tử của A chia hết cho p 2.tìm số phân hoạch 1 tập n phần tử thành k tập (1<=k<=n) từ đó suy ra số phân hoạch tập n ptử. (Xin cám ơn các bác nhiều])
Bài 2 ban có thể đoc trong cuốn "tổ hơp " nhà xuất bản đai hoc quốc gia hay môt quyển nào về tổ hơp ,có cả thuât toán trên PC nữa đây,viết ra đây e không kĩ bằng đâu.
Goi S(n,k)so cac phan hoach tap n pt thanh k tap 1> S(n,k)=S(n-1,k-1)+k*S(n-1,k) voi o<k<n S(n,n)=1;S(n,0)=0; 2> S(n,k)=tong(S(i,k-1)*C(i,n-1)) voi k>=2 ; tong theo i voi :i=k- 1...n-1 C(i,n-1) =to hop chap i cua n-1; 3> So tat ca cac phan hoach (k=0...n) la B(n,k)=tong( C(i,n-1)* B(n,i) ) voi i chay tu 0.den..n ;B(n,0)=1;
Bay gio cac nho cac bac sieu toan giai giup bai nay ( nho cac bac gui nhanh giup em ) " Cho 2n-1 so nguyen bat ki , cmr luon tim duoc n so co tong chia het cho n ."
*Trước hết ta chứng minh với trường hợp n=p là 1 số nguyên tố Nếu trong 2p-1 số có p số có cùng số dư khi chia cho p thì xong! Nếu không, ta có thể sắp xếp 2p-1 số đó dưới dạng a1,b1,a2,b2,...,ap-1,bp-1,a sao cho ai khác bi với mọi i (Tại sao? ) Ta chứng minh bằng quy nạp rằng từ 2k số đầu tiên ta tìm được k+1 tổng của k số mà số dư khi chia cho p của chúng là khác nhau k=1: a1 <> b1 ==> hiển nhiên đúng Giả sử đúng với k-1, tức là có k tổng S1,S2,...,Sk của k-1 số chia cho p nhận các số dư khác nhau Ta chứng minh khẳng định cho k Xét nhóm 1gồm các số S1+ak, S2+ak,..., Sk+ak và nhóm 2 gồm các số S1+bk,...,Sk+bk Fải có 1 số trong nhóm 2 khác các số trong nhóm 1 vì nếu không thì ta sẽ có k(bk-ak) chia hết cho p ==> vô lý ==> khẳng định đúng Do đó trong 2p-2 số đầu tiên có p tổng là G1,...,Gp của p-1 số chia cho p nhận các số dư khác nhau ==> G1+a,...,Gp+a là p tổng cua p số chia cho p nhận các số dư khác nhau ==> tồn tại 1 tổng p số chia hết cho p *Nếu đúng với n=p, n=q thì đúng với n=p.q ==> dễ dàng = cách xét 2q-1 lần 2p-1 số, sau đó xét tiếp ==> ĐPCM!
