Bài 18: Cho tập A = {1,2,3...,2016}. Hỏi lấy ra nhiều nhất bao nhiêu phần tử từ tập A để trong những phần tử lấy ra không có phần tử nào bằng tích của hai phần tử còn
Không ai vào làm nhỉ
Xét bài toán với tập 1 đến n:
Xét trường hợp lấy ra tất cả các số lớn hơn hoặc bằng $\sqrt{n}$ , số 1 và số $\left \lfloor \sqrt{n} \right \rfloor$ nếu $\left \lfloor \sqrt{n} \right \rfloor.\left \lfloor \sqrt{n}+1 \right \rfloor > n$ (hiển nhiên thỏa mãn)$a=\left \lfloor \sqrt[4]{n} \right \rfloor$
Giả sử lấy số $a=\left \lfloor \sqrt[4]{n} \right \rfloor$ thì ta có a^3-a số : (a+1,a^2+a),...,(a^3,a^4) trong đó chỉ 1 trong cặp tồn tại
Ta thấy $a^{3}-a\geqslant 2a^{2}-2$ nên khi chọn a và các số nhỏ hơn ta được dãy ít số hơn dãy đã xét
Giả sử lấy k số $\sqrt[4]{n} \leq b< \sqrt{n}$ thì tích số min với các số còn lại và tích 2 số lớn nhất ta được k tích khác nhau lớn hơn $\sqrt{n}$ nên ....
Trường hợp k=2 thì tích 2 số và tích số và tích của số nhỏ hơn với số nhỏ nhất lớn hơn căn n sẽ nhỏ hơn n (dễ cm) nên ...
Trường hợp k=1 cmtt
Vậy ta có dãy đã xét là dãy có số phần tử max
Bài viết đã được chỉnh sửa nội dung bởi halloffame: 04-06-2017 - 22:43