Question

[Vũ Tường Vinh]

Cho tập A ={1, 2,3,... ,20} . Hỏi phải lấy ra it nhất bao nhiêu phần tử từ A , để trong đó chắc chắn có 2 phần tử a b , mà ab chia hết cho a+b .

Answer 1

[Trương Nhật Minh]

Để tìm số phần tử ít nhất cần lấy từ tập \(A=\left\lbrace1,2,3,\ldots,20\right\rbrace\) sao cho chắc chắn có hai số \(a\) và \(b\) thỏa mãn \(a b \div \left(\right. a + b \left.\right)\) là số nguyên, chúng ta bắt đầu bằng việc xác định các cặp số thỏa điều kiện.

Ta thấy các cặp như \(\left(\right. 3 , 6 \left.\right)\), \(\left(\right. 4 , 12 \left.\right)\), \(\left(\right. 5 , 20 \left.\right)\), \(\left(\right. 6 , 12 \left.\right)\), \(\left(\right. 9 , 18 \left.\right)\), và \(\left(\right. 10 , 15 \left.\right)\) đều thỏa mãn vì phép chia \(a b \div \left(\right. a + b \left.\right)\) cho kết quả nguyên.

Tiếp theo, ta xây dựng tập hợp lớn nhất không chứa bất kỳ cặp nào trong số này. Đầu tiên, chọn các số không thuộc bất kỳ cặp nào: \(1 , 2 , 7 , 8 , 11 , 13 , 14 , 16 , 17 , 19\) (10 số). Sau đó, từ mỗi cặp đã xác định, chọn thêm một số sao không lấy cả hai. Chẳng hạn, từ cặp \(\left(\right. 3 , 6 , 12 \left.\right)\), chọn \(3\) và \(12\) (bỏ \(6\)); từ cặp \(\left(\right. 5 , 20 \left.\right)\), chọn \(5\); từ cặp \(\left(\right. 9 , 18 \left.\right)\), chọn \(9\); và từ cặp \(\left(\right. 10 , 15 \left.\right)\), chọn \(10\). Như vậy, thêm được 5 số: \(3 , 12 , 5 , 9 , 10\).

Tập hợp "an toàn" này có tổng \(10 + 5 = 15\) phần tử. Nếu lấy 15 số này, ta vẫn tránh được tất cả cặp thỏa điều kiện. Tuy nhiên, theo nguyên lý Dirichlet, để chắc chắn có ít nhất một cặp thỏa mãn, ta cần lấy thêm 1 số nữa.

Vậy, số phần tử ít nhất cần lấy là \(15 + 1 = 16\).
\(\)