Đến nội dung

Hình ảnh

Tìm $k$ nhỏ nhất

- - - - -

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

#1
Huy Thong

Huy Thong

    Binh nhì

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

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$.



#2
tap lam toan

tap lam toan

    Trung sĩ

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

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