Chủ đề này có 3 trả lời

[QUANVU]

Đặt $X=\{A_1,A_2,...,A_n\}$ là tập các tập con $3$ phần tử của $\{1,2,...,36\}$ sao cho
i)$A_i\cap A_j\neq \emptyset\forall i,j$ và
ii)$\cap_{i=1}^nA_i=\emptyset$.
Chứng minh rằng $n\leq 100$. Khi $n=100$ có bao nhiêu tập $X$ như vậy?

[DinhCuongTk14]

Bài này có thể giải như sau :
xét tập $ A_{i} $ bất kì và $A_{i}={a,b,c}$ khi đó có 2 th xảy ra :
Nếu các bộ (a,b) (b,c) (c,a) đều thuộc các tập $ A_{i} $ khác thì không tồn tại $ A_{j} $ mà không chứa bộ 2 nào
Ngược lại giả sử tồn tại (a,b) mà tất cả các bộ 3 (a,b,k) đều thuộc các $ A_{i} $ nói trên
xét một bộ 3 khác lí luận theo các cặp nói trên ta chỉ ra được đpcm
Số cặp có lẽ là 36C3

[vnm]

Dễ thấy tồn tại 2 bộ chỉ có 1 phần tử chung g/s là (a;b;c) và (a;d;e)
Do giao của 100 bộ khác rỗng nên tồn tại 1 bộ ko chứa a g/s (b;d;f) f có thể là c hay e
Chia các bộ còn lại thành 2 tập A các bộ có chứa a và B các bộ không chứa a
Các bộ thuộc A có giao với (b;d;f) nên chia 3 tập A1 các tập chứa (a;b);A2 các tập chứa (a;d)-không chứa b;A3 các tập chứa (a;f)-không chứa b,d
Nếu trong B có 1 tập không chứa b và d thì nó phải là (c;e;f) do nó có giao với 2 bộ (a;b;c)và (a;d;e);khi đó f khác c;e;dễ thấy do các bộ của A_i giao với bộ này suy ra $|A1|;|A2|\leq\ 2$;$|A_3|\leq\ 32$;các bộ còn lại thuộc B có dạng M các bộ (b;e;x) hay N các bộ (c;d;y) x khác a,b,e-33 khả năng;y khác c,d,a=33 khả năng;Nếu A_3 khác rỗng thì cố định 1 bộ (a;f;t) t khác b,d;1 phần tử (c;d;y) hay (b;e;x) có giao với nó thì y và x trùng f hay t-> |M|<=2;|N|<=2-> có nhiều nhất 4+2+2+2+2+32<100 bộ .
Nếu A3 rỗng thì có nhiều nhất 4+2+2+33.2<100 bộ
Nếu ko thì chia B làm 3 tập B1 các bộ chứa cả b và d;B2 các bộ chỉ chứa b-nên chứa (b;e) do có giao với (a;d;e);B3 các bộ chỉ chứa d-nên chứa (d;c) do có giao với (a;b;c)
nếu B1 hay A3 rỗng thì tập còn lại có ko quá 32 phần tử
nếu 2 tập đều ko rỗng:Xét 1 bộ cố định thuộc B1 là (b;d;x) 1 bộ thuộc A3 có dạng (a;f;y)->y=x
vậy trường hợp này cả B1 và A3 đều ko thể có hơn 1 bộ
nếu B2 hay A2 rỗng thì tập còn lại có <=32 phần tử
nếu 2 tập đều ko rỗng .Cố định 1 bộ thuộc B2 (b;e;y) 1 bộ thuộc A2 có dạng (a;d;x) x khác b;y khác d->x=y Vậy tập A2 có không quá 1 bộ;lí luận tương tự cũng có B2 ko quá 1 bộ
Cặp (B3;A1) làm tương tự nhưng khi B3 rỗng A1 có thể có 33 phần tử
Vậy số tập ko quá $3+(|A3|+|B1|)+(|A2|+|B2|)+(|A1|+|B3|)\leq\ 3+32+32+33=100$
Vậy có đpcm

Bài viết đã được chỉnh sửa nội dung bởi vnm: 02-03-2007 - 15:04

[bluesea]

có ai có lời giải ngắn hơn ko
DC viết rõ lời giải của mình ra đi