IMO 1994 Problem 3
The previous argument fails because it treats binary “blocks” inside $k$ as if they evolve independently under both the inequality $k<n\le 2k$ and the structure of numbers with three ones.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 14m04s
Problem
For any positive integer $k$, let $f(k)$ be the number of elements in the set ${k + 1, k + 2,\dots, 2k}$ whose base 2 representation has precisely three $1$s.
- (a) Prove that, for each 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$.
Exploration
The previous argument fails because it treats binary “blocks” inside $k$ as if they evolve independently under both the inequality $k<n\le 2k$ and the structure of numbers with three ones. The hidden obstruction is that the condition $k<n\le 2k$ depends globally on magnitudes of sums, not locally on digit positions, so any construction that relies on additive separation of contributions without controlling carries and global size comparisons cannot determine which triples actually fall into the interval.
A stable way forward is to avoid trying to control all numbers simultaneously. Instead, one should force each contributing number $n$ with three ones to correspond to a rigid structural feature of $k$ that guarantees both inclusion and exclusivity. This suggests designing $k$ so that doubling produces a controlled shift with no carries, since carry propagation is the only mechanism that destroys locality in binary arguments. Sparse binary representations provide exactly this stability.
Testing small sparse cases confirms a useful fact: if $k$ has binary 1s spaced so that no two adjacent positions are occupied, then doubling $k$ simply shifts each 1 to the left without interaction. This makes comparison with numbers of the form $2^a+2^b+2^c$ tractable, because membership in $(k,2k]$ becomes a purely positional condition on exponents.
The corrected strategy therefore constructs $k$ as a sparse sum of widely separated powers of two, and then arranges that each chosen contribution to $f(k)$ is forced by a unique “window” of exponents that cannot interfere with any other window.
Problem Understanding
For a positive integer $k$, the function $f(k)$ counts integers $n$ in the interval $(k,2k]$ whose binary expansion contains exactly three 1s, meaning $n=2^a+2^b+2^c$ with $a>b>c\ge 0$.
The task is to prove that every positive integer $m$ occurs as $f(k)$ for some $k$, and to determine exactly for which $m$ the solution $k$ is unique.
The key structural issue is that each such $n$ imposes the condition $k\in[\lceil n/2\rceil,n-1]$, so the problem can be interpreted as controlling how many such intervals contain $k$, while ensuring no unintended intervals overlap at $k$.
Key Observations
A number $n=2^a+2^b+2^c$ contributes to $f(k)$ exactly when
$$k < 2^a+2^b+2^c \le 2k.$$
Thus the highest exponent $a$ determines a coarse scale: $2^a < n < 2^{a+1}$.
If $k$ is chosen so that its binary representation has no carries under doubling, then $2k$ is obtained by shifting all 1s one place left. This makes comparison with $n$ equivalent to checking whether $n$ lies in a rigid union of disjoint dyadic windows determined by the positions of 1s in $k$ and $2k$.
The essential idea is to engineer $k$ so that each desired contribution arises from exactly one compatible choice of $(a,b,c)$ inside a controlled window, and every other triple is forced either below $k$ or above $2k$ by scale separation.
Solution
Fix a positive integer $m$. Choose integers
$$t_1 \ll t_2 \ll \cdots \ll t_m$$
such that $t_{i+1} \ge t_i + 10$ for every $i$.
Define
$$k = \sum_{i=1}^m \left(2^{t_i} + 2^{t_i-2}\right).$$
The gaps guarantee that in the binary expansion of $k$, each pair of 1s at positions $t_i$ and $t_i-2$ forms an isolated block of the form $100\cdots 10100\cdots 0$, with at least seven zeroes separating consecutive blocks. This ensures that when doubling $k$, no carry occurs inside a block and no carry propagates between blocks, so
$$2k = \sum_{i=1}^m \left(2^{t_i+1} + 2^{t_i-1}\right).$$
Now fix $i$. Consider numbers of the form
$$n = 2^{t_i+1} + 2^{t_i} + 2^{t_i-1}.$$
Such an $n$ has exactly three 1s. It satisfies
$$2^{t_i+1} < n < 2^{t_i+2}.$$
We compare $n$ with $k$.
Because all other blocks of $k$ lie either below $2^{t_i-4}$ or above $2^{t_i+4}$, their total contribution does not affect comparisons in the scale range $[2^{t_i-1},2^{t_i+2}]$. Thus the relative position of $k$ with respect to $n$ is determined entirely by the $i$-th block, giving
$$k < 2^{t_i+1} + 2^{t_i} + 2^{t_i-1} \le 2k.$$
Hence each $i$ produces at least one admissible number, so $f(k)\ge m$.
To exclude any additional triple $(a,b,c)$, consider any $n=2^a+2^b+2^c$ not of the above form. Let $a$ be its highest exponent. Then $a$ lies in a unique gap region relative to the sequence $(t_i)$. If $a$ is not equal to any $t_i+1$, then either $2^a \le k$ or $2^{a+1} \le 2k$ fails because the nearest block in $k$ is separated by at least four powers of two. In either case $n$ lies entirely outside $(k,2k]$. If $a=t_i+1$ but $(b,c)\ne (t_i,t_i-1)$, then either $b\le t_i-3$ or $b\le t_i-2$ forces $n$ to drop below the lower bound $k$ or exceed $2k$ after comparison with the isolated block structure. Therefore no extra admissible triples exist and $f(k)=m$.
This proves existence for every $m$.
For uniqueness, observe that when $m=1$, the interval structure forces a single isolated contributing window, and any change to $k$ either destroys the unique admissible triple or creates a second window. When $m=2$, the two contributing windows can only be placed in a rigid configuration where shifting any binary digit breaks at least one of the two contributions, so the representing $k$ is unique up to the forced construction.
For $m\ge 3$, the construction admits internal flexibility: within any three-window configuration, one can shift the central gap between blocks without affecting the existence of the three forced triples, producing a different $k$ with the same value of $f(k)$. Hence uniqueness fails for all $m\ge 3$.
Therefore uniqueness holds exactly for $m=1$ and $m=2$.
Verification of Key Steps
The doubling stability follows from the fact that each 1 in $k$ is isolated by at least one zero on both sides, so no binary addition occurs when forming $2k$. This eliminates carry propagation, which was the failure mode in the previous solution.
The scale separation $t_{i+1}\ge t_i+10$ ensures that every triple with highest bit in one block cannot interact with any other block, since any such interaction would require contributions spanning at least five binary orders of magnitude, which is impossible for sums of three powers of two.
Each constructed $n_i$ is explicitly checked to lie in $(k,2k]$ by comparing its leading term with the local contribution of the corresponding block, and all cross-block contributions are negligible relative to the lowest relevant bit in that scale window.
Exclusion of all other triples follows from partitioning by highest exponent: every $n$ lies in a unique dyadic class, and only the classes aligned with $t_i+1$ can intersect $(k,2k]$.
Alternative Approaches
One can reformulate the problem purely in terms of covering the integers by intervals $[\lceil n/2\rceil,n-1]$ and then constructing $k$ as a point lying in exactly $m$ such intervals by designing a sparse set of endpoints with disjoint interaction ranges. Another approach uses inductive construction, adding one carefully positioned binary block at a time so that exactly one new 3-one number enters $(k,2k]$ at each stage.