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$.
Rumani 2013 TST
#1
Đã gửi 10-02-2016 - 18:22
#2
Đã gửi 10-02-2016 - 18:59
#4
Đã gửi 10-02-2016 - 20:30
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
- Dung Du Duong và IHateMath thích
Đừng khóc vì chuyện đã kết thúc hãy cười vì chuyện đã xảy ra
Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em
Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh
#5
Đã gửi 10-02-2016 - 21:21
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 và No Moniker thích
#6
Đã gửi 10-02-2016 - 21:34
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
- Dung Du Duong và IHateMath thích
Đừng khóc vì chuyện đã kết thúc hãy cười vì chuyện đã xảy ra
Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em
Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh