Chủ đề này có 2 trả lời

[LNH]

Cho $2$ số nguyên dương $m,n$. Chứng minh rằng số các số tự nhiên $x$ thoả mãn: $\sum_{i=1}^{n}\left \lfloor \frac{x}{2^i} \right \rfloor=x-m$ không quá $2^n$

[bangbang1412]

Cho $2$ số nguyên dương $m,n$. Chứng minh rằng số các số tự nhiên $x$ thoả mãn: $\sum_{i=1}^{n}\left \lfloor \frac{x}{2^i} \right \rfloor=x-m$ không quá $2^n$

em sẽ chỉ xét cho $m>3$ thôi nhé

Giả sử có nhiều hơn $2^{n}$ nghiệm

Gọi $2^{n}+1$ nghiệm đầu là $1\leq a_{1}<a_{2}<.........<a_{2^{n}}<a_{2^{n}+1}$ 

Khi đó rõ ràng ta có $x=a_{2^{n}+1}>2^{n}$

Vì vậy ta có $x-m=\sum_{i=1}^{n}\left \lfloor \frac{x}{2^{i}} \right \rfloor> \sum_{i=1}^{n}2^{n-i}=\sum_{k=0}^{n-1}2^{k}=2^{k}=2^{n}-1=>x >2^{n}+m-1=>x\geq 2^{n}+m$

Nhưng với lần này ta có

$\sum_{i=2}^{n}\left \lfloor \frac{x}{2^{i}} \right \rfloor+\left \lfloor \frac{x}{2} \right \rfloor>\sum_{i=2}^{n}2^{n-i}+2^{n-1}+1=2^{n}-1+1=2^{n}=>x>2^{n}+m=>x>2^{n}+4=>x-m= \sum_{i=3}^{n}\left \lfloor \frac{x}{2^{i}} \right \rfloor+\left \lfloor \frac{x}{2} \right \rfloor+\left \lfloor \frac{x}{4} \right \rfloor>2^{n}-1+3=2^{n}+1=>x>2^{n}+2+m=>x\geq 2^{n}+3+m$

Làm như vậy lần nữa ta cm đc $x$ là một vô hạn nên ta có đpcm 

Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 14-12-2013 - 21:46

[LNH]

 

Bài này có một cách rất đơn giản như sau:

Xét hàm số: $f\left ( x \right )=x-\sum_{i=1}^{n}\left \lfloor \frac{x}{2^i} \right \rfloor$

Đặt $x=2^na+b$ với $a,b$ là 2 số nguyên không âm, $b<2^n$

Dễ dàng chứng minh được $f\left ( x \right )=a+f\left ( b \right )$

Bây giờ ta cố định số $m$

Với mỗi $b$ ta chỉ tồn tại một số $a$ để $f\left ( x \right )=a+f\left ( b \right )=m$

Mà số các số $b$ không quá $2^n$ nên số các số $x$ thoả mãn ycđb không vượt quá $2^n$