Cho X ={1;2;...;2001}. Tìm $m\in N^{*}$ nhỏ nhất để với mọi cách chọn ra m số của X là $x_1;x_2;...;x_m$ thì luôn có i và j để $x_i+x_j$ là lũy thừa của 2.
Tìm $m\in N^{*}$ nhỏ nhất để với mọi cách chọn ra m số của X là $x_1;x_2;...;x_m$ thì luôn có i và j để $x_i+x_j$ là lũy thừa của 2.
#1
Đã gửi 25-10-2017 - 21:33
#2
Đã gửi 25-10-2017 - 21:59
Cho X ={1;2;...;2001}. Tìm $m\in N^{*}$ nhỏ nhất để với mọi cách chọn ra m số của X là $x_1;x_2;...;x_m$ thì luôn có i và j để $x_i+x_j$ là lũy thừa của 2.
Lũy thừa của 2 có dạng $2^n(n>0)$. Nhận thấy $n$ càng lớn hay $2^n$ càng lớn thì càng có nhiều cặp số $(x_i,x_j)$ thỏa mãn $x_i+x_j=2^{n}$.
Vậy để $m$ đạt Min thì $n$ phải đạt Max và $2^{n}\leq 2000+2001$. Suy ra $n=11$
Vậy giờ ta sẽ tìm số $m$ nhỏ nhất để từ tập $X$ thì với mọi cách chọn ra m số thì luôn có cặp số $(x_i,x_j)$ thỏa mãn $x_i+x_j=2048$.
Số cặp số $(x_i,x_j)$ thỏa mãn $x_i+x_j=2048$ là $2001-1025+1=977$ cặp.
Vậy số $m$ nhỏ nhất thỏa mãn yêu cầu bài toán là $m=2001-977+1=1025$
- dunglamtym yêu thích
"Đừng khóc, Alfred! Anh cần có đủ nghị lực để chết ở tuổi hai mươi"
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh