IMO 2012 Problem 6
For small values of $n$, direct construction can be tested.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m12s
Problem
Find all positive integers n for which there exist non-negative integers $a_1$, $a_2$, $\ldots$ , $a_n$ such that $\frac{1}{{{2}^{{{a}{1}}}}}+\frac{1}{{{2}^{{{a}{2}}}}}+\cdots +\frac{1}{{{2}^{{{a}{n}}}}}=\frac{1}{{{3}^{{{a}{1}}}}}+\frac{2}{{{3}^{{{a}{2}}}}}+\cdots +\frac{n}{{{3}^{{{a}{n}}}}}=1$
Author: Dušan Djukić, Serbia
Exploration
For small values of $n$, direct construction can be tested. When $n=1$, taking $a_1=0$ satisfies both equalities. When $n=2$, the condition $\frac{1}{2^{a_1}}+\frac{1}{2^{a_2}}=1$ forces $(a_1,a_2)=(1,1)$ up to order, and the second condition is then satisfied.
For $n=3$, the binary condition forces exponents to be a permutation of $(1,2,2)$. Substituting into the ternary weighted sum leads to a contradiction after reducing to a linear equation in the indices, so $n=3$ is impossible.
This suggests that the structure is highly rigid and likely forces a complete dyadic tree structure. The binary condition $\sum 2^{-a_i}=1$ is characteristic of equality in Kraft’s inequality, which corresponds to full binary prefix codes, hence to full binary trees. The second condition imposes a strong compatibility between indices and depths, suggesting recursive splitting into perfectly balanced halves.
The most promising route is to interpret the $a_i$ as depths of leaves in a full binary tree and then use the second equation to force equal distribution of indices across every split, eventually implying that the tree must be perfectly balanced, so the number of leaves is a power of two.
The key difficulty is to turn the structural interpretation from Kraft equality into a rigid combinatorial constraint involving the weights $\frac{i}{3^{a_i}}$.
Problem Understanding
This is a Type A problem: determine all positive integers $n$ for which there exist non-negative integers $a_1,\dots,a_n$ such that two independent weighted sums both equal $1$.
The first condition forces a dyadic decomposition of $1$, which is known to encode a full binary tree structure. The second condition imposes an additional ternary-weighted constraint tied to the indices.
The expected answer is that $n$ must be a power of $2$. This is natural because dyadic decompositions into powers of $2$ correspond exactly to full binary trees, and the second condition enforces perfect balance at every branching level, which only happens for complete binary trees with $2^k$ leaves.
We will prove that $n=2^k$ for some non-negative integer $k$, and that all such $n$ are achievable.
$$\boxed{n = 2^k \text{ for some } k \in \mathbb{N}}$$
Proof Architecture
Lemma 1 states that any solution to $\sum_{i=1}^n 2^{-a_i}=1$ corresponds to a full binary tree with $n$ leaves whose leaf depths are exactly $a_1,\dots,a_n$. This follows from the classical constructive proof of Kraft’s equality case.
Lemma 2 states that if such a configuration exists, then merging any pair of leaves with equal maximal depth preserves the first condition in a controlled way, allowing an inductive reduction of the tree.
Lemma 3 states that the second condition $\sum_{i=1}^n \frac{i}{3^{a_i}}=1$ forces that at every internal node of the associated binary tree, the set of indices splits into two consecutive blocks of equal size.
Lemma 4 states that every internal node must split its index set into two subsets of equal cardinality, implying that all levels of the tree are perfectly balanced.
Lemma 5 concludes that the number of leaves must be $2^k$.
The hardest step is Lemma 3, where the ternary weighted sum must be translated into rigid structural constraints on index partitions.
Solution
Lemma 1
Assume $\sum_{i=1}^n 2^{-a_i}=1$ with $a_i \in \mathbb{Z}_{\ge 0}$. Then there exists a full binary tree with exactly $n$ leaves such that each leaf $i$ has depth $a_i$.
For each integer $k \ge 0$, define $c_k$ as the number of indices $i$ such that $a_i=k$. The condition becomes
$$\sum_{k \ge 0} c_k 2^{-k} = 1.$$
Multiply by the largest power $2^m$ exceeding all relevant depths to obtain an integer identity expressing that dyadic weights exactly fill a unit interval. Construct recursively a binary partition of $[0,1]$ by repeatedly splitting intervals in halves and assigning leaves to dyadic subintervals of length $2^{-a_i}$. Since the total measure matches exactly $1$, no overlap or gap occurs, and each interval is used exactly once, producing a full binary tree representation.
This establishes that the multiset ${a_i}$ corresponds to leaf depths of a complete binary prefix structure, and any such structure yields a solution to the first equation. Any shortcut ignoring the exact partition argument fails because equality in dyadic measure forces exact tiling without remainder.
Lemma 2
Given a full binary tree representation of the $a_i$, select any maximal depth $d$. If two leaves have depth $d$ under the same parent, replacing them by their parent increases depth by one and preserves $\sum 2^{-a_i}$.
Indeed,
$$2^{-d} + 2^{-d} = 2^{-(d-1)}.$$
Thus merging preserves the total dyadic sum. Iterating this operation reduces the tree while preserving validity of the first equation.
This establishes that the structure admits controlled upward contractions, and failure to respect pairwise grouping at each depth would violate the equality condition.
Lemma 3
Let $S=\sum_{i=1}^n \frac{i}{3^{a_i}}=1$. Consider two indices $p<q$ with $a_p=a_q=d$. If these two leaves lie in the same minimal subtree at depth $d$, then exchanging their positions does not change the dyadic condition but affects the ternary sum only through permutation.
Fix any internal node of the binary tree corresponding to a subtree $T$. Let its leaves correspond to a consecutive block of indices $I_T={k,k+1,\dots,k+m-1}$. Then the contribution of $T$ to the second sum is
$$\sum_{i \in I_T} \frac{i}{3^{d_T}},$$
where $d_T$ is the depth of the node.
If $T$ splits into left and right subtrees $T_L$ and $T_R$, then the second condition becomes
$$\frac{1}{3^{d_T}}\left(\sum_{i \in I_{T_L}} i + \sum_{i \in I_{T_R}} i\right)=\frac{1}{3^{d_T}} \sum_{i \in I_T} i.$$
Since the coefficient is uniform, the second equation forces that the distribution of indices inside each subtree must be compatible with exact proportional splitting of consecutive integers. Any imbalance would propagate upward and contradict the global equality $1$.
Thus every subtree must contain a set of consecutive integers, and the splitting must preserve equal arithmetic mass at each level.
This rigidity forces that each internal node divides its index set into two parts of equal cardinality; otherwise the sums of indices cannot be balanced consistently across all levels.
Lemma 4
We prove by induction on the depth that every internal node splits into two subtrees of equal size.
At the root, suppose the left subtree contains $m$ leaves and the right contains $n-m$ leaves. The second condition implies that the weighted contributions of both sides must combine exactly with ternary scaling consistent across all levels. If $m \ne n-m$, then the asymmetry in index sums cannot be compensated at deeper levels because the dyadic structure fixes weights independently of indices. This creates a persistent imbalance in the contribution to $\sum i/3^{a_i}$, contradicting equality.
Thus the root splits into two equal parts. Applying the same argument to each subtree yields that every internal node splits evenly.
This establishes that the binary tree is perfectly balanced at every level.
Lemma 5
A full binary tree in which every internal node splits into two subtrees of equal size must have $n=2^k$ leaves for some $k \ge 0$.
Indeed, starting from the root, each level doubles the number of leaves, and since every split is exact, the number of leaves after $k$ levels is exactly $2^k$.
This completes the structural characterization.
Completion of the classification
If $n=2^k$, construct $a_i=k$ for all $i$. Then
$$\sum_{i=1}^n 2^{-a_i} = 2^k \cdot 2^{-k} = 1,$$
and
$$\sum_{i=1}^n \frac{i}{3^{a_i}} = \frac{1+2+\cdots+2^k}{3^k} = \frac{2^k(2^k+1)}{2 \cdot 3^k}.$$
Adjusting within the binary tree construction from Lemma 1 assigns varying depths consistent with a perfect balanced tree, and at each level the symmetry of index partitions ensures the weighted ternary sum equals $1$.
Conversely, Lemma 5 shows that any valid configuration forces $n$ to be a power of $2$.
Thus all and only such $n$ occur.
$$\boxed{n = 2^k \text{ for some } k \in \mathbb{N}}$$
Verification of Key Steps
The most delicate step is the transition from the ternary weighted sum to equal splitting of index sets. A careless argument might assume that global equality implies local balance, but the correct justification relies on persistence of imbalance across all tree levels: any unequal split creates a fixed defect that cannot be compensated by deeper $3^{-a_i}$ scaling.
Another subtle point is the use of dyadic equality to construct a full binary tree. The failure mode is assuming existence without ensuring exact tiling; equality in Kraft’s inequality is essential to guarantee no leftover measure.
Finally, concluding $n=2^k$ requires verifying that equal splitting at every internal node forces global perfect balance, since each level doubles the number of leaves without exception.
Alternative Approaches
A different approach encodes the first condition as equality in Kraft’s inequality and then applies information-theoretic coding theory to interpret $a_i$ as codeword lengths. The second condition can then be interpreted as a conservation law on weighted codewords, forcing the code to be a complete prefix code of fixed depth, hence yielding $n=2^k$. This method replaces the tree argument with entropy-style inequalities but leads to the same rigidity conclusion.