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

[LotusSven]

Cho các số nguyên dương $n,k$ thoả mãn $n> k^{2}-k+1$ và $A_{1},A_{2},...,A_{n}$ là $n$ tập hợp khác rỗng, đôi một khác nhau, thoả mãn đồng thời hai điều kiên:
(i) $\left |A_{i} \right |=k \forall i\in \left \{ 1,2,...,n \right \}$;
(ii) $\left | A_{i}\cap A_{j} \right |=2k-1,\forall i,j\in \left \{ 1,2,...,n \right \}:i\neq j$.
Chứng minh rằng $A_{1},A_{2},...,A_{n}$ có đúng 1 phần tử chung và tính số phần tử của $A_{1}\bigcup A_{2}\bigcup ...\bigcup A_{n}$.

Bài viết đã được chỉnh sửa nội dung bởi LotusSven: 13-02-2013 - 22:50

[perfectstrong]

Bạn nhầm giả thiết rồi. Giả thiết (ii) phải là $\left| {A_i \cup A_j } \right| = 2k - 1$.
Lời giải:
\[
\left| {A_i \cap A_j } \right| = -\left| {A_i \cup A_j } \right| + \left| {A_i } \right| + \left| {A_j } \right| = 1,\forall i \ne j\quad (1)
\]
Xét $A_1$. Do $(1) \Rightarrow |A_1 \cap A_j|=1\,\forall j=\overline{2,n}$.
Vì $|A_1|=k$ nên theo nguyên lý Dirichlet, tồn tại 1 phần tử $a \in A_1$ là phần tử chung của $A_1$ và ít nhất $m$ tập $A_{i_1};A_{i_2}:...;A_{i_m}$ với $m$ thỏa:
$$m \ge \dfrac{n-1}{k}>k-1 \,\text{(do giả thiết)} \quad (*)$$

Ta chứng minh rằng $m=n-1$. Thật vậy, giả sử $m<n-1$, suy ra tồn tại tập $A_j$ sao cho $a \not \in A_j$ (2)
Do (1) nên $A_1 \cap A_j=\{ b \}$ và do (2) nên $b \ne a$.
Đặt $A_j \cap A_{i_t}=\{ a_{i_t} \}$ với $t=\overline{1,m}$.

Nếu $\exists t: a_{i_t}=b \ne a \Rightarrow \{a;b \} \subset (A_{j} \cap A_{i_t}) \Rightarrow |A_j \cap A_{i_t}| \ge 2:\text{ trái } (1)$.
Cho nên $b \ne a_{i_t}\,\forall t=\overline{1,m}$. (3)

Nếu có phần tử $a_{i_s} \equiv a_{i_t}$. Vì $a_{i_s};a_{i_t} \in A_j$ mà $a \not \in A_j$ nên $a_{i_s};a_{i_t} \ne a$.
$\Rightarrow \{ a;a_{i_s} \} \subset (A_{i_s};A_{i_t}) \Rightarrow |A_{i_s} \cap A_{i_t}| \ge 2: \text{ trái } (1)$
Suy ra $a_{i_s} \ne a_{i_t}\,\forall s \ne t$ (4).

Từ (3),(4) suy ra $A_j$ chứa ít nhất $m+1$ phần tử $b;a_{i_1};..;a_{i_m}$.
$$(*) \Rightarrow |A_j| \ge m+1 >k:\text{ trái } (i)$$

Vì vậy điều giả sử ban đầu là sai, tức $m=n-1$ (vì $m \le n-1$).
Suy ra \[
\left\{ \begin{array}{l}
\bigcap\limits_{i = 1}^n {A_i } = \left\{ a \right\} \\
A_i \cap A_j = \left\{ a \right\},\forall i \ne j \\
\end{array} \right.
\]
Cho nên \[
\bigcup\limits_{i = 1}^n {A_i } = \left\{ a \right\} \cup \bigcup\limits_{i = 1}^n {\left( {A_i \backslash \left\{ a \right\}} \right)}
\]
Và $A_i \backslash \{ a \}$ là các tập đôi một rời nhau không chứa $a$ (do (1)). Vì vậy:
\[
\left| {\bigcup\limits_{i = 1}^n {A_i } } \right| = 1 + \sum\limits_{i = 1}^n {\left| {A_i \backslash \left\{ a \right\}} \right|} = 1 + n\left( {k - 1} \right)
\]

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 14-02-2013 - 21:58

[cool hunter]

Bạn nhầm giả thiết rồi. Giả thiết (ii) phải là $\left| {A_i \cup A_j } \right| = 2k - 1$.
Lời giải:
\[
\left| {A_i \cap A_j } \right| = \left| {A_i \cup A_j } \right| - \left| {A_i } \right| - \left| {A_j } \right| = 1,\forall i \ne j\quad (1)
\]
Xét $A_1$. Do $(1) \Rightarrow |A_1 \cap A_j|=1\,\forall j=\overline{2,n}$.
Vì $|A_1|=k$ nên theo nguyên lý Dirichlet, tồn tại 1 phần tử $a \in A_1$ là phần tử chung của $A_1$ và ít nhất $m$ tập $A_{i_1};A_{i_2}:...;A_{i_m}$ với $m$ thỏa:
$$m \ge \dfrac{n-1}{k}>k-1 \,\text{(do giả thiết)} \quad (*)$$

hình như chỗ màu đỏ là: $\left | A_{i}\cap A_{j} \right |=\left | A_{i} \right |+\left | A_{j} \right |-\left | A_{i} \cup A_{j} \right |$ chứ anh