Các bài toán tổ hợp hay được sưu tầm:
Bài 1:(HSGS-TST 2014 vòng 1):Cho tập S gồm 2015 phần tử.Xét n tập con $A_i$ phân biệt của S($n <2^{2015}$).Đặt $B_i=S-A_i$ với $i=1,n$.Với mỗi i ta đánh dấu 1 trong 2 tập $A_i,B_i$.Tìm n bé nhất để với mọi cách đánh dấu và cách chọn tập con thì hợp các tập đánh dấu là S.
Bài 1':(cách diễn đạt khác và tổng quát cho bài 1):Cho n số tự nhiên từ 1 đến n,xét k miếng bìa,mỗi miếng viết một tập con của n phần tử và mặt kia viết những số mà mặt này chưa viết,.Tìm k bé nhất để với mọi cách lật mặt bìa thì luôn xuất hiện đủ các số từ 1 đến n
Lời giải(Cho trường hợp tổng quát)
Đáp án là $[log_2n]+1$ hay nói cách khác là số k bé nhất thỏa $2^k>n$
Xét $2^{k+1}>n\ge 2^k$
Giả sử ta chỉ chọn k miếng bìa,khi đó ta chỉ ra một cách chọn ko thỏa bài toán
Chỉ cần xét các số từ 1 đến $2^k$,miếng bìa thứ i viết bằng cách xét miếng bìa thứ i-1,lấy 1 nửa trong khoảng 1 đến $2^{k-1}$ cho sang mặt bên kia,các chọn này chỉ ra k ko thỏa
Ta chứng minh $k+1$ thỏa
Ta gọi một cách lật là t thiếu nếu số t ko xuất hiện
Dễ thấy ko có 2 cách lật cùng là t thiếu,mà số cách lật là $2^{k+1}>n$ nên tồn tại cách lật không thiếu số nào
Bài 2:(Problem solving method):Một ngôi làng nọ có một số hữu hạn hội,mỗi hội có ít nhất 1 người.Biết rằng 2 hội chung nhiều nhất 1 người và mỗi người tham gia ít nhất k hội.CMR:Có k hội có số thành viên như nhau.
Lời giải:
Đây là một bài toán điển hình của nguyên lí cực hạn và Dirichlet
Gọi A là hiệp hội có nhiều người nhất(gồm n người) và B là tập các hiệp hội có 1 người quen chung với A
Khi đó do mỗi người trong A tham gia k-1 hội khác,và mỗi hội trong B chứa đúng một người trong A nên ta có $|B|\ge n(k-1)$ nên số hội $\ge n(k-1)+1$(tính cả A),khi đó theo NL Dirichlet tồn tại $[\frac{n(k-1)+1-1}{n}]+1=k$ hội có số người như nhau
Bài 3:Cho n đường thẳng trên măt phẳng sao cho không có 2 đt nào song song và không có 3 đường thẳng đồng quy.CMR:Ta có thể tô ít nhất $[\sqrt\frac{n}{2}]$
Lời giải:
Không có nhận xét nào:
Đăng nhận xét