Cho số nguyên dương $n$. Xét tập $A$ có $n$ phần tử. Tìm số nguyên dương $k$ nhỏ nhất sao cho mọi cách chọn $k$ tập hợp con của $A$ thì đều tìm được hai tập $X,Y$ khác nhau thỏa mãn $XY$

Đáp án:

`k=C_n^{[n/2]}+1`

Giải thích các bước giải:

Ta có: số tập con có `2` phần tử của tập `A` là: `C_n^2`

Giả sử `k=C_n^2`, như vậy ta sẽ có đúng `k` cách chọn tập con có `2` phần tử mà không thể tìm được hai tập `X,Y` khác nhau thỏa mãn `XsubsetY`(Do mỗi tập con có `2` phần tử là khác nhau), Như vậy `k=C_n^2` sẽ không thỏa mãn.

Nếu ta cho `k=C_n^2+1`, vậy thì ta sẽ có `C_n^2` cách chọn tập con có `2` phần tử, cách còn lại ta sẽ chọn tập con bất kì thì sẽ đều tìm được hai tập `X,Y` khác nhau thỏa mãn `XsubsetY` (Do đã lấp đầy tập con `2` phần tử, tập còn lại mình chọn dù là tập con nào thì cũng tìm được 2 tập số thỏa mãn yêu cầu bài toán)

Nhưng liệu `k=C_n^2+1` có nhỏ nhất? Tất nhiên là không phải như vậy, điều này sẽ sai hoàn toàn khi ta không dùng `C_n^2` cách đầu để chọn toàn bộ tập con có `2` phần tử nữa, mà ta sẽ chọn toàn bộ tập con có `3` phần tử thì sao? Khi đó, `C_n^2` là không đủ, và `k=C_n^3` thì mới đủ lấp đầy tập con có `3` phần tử, nhưng khi ấy, ta lại không dùng `C_n^3` cách ấy để chọn toàn bộ tập con có `3` phần tử nữa, ta lại chọn toàn bộ số tập con có `4` phần tử cơ, câu hỏi đặt ra là liệu nó có không đủ mãi như vậy không?

Tất nhiên là không, giải pháp ở đây là ta sẽ chọn số nguyên dương `m` đủ lớn sao cho `C_n^m` là lớn nhất, qua tính chất `C_n^m=C_n^{n-m}` thì ta sẽ có được là `C_n^m` lớn nhất khi `m=n-m` hay `2n=m`, do chưa biết `n` chẵn hay `n` lẻ nên ta sẽ để `m=[n/2]` và khi đó `C_n^m` là lớn nhất. Như vậy, ta sẽ tìm được ra `k=C_n^m+1` là số nguyên dương nhỏ nhất với `m=[n/2]` thì sẽ luôn tìm được hai tập `X,Y` khác nhau thỏa mãn `XsubsetY`

Vậy `k=C_n^{[n/2]}+1`

`text{Chúc em học tốt<3}`

`text{#Honekawa Hirusamasensei}`