2 replies to this topic

[lehoan]

Trong một cuộc hội thảo quốc tế có n thành viên tham gia $(n>2)$.
Họ biết tổng cống 14 ngôn ngữ và biết :
1) Cứ 3 thành viên bất kì thì nói chung 1 ngoại ngữ
2) Mỗi ngoại ngữ có không quá nửa số thành viên nói được.
Hãy tìm số $n$ nhỏ nhất có thể được.

Edited by dark templar, 16-03-2013 - 15:43.

[Hr MiSu]

Cứ 3 người thì chọn ra 1 ngôn ngữ để trao đổi, số cách chọn ra ngôn ngữ là $\binom{n}{3}$ mà con số này không quá 14.$\frac{n}{2}$=7n, giải bất phương trình 

 $\binom{n}{3}$$\leq$7n ta được n$\leq$8, với n = 8 ta có cách chia ngôn ngữ như sau  1234, 5678, 1256, 3478, 1278,3456, 1357,2468,1368,2457,1458,2367,1467, 2358

Edited by Hr MiSu, 12-07-2018 - 02:21.

[duylax2412]

Người ta bảo tìm giá trị nhỏ nhất n mà. Lạ thay mình cũng ra $8$??

Gọi các thành viên là $1,2,..,n$ và các ngôn ngữ là $L_1;L_2;...;L_{14}$. Thiết lập bảng vuông $n$ dòng là các thành viên ; $14$ cột là các ngôn ngữ

Điền vào ô $ (L_i;j)$ số $1$ nếu $j$ nói được tiếng $L_i$ và số $0$ trong trường hợp ngược lại. Gọi $d(L_i)$ là số các số 1 điền vào cột $L_i$ ($d(L_i)\leq \frac{n}{2}$)

Mỗi cột có $\binom{d(L_i)}{3}$ bộ ba số $1$. Vậy trên bảng có tối đa $14\binom{\frac{n}{2}}{3}$ bộ ba số $1$ cùng cột

Với $3$ hàng tùy ý, luôn có  một cột có $3$ ô đánh số 1 ứng với ba hàng đó. Nên số các bộ ba ô điền số $1$ cùng cột $\geq$ số bộ ba hàng là $\binom{n}{3}$ Suy ra $\binom{n}{3} \leq 14\binom{\frac{n}{2}}{3} \Rightarrow n \geq 8$

$n=8$ chỉ ra như trên