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

[PTKBLYT9C1213]

Cho m, n nguyên dương và m, n > 1. Xét tập hợp X gồm n phần tử và A₁, A₂,..., A_m là m tập con của X thõa mãn điều kiện:

 Với $\forall x, y \in X, x\neq y$ thì tồn tại tập A_k với $1\leq k\leq m$ sao cho $x\in A_{k}, y\notin A_{k}$ hoặc $x\notin A_{k}, y\in A_{k}$

Chứng minh rằng : $n\leq 2^{m}$

[nguyenthehoan]

Cho m, n nguyên dương và m, n > 1. Xét tập hợp X gồm n phần tử và A₁, A₂,..., A_m là m tập con của X thõa mãn điều kiện:

 Với $\forall x, y \in X, x\neq y$ thì tồn tại tập A_k với $1\leq k\leq m$ sao cho $x\in A_{k}, y\notin A_{k}$ hoặc $x\notin A_{k}, y\in A_{k}$

Chứng minh rằng : $n\leq 2^{m}$

Giả sử $x_1,x_2,...,x_n$ là các phần tử của tập $X$. Kí hiệu $S_i$ là tập các tập $A_j$ mà chứa phần tử $x_i$.

Giả sử $n\geq 2^{m}$.

Ta có tất cả $n$ tập $S_i$, mỗi tập $S_i$ là một cách chọn ra một bộ $A_j_1,A_j_2,...A_j_k$ nên tối đa ta có $2^{m}-1$ cách chọn tập $S_i$   (là số các tập con của tập có $m$ phần tử)

Mà ta có $n\geq 2^{m}$ tập $S_i$, nên theo nguyên tắc Dirichle tồn tại hai tập $S_i$ và $S_t$ trùng nhau, hay khi đó các phần tử $x_i$ và $x_t$ là các phần tử chung của cùng một số tập trong các tập $A_i$.

Khi đó $2$ phần tử này không thỏa mãn điều kiện của bài toán nên ta có mâu thuẫn.

Vậy $n<2^{m}$.

[quocbaolqd11]

Giả sử $x_1,x_2,...,x_n$ là các phần tử của tập $X$. Kí hiệu $S_i$ là tập các tập $A_j$ mà chứa phần tử $x_i$.

Giả sử $n\geq 2^{m}$.

Ta có tất cả $n$ tập $S_i$, mỗi tập $S_i$ là một cách chọn ra một bộ $A_j_1,A_j_2,...A_j_k$ nên tối đa ta có $2^{m}-1$ cách chọn tập $S_i$   (là số các tập con của tập có $m$ phần tử)

Mà ta có $n\geq 2^{m}$ tập $S_i$, nên theo nguyên tắc Dirichle tồn tại hai tập $S_i$ và $S_t$ trùng nhau, hay khi đó các phần tử $x_i$ và $x_t$ là các phần tử chung của cùng một số tập trong các tập $A_i$.

Khi đó $2$ phần tử này không thỏa mãn điều kiện của bài toán nên ta có mâu thuẫn.

Vậy $n<2^{m}$.

mình nghĩ $S_i$ có thể rỗng vì điều kiện của bài toán là với $x,y \in X$ thì luôn tồn tồn tại $A_k$ thỏa $x \notin A_k$ và $y \in A_k$ nên mình sẽ cho $x_i$ không thuộc bất kì tập nào trong m tập con dạng $A_k$ và tất cả $n-1$ phần tử còn lại đều thuộc các tập trên.

[chanhquocnghiem]

Giả sử $x_1,x_2,...,x_n$ là các phần tử của tập $X$. Kí hiệu $S_i$ là tập các tập $A_j$ mà chứa phần tử $x_i$.

Giả sử $n\geq 2^{m}$.

Ta có tất cả $n$ tập $S_i$, mỗi tập $S_i$ là một cách chọn ra một bộ $A_j_1,A_j_2,...A_j_k$ nên tối đa ta có $2^{m}-1$ cách chọn tập $S_i$   (là số các tập con của tập có $m$ phần tử)

Mà ta có $n\geq 2^{m}$ tập $S_i$, nên theo nguyên tắc Dirichle tồn tại hai tập $S_i$ và $S_t$ trùng nhau, hay khi đó các phần tử $x_i$ và $x_t$ là các phần tử chung của cùng một số tập trong các tập $A_i$.

Khi đó $2$ phần tử này không thỏa mãn điều kiện của bài toán nên ta có mâu thuẫn.

Vậy $n<2^{m}$.

$n$ có thể bằng $2^m$.

Chẳng hạn tập $X$ có $4$ phần tử $X=\left \{ 2;3;6;7 \right \}$ ($n=4$)

$A_{1}=\left \{ 2;6 \right \};A_{2}=\left \{ 3;6 \right \}$ là 2 tập thỏa mãn ĐK đề bài ($m=2$)

Khi đó $n=2^m$

Vậy xin sửa lại lời giải như sau :

Giả sử $X=\left \{ x_{1};x_{2};...;x_{n} \right \}$, $Y=\left \{ A_{1};A_{2};...;A_{m} \right \}$

Gọi $Y_{i}$ là tập các tập hợp thuộc $Y$ có chứa phần tử $x_{i}$

Giả sử $n> 2^m$

Mỗi tập $Y_{i}$ là một tập con của $Y$ (lưu ý rằng $Y_{i}$ có thể là tập rỗng) và tập $Y$ có $m$ phần tử ---> có tối đa $2^m$ tập $Y_{i}$ khác nhau từng đôi một.

Vì có tất cả $n$ tập $Y_{i}$ (ứng với $n$ phần tử thuộc $X$) và $n> 2^m$ nên có ít nhất $2$ tập $Y_{j}$ (ứng với $x_{j}$) và $Y_{k}$ (ứng với $x_{k}$) trùng nhau ---> Không tồn tại tập nào thuộc $Y$ có chứa $x_{j}$ mà không chứa $x_{k}$ hoặc có chứa $x_{k}$ mà không chứa $x_{j}$.Điều này mâu thuẫn với giả thiết.

Vậy $n\leqslant 2^m$.