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

[manhhung2013]

Cho các số nguyên dương k, n thỏa mãn điểu kiện n>$k^{2}-k+1$. Giả sử n tập $A_{1},A_{2},...,A_{n}$ thỏa mãn đồng thời 2 điều kiện:

a)$\left | A_{i} \right |=k,\forall i(1\leqslant i\leqslant n);$

b)$\left | A_{i}\cap A_{j} \right |=2k-1;\forall i,j (i\neq j,1\leq i,j\leq n)$

Hãy xác định số phần tử của tập $\bigcup_{i=1}^{n}A_{i}$

[redfox]

Từ đề bài ta có $\left | A_i\cap A_j \right |=1$. Xét các phần tử thuộc $A_1$, theo Dirichlet tồn tại phần tử $x$ thuộc ít nhất $k+1$ tập hợp (gồm $A_1$).

Giả sử tồn tại $i$ sao cho $x\notin A_i$. Khi đó xét giao của $A_i$ với các tập hợp chứa $x$, ta được ít nhất $k+1$ phần tử khác $x$ thuộc $A_i$. Dễ thấy các phần tử đó đều phân biệt (vô lý).

Vậy $A_i\cap A_j= \left \{ x \right \},\forall 1\leq i< j\leq n$, tính được $\left | \bigcup_{i=1}^{n} A_i\right |=nk-k+1$.

(câu b) có lẽ là $\left | A_i\cup A_j \right |=2k-1$).

Bài viết đã được chỉnh sửa nội dung bởi redfox: 21-05-2017 - 19:36

[NHoang1608]

Lời giải trên có vẻ chưa chặt chẽ cho lắm    mặc dù ý tưởng đúng 

Lời giải:

Từ đề bài ta có $\left | A_{i}\cap A_{j} \right |=1$. (1)

Ta xét tập $A_{1}$ và $n-1$ tập còn lại. Ta có $\left | A_{1}\cap A_{j} \right |=1$ trong đó $2\leq j \leq n$

Vì tập $A_{1}$ có $k$ phần tử nên theo nguyên lí $Drichlet$ thì tồn tại $1$ phần tử $x$ thuộc $A_{1}$ lÀ phần tử chung của ít nhất $m=\frac{n-1}{k} > k-1 (2)$ tập hợp.

Ta sẽ chứng minh $m=n-1$

Dễ thấy $m \leq n-1$

Giả sử rằng $m< n-1$. Lúc đấy sẽ tồn tại $1$ tập hợp $A_{o}$ không chứa phần tử $x$.

Nhưng mà $\left | A_{1}\cap A_{o} \right |=1$ Gọi phần tử đó là $b$.

Gọi giao của $A_{o}$ và tập hợp $A_{l}$ là $t$ trong đó $1\leq l \leq m$ nghĩa là $A_{l}$ là 1 tập hợp bất kì trong những tập hợp chứa $x$.

Ta thấy rằng $b\neq t$ vì nếu $b=t$ thì giao của $A_{1}$ và $A_{l}$ là $x,b$ ( vô lí )

Với $l=\overline{1;m}$ thì $t_{1}\neq t_{2}....\neq t_{m}$ Vì nếu giả sử rằng $t_{p}=t_{q}$ $(1\leq p,q \leq m)$

ThÌ giao của tập hợp $A_{p}$ và $A_{q}$ sẽ là $x, t_{p}=t_{q}$ (Vô lí vì (1))

Từ đó tập $A_{o}$ sẽ chứa $b,t_{1},....t_{m}$ tức là $m+1$ phần tử khác nhau mà $\left | A_{o} \right |=k$ nên $m+1 \leq k$  vô lí với (2).

Vậy điều giả sử là sai tức là $m=n-1$ có nghĩa là $\bigcap_{i=1}^{n}A_{i}={x}$ mà $\left | A_{i}\cap A_{j} \right |=1$

Nên theo công thức bao hàm loại trừ thì ta có$\left | \bigcup_{i=1}^{n}A_{i} \right |=n(k-1)+1$

Bài viết đã được chỉnh sửa nội dung bởi NHoang1608: 19-08-2017 - 14:26

[Hkai Bao]

Từ đề bài ta có $\left | A_i\cap A_j \right |=1$. Xét các phần tử thuộc $A_1$, theo Dirichlet tồn tại phần tử $x$ thuộc ít nhất $k+1$ tập hợp (gồm $A_1$).

Giả sử tồn tại $i$ sao cho $x\notin A_i$. Khi đó xét giao của $A_i$ với các tập hợp chứa $x$, ta được ít nhất $k+1$ phần tử khác $x$ thuộc $A_i$. Dễ thấy các phần tử đó đều phân biệt (vô lý).

Vậy $A_i\cap A_j= \left \{ x \right \},\forall 1\leq i< j\leq n$, tính được $\left | \bigcup_{i=1}^{n} A_i\right |=nk-k+1$.

(câu b) có lẽ là $\left | A_i\cup A_j \right |=2k-1$).

 

Lời giải trên có vẻ chưa chặt chẽ cho lắm    mặc dù ý tưởng đúng 

Lời giải:

Từ đề bài ta có $\left | A_{i}\cap A_{j} \right |=1$. (1)

Ta xét tập $A_{1}$ và $n-1$ tập còn lại. Ta có $\left | A_{1}\cap A_{j} \right |=1$ trong đó $2\leq j \leq n$

Vì tập $A_{1}$ có $k$ phần tử nên theo nguyên lí $Drichlet$ thì tồn tại $1$ phần tử $x$ thuộc $A_{1}$ lÀ phần tử chung của ít nhất $m=\frac{n-1}{k} \geq k-1 (2)$ tập hợp.

Ta sẽ chứng minh $m=n-1$

Dễ thấy $m \leq n-1$

Giả sử rằng $m< n-1$. Lúc đấy sẽ tồn tại $1$ tập hợp $A_{o}$ không chứa phần tử $x$.

Nhưng mà $\left | A_{1}\cap A_{o} \right |=1$ Gọi phần tử đó là $b$.

Gọi giao của $A_{o}$ và tập hợp $A_{l}$ là $t$ trong đó $1\leq l \leq m$ nghĩa là $A_{l}$ là 1 tập hợp bất kì trong những tập hợp chứa $x$.

Ta thấy rằng $b\neq t$ vì nếu $b=t$ thì giao của $A_{1}$ và $A_{l}$ là $x,b$ ( vô lí )

Với $l=\overline{1;m}$ thì $t_{1}\neq t_{2}....\neq t_{m}$ Vì nếu giả sử rằng $t_{p}=t_{q}$ $(1\leq p,q \leq m)$

ThÌ giao của tập hợp $A_{p}$ và $A_{q}$ sẽ là $x, t_{p}=t_{q}$ (Vô lí vì (1))

Từ đó tập $A_{o}$ sẽ chứa $n,t_{1},....t_{m}$ tức là $m+1$ phần tử khác nhau mà $\left | A_{o} \right |=k$ nên $m+1 \leq k$  vô lí với (2).

Vậy điều giả sử là sai tức là $m=n-1$ có nghĩa là $\bigcap_{i=1}^{n}A_{i}={x}$ mà $\left | A_{i}\cap A_{j} \right |=1$

Nên theo công thức bao hàm loại trừ thì ta có$\left | \bigcup_{i=1}^{n}A_{i} \right |=n(k-1)+1$

 

 2 ý tưởng đều như nhau và lời giải vẫn như nhau chỉ là ghi rõ ra và sửa vài chỗ thôi. Với lại sai đúng 1 chỗ mặc dù đã có sửa đổi.

Lỗi sai:  Ở redfox thì chỗ suy ra k+1 là sai

Ở NHoang1608 thì sai tới 2 chỗ : 1 chỗ là như redfox còn một chỗ ở dưới. (chỗ bôi đỏ). Dễ thấy chỗ đỏ sai bởi vì trong lời giải của bạn có đề cập tới $k-1$ nhưng mình chả thấy nó ứng dụng vào chỗ nào (nên mình tự nghĩ chỗ đó là vô dụng chăng)

 

Vấn đề ở đây là $n>k^2-k+1$ suy ra $m$ lớn hơn hẳn $k-1$ hay $m \geq k$

Lập luận như NHoang1680 tới chỗ đỏ. Do có ít nhất k tập chứa $x$ nên gọi các tập đó là $A_{j_i}, \forall i=1,k$. Và $A_o$ giao $A_{j_i}$ là $t_i$Vì nếu giả sử rằng $t_p=t_q$ thì hai tập đó có giao quá 1 phần tử gồm $x, t_p$ (vô lý). Từ đó tập $A_o$ sẽ chứa $x, t_i, \forall i=1,k$ tức $k+1$ phần tử phân biệt lơn hơn $k$ (vô lý). Vậy $m=n-1$

-------------------------------------------------------------------------------------------------------

Mình nghĩ thế đúng ko nhỉ.

[NHoang1608]

đoạn $m=\frac{n}{k-1} \geq k-1$ mình viết nhầm . Là $m=\frac{n}{k-1}> k-1$. Còn đoạn bôi đỏ mình làm đúng rồi mà vì mình định nghĩa $A_{o}$ là $1$ tập không chứa $x$ và các tập $A_{j}$ là tập chứa $x$ nên sẽ có $m$ tập như vậy chứ không phải $k$. Tới chỗ này áp dụng $m> k-1$ từ $(2)$ để nhận ra sự vô lí của lực lượng tập $A_{o}$.

Bài viết đã được chỉnh sửa nội dung bởi NHoang1608: 19-08-2017 - 14:29

[redfox]

Lỗi sai:  Ở redfox thì chỗ suy ra k+1 là sai.

Áp dụng Dirichlet cho $k$ phần tử của $A_1$ và  $n-1\geq k^2-k+1$ tập hợp $A_2,..,A_n$, tồn tại phần tử $x$ thuộc ít nhất $k$ tập hợp trong $A_2,...,A_n$, tính thêm $A_1$ nữa là $k+1$ tập hợp, tồn tại phần tử $x$ thuộc ít nhất $k+1$ tập hợp, gọi là $B_1,...,B_{k+1}$

Giả sử tồn tại $x\notin A_i$, xét các phần tử $A_i\cap B_j=\left \{ y_j \right \}$, giả sử tồn tại $y_j,y_l$ trùng nhau, khi đó $B_j\cap B_l=\left \{ y_j,x \right \}$(vô lý). Vậy các phần tử $y_1,...,y_{k+1}$ phân biệt, ta có $\left \{ y_1,...,y_{k+1} \right \}\subset A_i$ mà $\left | A_i \right |=k$ (vô lý).

Vậy $x\in A_i,\forall 1\leq i\leq n$ rồi tính được $\left | \bigcup_{i=1}^{n}A_i \right |=nk-k+1$.

(ở trên mình làm hơi tắt, mong các bạn thông cảm, không biết dưới này rõ ràng hơn chưa?)