Đã gần $2$ năm rồi!
Mình thật sự muốn duy trì và phát triển topic này nhưng biết khả năng có hạn nên hi vọng các bạn nhiệt tình ủng hộ!
Để hâm nóng lại topic, mình xin làm
Bài 5 Trích:
Nguyên văn bởi daylight  Bài 5: Cho $11 $ tập hợp $M_1,M_2,...,M_{11}, $ mỗi tập có $5 $ phần tử và thỏa mãn $M_i \cap M_j \not=\O \ ,\forall 1 \le i < j \le 11. $
Gọi $m $ là số lớn nhất sao cho tồn tại các tập $M_{i_1},M_{i_2},...,M_{i_m} $ trong số các tập đã cho sao cho $\cap_{k=1}^m M_{i_k} \not= \O $.
Hỏi giá trị nhỏ nhất của $m $ là bao nhiêu ? |
Mình diễn giải một chút như sau: Ý của đề là tìm giá trị $m$ nhỏ nhất sao cho trong $11$ tập hợp đã cho tồn tại $m$ tập hợp $M_{i_1},M_{i_2},...,M_{i_m}$ sao cho $\cap_{k=1}^m M_{i_k} \not= \varnothing $ và không tồn tại một số $n>m$ nào mà tồn tại $n$ tập hợp $M_{i_1},M_{i_2},...,M_{i_n}$ sao cho $\cap_{k=1}^n M_{i_k} \not= \varnothing $, tức là với mọi $n>m$ thì với mọi $n$ tập hợp $M_{i_1},M_{i_2},...,M_{i_n}$ bất kì trong $11$ tập đã cho, giao của chúng bằng rỗng.
Lời giải:
Để dễ nêu ví dụ, mình giả sử tập hợp đề cho là tập các số.
$m=4$ là giá trị thỏa đề, ví dụ như sau:
$M_1=\left \{ 1;2;3;4;{\color{Red} 5} \right \}$
$M_2=\left \{ 1;{\color{Red} 6};{\color{Red} 7};{\color{Red} 8};{\color{Blue} 9} \right \}$
$M_3=\left \{ 2;{\color{Red} 6};{\color{Red} {10}};{\color{Blue} {11}};{\color{Red} {12}} \right \}$
$M_4=\left \{ 3;{\color{Red} 7};{\color{Red} {10}};{\color{Blue} {13}};14 \right \}$
$M_5=\left \{ 4;{\color{Red} 8};{\color{Blue} {11}};{\color{Blue} {13}};15 \right \}$
$M_6=\left \{ {\color{Red} 5};{\color{Blue} 9};{\color{Red} {12}};14;15 \right \}$
$M_7=\left \{ 1;{\color{Red} {10}};15;16;{\color{Red} {17}} \right \}$
$M_8=\left \{ 4;{\color{Red} 6};14;16;{\color{Red} {17}} \right \}$
$M_9=\left \{ 2;{\color{Red} 7};15;16;{\color{Red} {17}} \right \}$
$M_{10}=\left \{ 3;{\color{Red} 8};{\color{Red} {12}};14;16 \right \}$
$M_{11}=\left \{ 1;2;3;4;{\color{Red} 5} \right \}$
Sự lặp lại các số như sau:
Số lặp lại ${\color{Blue} {2}}$ lần: ${\color{Blue} {9;11;13}}$,
Số lặp lại ${\color{Red} {3}}$ lần: ${\color{Red} {5;6;7;8;10;12;17}}$,
Số lặp lại $4$ lần: $1;2;3;4;14;15;16$.
Do đó không có trá trị lớn hơn $4$ nào thỏa đề.
Bây giờ ta đi chỉ ra mâu thuẫn khi $m$ nhận giá trị nhỏ hơn $4$.
Vì $m<4$ nên ta giả sử sự lặp lại của các số trong $11$ tập hợp như sau:
1/. Có $x_1$ số lặp lại $1$ lần,
2/. Có $x_2$ số lặp lại $2$ lần,
3/. Có $x_3$ số lặp lại $3$ lần.
suy ra $x_1+2x_2+3x_3=55$
Theo đề, giao của $2$ tập bất kì khác rỗng nên khi lấy giao giữa $2$ tập hợp kì, ta nhận được ít nhất $1$ phần tử giao.
Do có $11$ tập hợp nên ta nhận được ít nhất $C_{11}^{2}=55$ phần tử giao (các phần tử giao có thể trùng nhau).
Tuy nhiên mỗi số lặp lại $2$ lần cho ta $C_{2}^{2}=1$ phần tử giao và mỗi số lặp lại $3$ lần cho ta $C_{3}^{2}=3$ phần tử giao, còn các số chỉ lặp lại $1$ lần tất nhiên không cho ta phần tử giao nào. Do vậy, ta nhận được $1.x_2+3.x_2=55-(x_1+x_2)$ phần tử giao.
Rõ ràng $55\geq 55-(x_1+x_2)\Leftrightarrow x_1+x_2\geq 0\Rightarrow x_1=x_2=0\Rightarrow x_3=\frac{55}{3}$: vô lí!
Vậy $m=4$ là giá trị thỏa đề.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]