Maths Olympiad Prep

Library / /3 of 4

Algebra Difficulty 7.6 National Olympiad, round 2 Prove it Romania

Let mm and nn be positive integers, where m<2nm < 2^n. Determine the smallest possible number of not necessarily pairwise distinct powers of 2 that add up to m(2n1)m \cdot (2^n - 1).

Solution

The required minimum is nn.
To prove this, notice that the sum of two like powers of 2 is again a power of 2, so the number of powers of 2 that add up to a positive integer kk can successively be decreased while keeping the sum constant. The process then ends up with kk being expressed as a sum of pairwise distinct powers of 2; that is, the binary expansion of kk. At this stage, the number of summands can no longer be decreased, so the smallest number of powers of 2 that add up to kk is equal to the number of units in the binary expansion of kk.

1st Proof.
Since multiplication by a power of 2 does not change the number of units in a binary expansion, we may and will assume that mm is odd. Leaving aside the trivial case m=1m = 1, let m3m \ge 3 so its binary expansion is m=1+i=1p2kim = 1 + \sum_{i=1}^{p} 2^{k_i}, where 0<k1<k2<<kp0 < k_1 < k_2 < \dots < k_p; and since m<2nm < 2^n, it follows that kp<nk_p < n, so p<np < n. Now, write m(2n1)=2n(m1)+((2n1)(m1))=i=1p2n+ki+(i=0n12ii=1p2ki)m \cdot (2^n - 1) = 2^n \cdot (m-1) + ((2^n - 1) - (m-1)) = \sum_{i=1}^{p} 2^{n+k_i} + (\sum_{i=0}^{n-1} 2^i - \sum_{i=1}^{p} 2^{k_i}).

The first sum consists of exactly pp pairwise distinct powers of 2, each of which is greater than 2n2^n, and the number in parentheses is the sum of exactly npn - p pairwise distinct powers of 2, each of which is less than 2n2^n.
Consequently, m(2n1)m \cdot (2^n - 1) is the sum of exactly p+(np)=np + (n - p) = n pairwise distinct powers of 2; that is, its binary expansion has exactly nn units, as stated.

2nd Proof.
If m=2km = 2^k for some k<nk < n, then m(2n1)=2n+k1+2n+k2++2k+1+2km \cdot (2^n - 1) = 2^{n+k-1} + 2^{n+k-2} + \dots + 2^{k+1} + 2^k, so the binary expansion of m(2n1)m \cdot (2^n - 1) has exactly nn units.
If mm is not a power of 2, let m=i=1p2kim = \sum_{i=1}^{p} 2^{k_i}, where p2p \ge 2 and 0k1<k2<<kp0 \le k_1 < k_2 < \dots < k_p, be the binary expansion of mm, to write m(2n1)=m2nm=(m2n2n+k1)+(2n+k1m)=i=2p2n+ki+(2n+k1i=1p2ki)m \cdot (2^n - 1) = m \cdot 2^n - m = (m \cdot 2^n - 2^{n+k_1}) + (2^{n+k_1} - m) = \sum_{i=2}^{p} 2^{n+k_i} + (2^{n+k_1} - \sum_{i=1}^{p} 2^{k_i}).
Clearly, the first sum is an integer greater than 2n+k12^{n+k_1} whose binary expansion has exactly p1p-1 units.
The number in parentheses is a positive integer (m<2n2n+k1m < 2^n \le 2^{n+k_1}) smaller than 2n+k12^{n+k_1} whose binary expansion has exactly n+k1kp+i=1p1(ki+1ki1)=np+1n+k_1-k_p+\sum_{i=1}^{p-1}(k_{i+1}-k_i-1) = n-p+1 units.
Consequently, the binary expansion of m(2n1)m \cdot (2^n - 1) has exactly (p1)+(np+1)=n(p-1) + (n-p+1) = n units, as stated.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.