1)Cho $X=\{1,2,...,50 \}$ , $k$ là số nguyên dương sao cho mọi tập con gồm $k$ phần tử của $X$ đều có chứa 2 phần tử khác nhau $a,b$ của $X$ sao cho $ab$ chia hết cho $a+b$ .Chứng minh $k>38$.
Xét tập con $S\subseteq X$ . Giả sử $a,b\in S$ và $ab\vdots (a+b)$. Đặt $c=\left ( a,b \right )$. Ta có $a=ca_{1},b=cb_{1},\left ( a_{1},b_{1} \right )=1$. Vì $ab\vdots (a+b)$ nên $c^{2}a_{1}b_{1}\vdots c(a_{1}+b_{1})\Rightarrow ca_{1}b_{1}\vdots(a_{1}+b_{1})$.
Do $\left ( a_{1},b_{1} \right )=1\Rightarrow \left\{\begin{matrix} \left ( a_{1},a_{1}+b_{1} \right )=1\\ \left ( b_{1},a_{1}+b_{1} \right )=1 \end{matrix}\right. \Rightarrow a_{1}b_{1}\vdots/(a_{1}+b_{1})$
$\Rightarrow c\vdots (a_{1}+b_{1})$
Có $a+b\leq 99\Leftrightarrow c(a_{1}+b_{1})\leq 99\Rightarrow (a_{1}+b_{1})^{2}\leq 99\Rightarrow a_{1}+b_{1}\leq 9$$a+b\leq 99\Leftrightarrow c(a_{1}+b_{1})\leq 99\Rightarrow (a_{1}+b_{1})^{2}\leq 99\Rightarrow a_{1}+b_{1}\leq 9$
Xét tất cả các khả năng, ta có $23$ cặp số $(a,b)$ thỏa mãn $(6,3);(12,6);(18,9);(24,12);(30,15);(36,18);(42,21);(48,24);(12,4);(24,8);(36,12);(48,16);(20,5);(40,10);(15,10);(30,20);(45,30);(30,6);(42,7);(35,14);(28,21);(40,24);(45,36)$.
Xét tập $M=\left \{ 6,12,15,18,20,21,24,35,40,42,45,48 \right \}$. $T=X\setminus M$
Chọn $12$ cặp $(6,3);(12,6);(18,9);(24,12);(30,15);(36,18);(42,21);(48,24);(12,4);(24,8);(36,12);(48,16)$. Vì một tập hợp bất kì gồm $39$ phần tử luôn tồn tại ít nhất $13$ phần tử thuộc các cặp trên nên theo nguyên tắc Dirichlet thì luôn tồn tại ít nhất một cặp.
Như vậy trường hợp $k=39$ thỏa mãn.
Nếu $k<39$ thì do $\left | T \right |=50-12=38$ nên luôn tồn tại một tập có $k$ phần tử không thỏa yêu cầu bài toán(mà cụ thể là một tập con của $T$)
Vậy $k>38$
Bài viết đã được chỉnh sửa nội dung bởi nhatquangsin: 20-08-2013 - 00:38