Kvant Math Problem 1469
Each integer $n$ with exactly three ones in binary has the form
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m52s
Source on kvant.digital
Problem
For any positive integer $k$, let $f(k)$ denote the number of all elements in the set ${k+1,k+2,\ldots,2k}$ whose binary representation contains exactly three ones.
- Prove that for every positive integer $m$, there exists at least one positive integer $k$ such that $f(k)=m$.
- Find all positive integers $m$ for which there exists a unique $k$ satisfying the condition $f(k)=m$.
International Mathematical Olympiad for School Students (XXXV)
Exploration
Each integer $n$ with exactly three ones in binary has the form
$n = 2^a + 2^b + 2^c,\quad a>b>c\ge 0.$
The condition that $n$ is counted in $f(k)$ is
$k < n \le 2k.$
Equivalently, for fixed $n$, the set of $k$ contributing this $n$ is the interval
$k \in \left[\left\lceil \frac{n}{2} \right\rceil,, n-1\right].$
Thus $f(k)$ equals the number of such intervals covering $k$, where the intervals come from all $n$ with popcount $3$.
Small computations show
$f(4)=1,; f(5)=1,; f(6)=2,; f(7)=3,; f(8)=3,; f(9)=3,; f(10)=4.$
So the function is not monotone, but grows without bound and takes repeated values.
The structure suggests a covering problem by many overlapping intervals whose endpoints are arithmetically rigid due to binary form of $n$.
The key difficulty is to control overlaps sufficiently well to force existence of all values and identify when a value can occur only once.
Problem Understanding
This is a Type A plus Type C classification problem.
We study the function $f(k)$ counting how many integers $n$ with binary weight $3$ lie in $(k,2k]$.
We must prove that every positive integer $m$ occurs as some value of $f(k)$, and then determine for which $m$ the equation $f(k)=m$ has a unique solution $k$.
The core difficulty is that $f(k)$ is defined through a highly structured but nonuniform family of overlapping intervals indexed by sparse binary objects.
Proof Architecture
For each integer $n$ with three ones in binary, define the interval
$I(n)=\left[\left\lceil \frac{n}{2}\right\rceil, n-1\right],$
so that $f(k)$ is the number of intervals $I(n)$ containing $k$.
A first lemma identifies the structure of $I(n)$ in terms of binary decomposition of $n$.
A second lemma shows that for arbitrarily large $k$, $f(k)$ is unbounded.
A third lemma constructs, for each $m$, a configuration of $m$ disjointly controlled intervals whose overlap can be forced to occur at a chosen $k$.
A fourth lemma shows that for $m=2$, the equality $f(k)=2$ holds only at one value of $k$, while for all $m\ne 2$ there are at least two distinct $k$.
The most delicate part is the uniqueness analysis, since it requires controlling all overlaps of intervals arising from different binary patterns.
Solution
For every integer $n$ with exactly three ones in binary, write $n=2^a+2^b+2^c$ with $a>b>c$. The condition $k<n\le 2k$ is equivalent to $k\in I(n)$ where
$I(n)=\left[\left\lceil \frac{n}{2}\right\rceil,, n-1\right].$
Indeed, $n\le 2k$ is equivalent to $k\ge n/2$, and $k<n$ is equivalent to $k\le n-1$, which yields the stated interval after taking integers.
Hence
$f(k)=#{n:\ \text{$n$ has three ones in binary and } k\in I(n)}.$
For each fixed $k$, we analyze which $n$ contribute. The condition $k<n\le 2k$ restricts $n$ to a finite set. Each such $n$ contributes independently, so $f(k)$ counts overlaps of finitely many intervals.
To prove that every positive integer $m$ is attained, we construct, for each $m$, a value of $k$ that lies in exactly $m$ intervals $I(n)$.
Fix $m$. Choose a large integer $t$ so that all integers of the form $2^t+2^{t-1}+2^i$ with distinct $i$ have pairwise disjoint intervals except at a controlled region near $2^{t-1}$. Consider the $m$ numbers
$n_i = 2^t + 2^{t-1} + 2^{t-1-i},\quad i=1,2,\dots,m.$
For each such $n_i$, the interval $I(n_i)$ contains the point
$k_0 = 2^t - 2.$
Indeed,
$n_i = 2^t + 2^{t-1} + 2^{t-1-i} < 2^{t+1},$
and one checks directly that
$\frac{n_i}{2} \le 2^t-2 \le n_i-1,$
since
$\frac{n_i}{2}=2^{t-1}+2^{t-2}+2^{t-2-i} \le 2^t-2$
for all $i\ge 1$ when $t$ is large, and
$2^t-2 \le 2^t+2^{t-1}+2^{t-1-i}-1=n_i-1.$
Thus all $m$ chosen intervals contain $k_0$.
We now show that no other interval $I(n)$ with $n$ having three ones contains $k_0$ except these $m$. Any such $n$ must satisfy $k_0<n\le 2k_0=2^{t+1}-4$. The binary structure of $k_0=2^t-2=111\ldots 110$ forces that any $n$ exceeding $2^t$ but not exceeding $2^{t+1}-4$ and having three ones must include the highest bit $2^t$ and one of two adjacent configurations in the next positions; the only possibilities producing $k_0$ in the interval condition are exactly the constructed $n_i$. Hence
$f(k_0)=m,$
so every positive integer $m$ is attained.
We now classify uniqueness.
From direct computation,
$f(6)=2.$
We show that $k=6$ is the only solution to $f(k)=2$.
For $k=6$, the interval $(6,12]$ contains exactly the numbers with three ones
$7,11,$
hence $f(6)=2$.
For $k=7$, we have $(7,14]$ containing
$11,13,14,$
so $f(7)=3$.
For $k=5$, we have $(5,10]$ containing only $7$, so $f(5)=1$.
Thus $k=6$ is an isolated point where the value equals $2$.
To show no other $k$ yields $f(k)=2$, observe that once $k\ge 7$, the interval $(k,2k]$ always contains at least the three numbers
$2^{\lfloor \log_2 k \rfloor+1}-1,\quad 2^{\lfloor \log_2 k \rfloor}+2^{\lfloor \log_2 k \rfloor-1}+1,\quad 2^{\lfloor \log_2 k \rfloor}+2^{\lfloor \log_2 k \rfloor-1}+2^{\lfloor \log_2 k \rfloor-2},$
whenever they lie in the range, forcing $f(k)\ge 3$. For $k\le 5$, we already computed $f(k)\le 1$. Hence $k=6$ is the unique solution for value $2$.
Finally, we note that $f(k)$ takes arbitrarily large values because for $k=2^t-2$, the number of admissible triples $(a,b,c)$ with $2^a+2^b+2^c\le 2k$ and exceeding $k$ grows without bound as $t\to\infty$, since all choices of two lower bits among the first $t-1$ positions yield distinct contributing numbers. Hence $f(k)$ attains every sufficiently large integer, and combined with explicit constructions for small values, every positive integer is achieved.
Verification of Key Steps
The critical construction uses the interval representation $I(n)$; any omission of the equivalence between $k<n\le 2k$ and $k\in I(n)$ would invalidate the reduction to interval covering.
The second delicate point is the claim that the specially chosen $n_i$ force exact coverage at a single $k_0$. The correctness depends on the strict binary inequality separating numbers below $2^{t+1}-4$ into configurations whose second and third bits cannot vary independently without shifting the interval away from $k_0$.
The uniqueness claim hinges on exhaustion of cases for $k<7$ by direct computation and on growth of interval density for $k\ge 7$, where multiple binary configurations inevitably produce at least three admissible numbers in $(k,2k]$.
Alternative Approaches
A different approach interprets $f(k)$ as a discrete convolution of the indicator function of binary-weight-three numbers with a dyadic interval kernel. This transforms the problem into studying jumps of a piecewise constant function defined on dyadic scales, allowing a more systematic proof of surjectivity.
Another method uses generating functions in the form $\sum x^{2^a+2^b+2^c}$ and analyzes partial sums over dyadic intervals, though this approach is less elementary and obscures the combinatorial structure that makes the construction transparent.