Tìm số nguyên dương $k$ nhỏ nhất sao cho mọi tập hợp $k$ phần tử của tập $\left \{ 1,2,...,50 \right \}$ đều chứa hai phần tử $a,b$ phân biệt sao cho $ab$ chia hết cho $a+b$.
Tìm $k$ nhỏ nhất
#1
Đã gửi 26-06-2015 - 19:56
#2
Đã gửi 27-06-2015 - 18:52
Nều $k\leq 38$
Ta có thể chọn tập bất kì $\subseteq T=\left \{ 1,2,3,4,5,7,8,9,10,11,13,14,16,17,19,22,23,25,26,27,28,29,30,31,32,33,34,36,37,38,39,41,43,44,46,47,49,50 \right \}$
dễ thấy $T$ không chứa 2 số $(a,b)$ thỏa mãn đề bài. Do đó $k>38$, ta chứng minh $ k=39 $ là giá trị nhỏ nhất thỏa đề.
Xét tập hợp $$X= \left \{ 3,4,5,6,7,8,9,10,12,14,15,16,20,21,24,28,30,35,36,40,42,45,48 \right \}$$
thì $|X|=24$
phân hoạch X thành 12 cặp $(a,b)$ thỏa đề bài:
$$(6,3),(4,12),(5,20),(7,42),(8,24),(9,18),(10,40),(14,35),(15,30),(16,48),(21,28),(36,45)$$
Với một tập con $S$ bất kì của $\left \{ 1,2,...,50 \right \}$ gồm $k \geq 39$ phần tử thì có ít nhất 13 phần tử thuộc $X$, nên luôn tồn tại 1 cặp $(a,b)$ thuộc $S$ (dpcm)
Bài viết đã được chỉnh sửa nội dung bởi tap lam toan: 27-06-2015 - 23:44
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh