Đến nội dung

Hình ảnh

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.

- - - - -

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

#1
dunglamtym

dunglamtym

    Trung sĩ

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

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.



#2
toannguyenebolala

toannguyenebolala

    Sĩ quan

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

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$


"Đừ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