For any positive integer $ k$, let $ f(k)$ be the number of elements in the set $ \{ k+1, k+2, \ldots, 2k\}$ whose base $2$ representation contains exactly three 1s.
(a) Prove that for any positive integer $ m$, there exists at least one positive integer $ k$ such that $ f(k)=m$.
(b) Determine all positive integers $ m$ for which there exists exactly one $ k$ with $ f(k) =m$.
============================
Call the numbers whose base $2$ representations have exactly three ones the good numbers. Let $$A_k:=\{k+1,\dots,2k\}.$$
(a) Since $f(1)=0$, it suffices to show that $$f(k-1)\le f(k)\le1+f(k-1).$$ Each time we remove $k$ and add $2k-1$ and $2k$ to obtain $A_k$ from $A_{k-1}$. If $k$ is good and so is $2k$, hence $f(k)\ge f(k-1)$. If $2k$ is good then so is $k$, hence $f(k)\le1+f(k-1)$.
(b) Equivalently, we seek $k$ such that both $2k-1$ and $2k+1$ are good, since $k$ is good if and only if $2k$ is good. In that case $m=f(k)$ is what we need.
Denote by $B\ge2C\ge4D$ the three powers of two in a good number $B+C+D$. Each time we jump from a good number to the next there are three types:
(i) $(B,C,D)\rightarrow(2B,2,1)$ when $B=2C=4D$. The good number increases by $D+3\ge4$.
(ii) $(B,C,D)\rightarrow(B,2C,1)$ when $B>2C=4D$. The good number increases by $D+1\ge2$.
(iii) $(B,C,D)\rightarrow(B,C,2D)$ when $C>2D$. The good number increases by $D\ge1$.
If $2k-1$ and $2k+1$ are consecutive good numbers, then the jump from $2k-1$ to $2k+1$ must be of type (ii) and hence $$2k-1=2^n+3,2k+1=2^n+5$$ where $n\ge2$. Then $k+1=2^{n-1}+3$ and it could be seen that $m=1+\binom{n-1}{2}$ for $n\ge3$. For $n=2$ it could be checked that there is exactly one good number $7$ in $[5,8]$. So $m=1+\binom{n-1}{2}$ is still valid since $\binom{1}{2}=0$.
If they are not consecutive good numbers, then $2k$ is also good. Hence both jumps from $2k-1$ to $2k$ and $2k$ to $2k+1$ are of type (iii), which is impossible because it requires that $2k+1$ is even.
Therefore we have $\boxed{m=1+\binom{\ell}{2},\ell\in\mathbb{N}.}$
No comments:
Post a Comment