quocbaolqd11

Bạn giải sai rồi nhé

Đáp số đúng là : $2n!\left [ n!+\sum_{i=1}^{2n}\left ( -1 \right )^i\frac{2n}{2n-i}C_{2n-i}^{i}\left ( n-i \right )! \right ]$

anh góp ý là cách viết công thức có vấn đề. Nếu $i$ chạy tới $2n$ thì ta sẽ có $\frac{2n}{0}.\binom{0}{2n}.(n-2n)!$. Và chắc chắn công thức này sai.

----------------------------------------------------------------------

Đã sửa

Gọi $T'$ là tập không chứa $A_i$ sao cho $|T'|$ đạt max. Như vậy, với bất kì tập $T''=T \cup \{x\}$ thì $T''$ chứa $A_i$. 
Giờ ta sẽ đếm số bộ $(A_i,m,n)=k$ với $m \neq n \in T'$ và $m,n \in A_i$. Vì  $|A_i \cap A_j| \le 1$ nên:
                                                                $k \le C_{|T'|}^{2}$  
Mà với mỗi $p \in A\setminus T'$, ta xác định được duy nhất một phần tử thuộc bộ $(A_i,m,n)$. Vậy nên:
                                                                $k \ge n-|T'|$ 
Từ đó, ta có: $C_{|T'|}^{2} \ge n-|T'|$. Giải bpt, ta được đpcm.

à, mình hiểu là nếu như với một số $m$ mà $|A|=m$ và ta luôn xây dựng được 1 tập có $m$ phần tử và không có phần tử nào chia hết cho nhau thì số $m$ không thỏa đề và nếu ta tìm được $m$ lớn nhất không thỏa đề thì $m+1$ là số nhỏ nhất thỏa đề. Cơ mà, cái lúc nãy mình nói ở post trên có vẻ sai rồi. Theo mình nghĩ thì ta vẫn có thể xây dựng được tập hợp có $[\frac{n}{2}]$ phần tử và không phần tử nào chia hết cho nhau. Mình nêu cách xác định với $n=2k$ (lấy ý tưởng hầu hết từ bài TST 2007 p.5).
xét tập $A=\{a_i=2^{f(i)}(2i-1)| [\frac{n}{3}]+1 \le 3^{f(i)}(2i-1) \le n \}$ (nếu $n$ không chiâ hét cho 3 hoặc  $A=\{a_i=2^{f(i)}(2i-1)| \frac{n}{3} \le 3^{f(i)}(2i-1) \le n \}$ nếu $n$ chia hết cho 3.
Dễ thấy tập này có $k$ phần tử thuộc $\{1,2,3,...2k \}$.
giả sử có $a_{j} \vdots a_i$ thì khi dó $2^{f(i)}(2i-1) \le 2^{f(j)}(2j-1)$, tức là $f(j) \ge f(i)$ và $2j-1 \vdots 2i-1$.
vì $2i-1; 2j-1$ lẻ nên $2j-1 \ge 3(2i-1)$.
Từ đó, có: $3^{f(i)+1}.(2i-1) \ge n >3^{f(j)}(2j-1) \ge 3^{f(i)+1}.(2i-1)$ hay $f(i) > f(j)$ (vô lí).
vậy với $m=k$ thì luôn xây dựng được tập thỏa ycđ. dễ chứng minh được rằng trong $k+1$ số trong $[1;2k]$ thì luôn tồn tại 2

số chia hết cho nhau nên $m_{min}=k+1$. TH $n$ lẻ thì để từ từ nghiên cứu vì cuối năm rồi .

Đề bài này có vấn đề.Có lẽ nên sửa lại như thế này :

Cho tập hợp $X=\left \{ 1,2,3,...,n \right \}\subset \mathbb{N}$.Gọi $A$ là tập con của $X$ thỏa mãn điều kiện $\forall a,b\in A$ ($a> b$) ta đều có $a\vdots b$

Tìm số nguyên dương $m$ NHỎ nhất (hay LỚN nhất) sao cho $\left | A \right |=m$.

 

Giải :

+ Nếu là tìm số nguyên dương $m$ NHỎ nhất sao cho $\left | A \right |=m$ thì dễ thấy $m=2$ (khi đó $A=\left \{ 1,k \right \}$ trong đó $k\in X$ và $k\neq 1$)

 

+ Nếu là tìm số nguyên dương $m$ LỚN nhất sao cho $\left | A \right |=m$ :

Khi đó các phần tử của $A$ sẽ là $2^0;2^1;2^2;2^3;...;2^{m-1}$

Trong đó $2^{m-1}\leqslant n< 2^m\Leftrightarrow m-1\leqslant log_{2}n< m$

Hay $m=p+1$ với $p$ là phần nguyên của $log_{2}n$

Bạn hiểu sai ý đề rồi. $m$ nhỏ nhất để luôn có hai phần tử $a,b$ và $a \vdots b$ chứ không phải là $m$ nhỏ nhất để có thể có 2 phần tử $a,b$ mà $a \vdots b$. Mình nghĩ đáp án là $m=t+1$ với t là số các số nguyên tố trong $[1;n]$. Mà việc tìm $t$ thì minh chưa nghĩ ra. Nếu cho $n$ cụ thể thì sẽ dễ hơn nhiều.

 Mình nghĩ là $k=3$ là đáp án, với $k=3$ thì có thể chia được thành các tập:
$A_1 =\{7,8,9,11,14,17,...\} \\
  A_2 =\{4,5,6,10,12,15,18,...\} \\
  A_3 =\{1,2,3,13,16,19,22,...\}  \\$

dễ thấy $A_1 \cup A_2 \cup A_3=N$ nên $k=3$ đúng.
Chứng minh $k \ge 4$ không chia được.
gọi $a_k^{(i)}$ là phần tử thứ $k \in A_i$.
giả sử tồn tại $k \ge 8$ chia được.
ta có 15 có 7 cách chia thành $a+b$ với $a \neq b$, mà có 8 tập nên phải có 2 tập có giao khác rỗng, vô lí.
vậy $k \le 7$.
dễ thấy $k=7$ cũng không đúng vì 15 có 7 cách chia thành dạng $a+b$ nên cả cách chia phải nằm vào 7 tập khác nhau.
Xét số 16, khi đó $a_k^{(i)}+a_{k'}^{(i)}=16$ với mọi $i \le 7; k \neq k'$
mà 16 cũng chỉ có 7 cách chia thành dạng $a+b$ nên sẽ tồn tại tập con có chung 2 phần tử (vô lí).
$k=6$, $k=5$, $k=4$ chứng minh tương tự (thực ra bạn chỉ cần chứng minh với TH $k=4$ là đủ rồi, chứng min hTH $k=4$ thì phải dùng đến phân tích của 17 thành $a+b$).
bài này là bài C4 IMO SL 2011, bạn có thể tham khảo thêm lời giải khác .