Đến nội dung

Hình ảnh

có bao nhiêu phần tử trong tất cả 1985 tập hợp


  • Please log in to reply
Chủ đề này có 1 trả lời

#1
I Am Gifted So Are You

I Am Gifted So Are You

    Binh nhất

  • Thành viên
  • 42 Bài viết

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.



#2
luuvanthai

luuvanthai

    Sĩ quan

  • Thành viên
  • 373 Bài viết

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