Cho 1985 tập hợp, mỗi tâp hợp gồm 45 phần tử, 2 tập hợp bất kì chứa chung đúng 1 phần tử. Hỏi có bao nhiêu phần tử trong tất cả 1985 tập hợp trên.
có bao nhiêu phần tử trong tất cả 1985 tập hợp
#1
Đã gửi 03-06-2014 - 01:16
#2
Đã gửi 03-06-2014 - 08:56
Ta xét bài toán tổng quát như sau:Cho các số nguyên dương $k,n$ thỏa mãn $n> k^{2}-k+1$.Giả sử có $n$ tập $A_{1},A_{2},...A_{n}$ mà $\left |A_{i}\bigcap A_{j} \right |=1(i\neq j,1\leq i,j\leq n)$ và $\left | A_{i} \right |=k(1\leq i\leq n)$
thì $\left | A_{1}\bigcup A_{2} \bigcup ...\bigcup A_{n}\right |=n(k-1)+1$
Xét tập bất kì chẳng hạn $\left | A_{1}\bigcap A _{i}\right |=1(2\leq i\leq n)$
Vì $\left | A_{1} \right |=k$ nên theo nguyên lí Dirichlet tồn tại ít nhất 1 phần tử $a\in A_{1}$ là phần tử chung của không ít hơn m trong số các tập $A_{1} \to A_{n}$ với $m\geq \frac{n-1}{k}> k-1$
Thật vậy giả sử ngược lại ,mọi phần tử của $A_{1}$ đều thuộc không quá m trong số các tập $A_{2}\rightarrow A_{n}$ với $m< \frac{n-1}{k}$ thì số các tập đã cho sẽ nhỏ hơn $k.\frac{n-1}{k}+1=n$ (vô lý)
*Nếu $m< n-1$ thì sẽ tồn tại 1 tập,giả sử là $A_{j}(1\leq j\leq n)$ mà $a\notin A_{j}$.
Kí hiệu b là phần tử chung của $A_{1},A_{j}$ với $A_{it}=a_{it}(1\leq t\leq m)$
Khi đó với mọi t $(1\leq m\leq t),(a_{it}\neq b)$ và với mọi t,s$(1\leq s,t\leq m),(s\neq t\Rightarrow a_{is}\neq a_{it})$
Thật vậy nếu mà tồn tại t $1\leq t\leq m$ mà $a_{it}=b$ thì $A_{1},A_{it}$ có ít nhất 2 phần tử chung(vô lý)
Nếu$\exists s,t;a_{it}=a_{is}$ thì $A_{it},A_{is}$ có ít nhất 2 phần tử chung(vô lý)
Do đó $A_{j}$ chứa ít nhất m+1 phần tử khác nhau $b,a_{i1},a_{i2},...,a_{im},\left | A_{j} \right |\geq m+1> k$ (mâu thuẫn)
Vậy $m=n-1,\bigcap_{i=1}^{n}A_{i}=\left \{ a \right \}$
Tóm lại $A_{i},A_{j}(1\leq i,j\leq n,i\neq j)$ chỉ có 1 phần tử chung duy nhất là a
$\Rightarrow \left | \bigcup_{i=1}^{n}A_{i} \right |=\bigcup_{i=1}^{n}\left | A_{i}\setminus \left \{ a \right \} \right |+\left | \left \{ a \right \} \right |=n(k-1)+1$
PS"làm xong nhớ tới bài Lương Thế Vinh-2014
Giả sử1 tháng có 30 ngày,tại 1 cái thư viện ở Biên Hòa ngày nào cũng có 5 người đến đọc sách,nhưng 2 ngày bất kìchir có 9 người đến đọc.Hỏi tháng đó có bn người đến đọc?
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh