Đến nội dung

Hình ảnh

4 bài toán liên Quan đến Tập Hợp

- - - - -

  • Please log in to reply
Chủ đề này có 3 trả lời

#1
gianglinh

gianglinh

    Sĩ quan

  • Thành viên
  • 302 Bài viết
mỉnh vốn yếu phần tập hợp rất mong các bạn giải hộ 4 bài này
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$.
2)Cho $X=\{1,2,...,2003 \}$, $n$ nguyên dương sao cho 1 tập con gồm $n$ phần tử của $X$ luôn có 1 phần tử là lũy thừa của 2 hoặc có 2 phần tử có tổng là lũy thừa của 2 . CM $n>998$.
3)Cho $X=\{1,2,...,2004 \}$, $n$ nguyên dương sao cho nếu loại bớt khỏi $X$ $n$ phần tử thì tập hợp còn lại không có phần tử nào là tích của 2 phần tử khác . CM $n>42$.
4)Cho $X=\{1,2,...,n \}$, $k$ nguyên dương sao cho trong mọi tập con chứa $k$ phần tử đều có ít nhất 2 số mà 1 trong 2 số đó là bội của số kia . CM $k> \left\lfloor \frac{n+1}{2} \right\rfloor$.

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 16-03-2013 - 14:21

n- hữu hạn số 0 < n
bạn có tin điều này không

#2
nhatquangsin

nhatquangsin

    Thượng sĩ

  • Thành viên
  • 238 Bài viết

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


#3
nhatquangsin

nhatquangsin

    Thượng sĩ

  • Thành viên
  • 238 Bài viết

4)Cho $X=\{1,2,...,n \}$, $k$ nguyên dương sao cho trong mọi tập con chứa $k$ phần tử đều có ít nhất 2 số mà 1 trong 2 số đó là bội của số kia . CM $k> \left\lfloor \frac{n+1}{2} \right\rfloor$.

Bài tương tự tại đây



#4
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

Một cách khác cho bài 1

 


Ta có các cặp số thoả mãn $ab$ chia hết $a+b$: $(3;6);(4;12);(5;20);(6;12);(6;30);(7;42);(8;2);(9;18);(10;15);(10;40);(12;24);(12;36);(14;35);(15;30);(16;48);(18;36);(20;30);(21;28);(21;42);(24;40);(24;48);(30;45);(36;45)$

Tổng hợp các số lại tập $A$, ta có:\[A = \left\{ {3;4;5;6;7;8;9;10;12;14;15;16;18;20;21;24;30;35;36;40;45;48} \right\}\]

\[ \Rightarrow k \ge \left| {X\backslash A} \right| + \left[ {\frac{{\left| A \right|}}{2}} \right] + 1 = 39\]

Vậy $min(k)=39$

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

Đây là kết quả sau 1h bấm máy tính của mình, các bạn có cách nào hay hơn thì đưa lên để mọi người cùng tham khảo

 

Giải bài 17:
Chứng minh $k \ge 39$
Các cặp số thoả mãn $ab$ chia hết $a+b$: $(3;6);(4;12);(5;20);(6;12);(6;30);(7;42);(8;2);(9;18);(10;15);(10;40);(12;24);(12;36);(14;35);(15;30);(16;48);(18;36);(20;30);(21;28);(21;42);(24;40);(24;48);(30;45);(36;45)$

Xét tập $M=(6,12,15,18,20,21,24,35,40,42,45,48)$. Vì 23 cặp trên đều có phần tử thuộc $M$ nên tập $X\M$ không thỏa mãn bài toán. Mà $|X\M|=38 \rightarrow k \ge 39$

Chứng minh mọi tập có 39 phần tử đều thỏa mãn bài toán:
Xét tập $A$ bất kì gồm 39 phần tử của $X$.
Chọn 12 cặp số trong 23 cặp trên sao cho các phần tử không trùng nhau: $(3;6);(4;12);(5;20);(7;42);(8;2);(9;18);(10;15);(14;35);(18;36);(21;28);(24;40);(30;45)$

12 cặp trên chứa 24 phần tử của $X$. Nên $X$ chỉ còn lại 26 phần tử.
Vậy ít nhất 13 phần tử của $A$ của phải thuộc 12 cặp trên.
Theo nguyên lí drichlet thì $A$ chứa ít nhất 1 trong 12 cặp trên.
Từ đó tập $A$ thỏa mãn đề bài.

 





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh