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

[IHateMath]

Cho tập $X=\{1,2,3,...1000\}$. Tìm số tự nhiên $n$ lớn nhất sao cho với 5 tập con bất kì chứa 500 phần tử $A_1, A_2, A_3, A_4, A_5$ của $X$, luôn tồn tại $1\le i,j \le 5$ mà $|A_i \cap A_j|\ge n$.

[I Love MC]

Đây

[IHateMath]

Đây

Cảm ơn bạn nhiều, lời giải này mình đọc rồi . Có ai có lời giải nào khác dùng cách lập bảng và đếm bằng hai cách không?

[nhungvienkimcuong]

Cho tập $X=\{1,2,3,...1000\}$. Tìm số tự nhiên $n$ lớn nhất sao cho với 5 tập con bất kì chứa 500 phần tử $A_1, A_2, A_3, A_4, A_5$ của $X$, luôn tồn tại $1\le i,j \le 5$ mà $|A_i \cap A_j|\ge n$.

ta có thể xem bảng như hình vẽ trên với $1$ ở ô $(i,j)$(hàng $i$ cột $j$) nghĩa là $i\in A_j$

$d(x)$ là số tập hợp mà phần tử $x$ có mặt

ta dễ thấy vài nhận xét sau(dễ chứng minh)

$\bullet \sum_{i=1}^{1000}d(i)=\sum_{j=1}^{5}\left | A_j \right |=2500$

$\bullet \sum_{i=1}^{1000}d^2(i)=\sum_{j\neq k}\left | A_j\cap A_k \right |=\sum \left | A_j \right |+2\sum_{j<k}\left | A_j\cap A_k \right |$

$\bullet \sum_{i=1}^{1000}d^2(i)\geq 2^2.500+3^2.500=6500$

$\Rightarrow \sum_{j<k}\left | A_j\cap A_k \right |=\frac{\sum_{i=1}^{1000}d(i)^2-\sum \left | A_j \right |}{2}\geq \frac{6500-2500}{2}=2000$

ở đây ta có $n=\max\left \{ i,j\in \left \{ 1,..,5 \right \}|min\left | A_i\cap A_j \right | \right \}$ do đó ta có điều sau

$C_5^2.n\geq 2000\Rightarrow n\ge 200$

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 10-02-2016 - 21:01

[IHateMath]

 

Capture.PNG

ta có thể xem bảng như hình vẽ trên với $1$ ở ô $(i,j)$(hàng $i$ cột $j$) nghĩa là $i\in A_j$

$d(x)$ là số tập hợp mà phần tử $x$ có mặt

ta dễ thấy vài nhận xét sau(dễ chứng minh)

$\bullet \sum_{i=1}^{1000}d(i)=\sum_{j=1}^{5}\left | A_j \right |=2500$

$\bullet \sum_{i=1}^{1000}d^2(i)=\sum_{j\neq k}\left | A_j\cap A_k \right |=\sum \left | A_j \right |+2\sum_{j<k}\left | A_j\cap A_k \right |$

$\bullet \sum_{i=1}^{1000}d^2(i)\geq 2^2.500+3^2.500=6500$

$\Rightarrow \sum_{j<k}\left | A_j\cap A_k \right |=\frac{\sum_{i=1}^{1000}d(i)^2-\sum \left | A_j \right |}{2}\geq \frac{6500-2500}{2}=2000$

ở đây ta có $n=\max\left \{ i,j\in \left \{ 1,..,5 \right \}|min\left | A_i\cap A_j \right | \right \}$ do đó ta có điều sau

$C_5^2.n\geq 2000\Rightarrow n\ge 200$

 

Hình như cm này còn thiếu phần cm n=200 thỏa mãn thì phải. bạn có thể chỉ ra một cách lập bảng thỏa mãn ycbt cho n=200 ko?

Bài viết đã được chỉnh sửa nội dung bởi IHateMath: 10-02-2016 - 21:21

[nhungvienkimcuong]

Hình như cm này còn thiếu phần cm n=200 thỏa mãn thì phải. bạn có thể chỉ ra một cách lập bảng thỏa mãn ycbt cho n=200 ko?

phép chứng minh khá đơn giản là ta có $\sum_{j<k}\left | A_j\cap A_k \right |=2000$ mà có $C_5^2$ tập $ A_j\cap A_k $

$\Rightarrow \exists j,k:\left | A_j\cap A_k \right |\geq \frac{2000}{C_5^2}=200$

việc chỉ ra cách lập bảng thì theo mình bỏ số $1$ ở đâu thì theo phép chứng minh trên ta đều có được đpcm nên nếu phải chỉ ra thì ghi số $1$ ở $500\text{x}5$ bảng đầu tiên là được :v

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 10-02-2016 - 21:35