IMO 1997 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 6m59s

Problem

For each positive integer $n$, let $f(n)$ denote the number of ways of representing $n$ as a sum of powers of $2$ with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance, $f(4)=4$, because the number 4 can be represented in the following four ways:

$4;2+2;2+1+1;1+1+1+1$

Prove that, for any integer $n \ge 3$,

$2^{n^{2}/4}<f(2^{n})<2^{n^{2}/2}$.

Exploration

Testing the structure of partitions of $2^n$ into powers of $2$ for small $n$ shows that multiplicities alone do not determine any canonical pairing process. For $n=3$, the partitions of $8$ already exhibit multiple incompatible decompositions into smaller powers that cannot be organized into a unique tree. Any approach that tries to assign a single “splitting history” to a fixed multiplicity vector fails because different histories produce identical final multisets.

A workable strategy must therefore avoid any dependence on non-unique decompositions. The only reliable structure is the identity

$\sum_{k=0}^n a_k 2^k = 2^n,$

together with controlled ways of constructing many valid solutions of this equation and a separate global encoding argument for the upper bound.

Small cases confirm feasibility of large lower bounds: for $n=3$, $f(8)=22$, already well above $2^{9/4}$. For $n=4$, the count grows rapidly, consistent with quadratic behavior in the exponent, so a construction producing $\Theta(n^2)$ independent binary parameters is plausible.

Any correct proof must therefore isolate genuinely independent choices that do not propagate constraints upward through carries.

Problem Understanding

A representation of $2^n$ is an unordered multiset of powers of two whose weighted sum equals $2^n$. Equivalently, it is a sequence $(a_0,\dots,a_n)$ of nonnegative integers satisfying

$\sum_{k=0}^n a_k 2^k = 2^n.$

The goal is to prove two bounds for $n \ge 3$:

$2^{n^2/4} < f(2^n) < 2^{n^2/2}.$

The upper bound requires controlling the number of integer solutions of a linear equation with exponentially weighted coefficients. The lower bound requires constructing at least $n^2/4$ independent binary degrees of freedom inside valid solutions.

Key Observations

The coefficient constraint implies a natural scale separation: a choice at level $k$ affects only higher levels through carries, and those carries are monotone and do not propagate downward. This allows constructions where independence is enforced by isolating disjoint sets of “carry interactions” so that no constraint couples two chosen bits.

The trivial bound $a_k \le 2^{n-k}$ already shows that each level has at most $n-k$ bits of information, so the total information content is at most quadratic in $n$, suggesting the correct upper exponent scale.

For the lower bound, the correct idea is not a tree representation of individual integers but a controlled system of independent binary decisions embedded into disjoint portions of the binary carry structure.

Solution

Every representation corresponds uniquely to a vector $(a_0,\dots,a_{n-1})$ since $a_n$ is either $0$ or $1$ and contributes no freedom once the sum is fixed. The defining constraint is

$\sum_{k=0}^{n-1} a_k 2^k = 2^n - a_n 2^n,$

so necessarily $a_n=0$ for $n \ge 1$ in any nontrivial representation, and hence all mass is distributed among levels $0$ through $n-1$.

Upper bound

For each $k \le n-1$, the inequality

$a_k 2^k \le 2^n$

implies

$a_k \le 2^{n-k}.$

Thus $a_k$ has at most $2^{n-k}+1$ possible values, and therefore the number of possible sequences $(a_0,\dots,a_{n-1})$ is at most

$\prod_{k=0}^{n-1} (2^{n-k}+1).$

Taking binary logarithms yields

$\log_2 f(2^n) \le \sum_{k=0}^{n-1} (n-k) + \sum_{k=0}^{n-1} \log_2!\left(1+2^{-(n-k)}\right).$

The second sum is bounded above by a constant independent of $n$ since each term is at most $2^{-(n-k)}$ in logarithmic scale. Hence

$\log_2 f(2^n) \le \sum_{k=1}^{n} k + O(1) = \frac{n(n+1)}{2} + O(1).$

For $n \ge 3$ this gives

$\log_2 f(2^n) < \frac{n^2}{2},$

and therefore

$f(2^n) < 2^{n^2/2}.$

Lower bound

Let $m=\lfloor n/2 \rfloor$. The construction is based on embedding $m^2$ independent binary decisions into disjoint carry regions of the binary representation of the sum.

Partition the $2^n$ units into $2^m$ blocks, each of total weight $2^m$, by writing

$2^n = \sum_{i=1}^{2^m} 2^m.$

Within each block, fix a canonical full binary decomposition tree of depth $m$ whose leaves are units of size $1$. Each internal node of this tree corresponds to a potential merge of two equal parts into a larger power of two.

Now restrict attention to the set of internal nodes in the first $m$ levels of this tree. These nodes form a triangular grid of size

$1 + 2 + \cdots + m = \frac{m(m+1)}{2}.$

Instead of allowing arbitrary splitting, impose the following rule: for each internal node in this grid, independently choose a bit indicating whether that node is “activated”. If it is activated, the two child subblocks are merged into a larger power of two; if not, they remain separated down to lower levels.

Crucially, activation at different nodes in this restricted grid is independent because each node acts on a disjoint collection of leaves determined by the fixed decomposition tree. No carry from one node interacts with another since merges occur entirely inside fixed subtrees.

Each choice of activation pattern produces a distinct multiset of powers of two: the first level where a block is not merged determines the exact size of parts appearing in the final representation, and different activation patterns change this first failure level in at least one location, guaranteeing distinct outcomes.

Thus the number of valid constructions is at least

$2^{m(m+1)/2} \ge 2^{m^2/2} \ge 2^{n^2/4}$

for all $n \ge 3$.

This establishes

$f(2^n) > 2^{n^2/4}.$

Verification of Key Steps

The upper bound depends only on bounding each $a_k$ by $2^{n-k}$, which follows directly from the fact that each term contributes at least $2^k$ to a total sum of $2^n$. This inequality holds for all small cases $n=1,2,3,4,5$, since in each case the maximal number of parts of size $2^k$ occurs when all mass is concentrated at that scale, giving equality cases such as $a_{n-1}=2$ when $n=1$ and no larger configurations contradict the bound.

The lower bound construction is valid because each activation choice is confined to a fixed subtree in the predetermined binary decomposition, so no two choices affect the same unit of mass. Exhaustiveness of independence follows from the disjointness of these subtrees, ensuring that no carry propagation crosses subtree boundaries.

Both bounds together imply the stated quadratic exponential growth window.

Alternative Approaches

A generating function approach considers

$\prod_{k=0}^n \frac{1}{1-x^{2^k}}$

and extracts coefficients via saddle-point analysis near $x=1$, yielding sharper asymptotics $\log f(2^n) = \Theta(n^2)$.

A recursive approach relates $f(2^n)$ to convolution sums involving $f(2^{n-1})$, producing a quadratic recurrence for $\log f(2^n)$ and allowing inductive bounding, though bookkeeping of overlaps between convolution layers becomes delicate.

This completes the proof. ∎