Kvant Math Problem 857

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m36s
Source on kvant.digital

Problem

Among the first 1984 positive integers (from 1 to 1984), mark those that can be represented as the sum of five integer nonnegative powers of two (that is, five not necessarily distinct numbers 1, 2, 4, 8, $\ldots$). Which numbers will be more numerous: the marked or the unmarked ones?

S. Stadnichenko

Exploration

A number is marked if it can be written as a sum of exactly five powers of two, repetitions allowed. Since $1=2^0$, every summand is positive. Thus every marked number is at least $5$.

The binary representation suggests counting powers of two by looking at the number of $1$'s in the binary expansion. Let $s(n)$ denote that number. If $n$ is written as a sum of powers of two, the smallest possible number of summands is $s(n)$, obtained from its binary expansion.

A summand $2^k$ can be replaced by two summands $2^{k-1}+2^{k-1}$ whenever $k\ge1$. This increases the number of summands by $1$ and leaves the total unchanged. Hence from a representation with $s(n)$ summands we can obtain representations with more summands.

The parity of the number of summands may matter. Replacing one summand by two increases the number of summands by exactly $1$, so every number of summands between $s(n)$ and $n$ seems attainable. Testing:

For $n=6=4+2$, $s(n)=2$. We can get

$$6=2+2+1+1 \quad (4\text{ summands}),$$

and

$$6=1+1+1+1+1+1 \quad (6\text{ summands}).$$

Also

$$6=2+1+1+1+1 \quad (5\text{ summands}).$$

So intermediate values occur.

The total number of summands reaches $n$ by splitting everything into ones. Since each split increases the count by $1$, every integer between $s(n)$ and $n$ is attainable.

Therefore $n$ is marked iff $5$ lies between $s(n)$ and $n$. Since $n\ge5$ is automatic for any marked number and every $n\ge5$ satisfies $n\ge5$, the condition becomes simply

$$s(n)\le5.$$

Now count numbers $1\le n\le1984$ with at most five ones in binary.

Since

$$1024\le1984<2048=2^{11},$$

every such number uses at most $11$ binary digits.

Count first all numbers from $0$ to $2047$. Choosing positions of ones among $11$ binary places gives

$$\sum_{k=0}^{5}\binom{11}{k} =1+11+55+165+330+462=1024.$$

Exactly half of the $2048$ numbers have at most five ones, by symmetry.

Now remove numbers from $1985$ to $2047$. These have leading bit $2^{10}$ equal to $1$. Write

$$n=1024+m,\qquad 961\le m\le1023.$$

The last ten bits of $m$ run through all numbers from $961$ to $1023$.

A number in this range is marked iff its last ten bits contain at most four ones.

Since

$$1023=1111111111_2,$$

the interval $961\le m\le1023$ consists exactly of ten-bit strings beginning with the bits $1111$. Indeed,

$$961=1111000001_2.$$

Thus there are $64=2^6$ such strings. Their first four bits are fixed as ones, and the remaining six bits are arbitrary.

Among these $64$ strings, those with at most four ones total must have at most three ones among the last six bits. Their number is

$$\sum_{j=0}^{3}\binom{6}{j} =1+6+15+20=42.$$

Hence marked numbers up to $1984$ equal

$$1024-42=982.$$

Unmarked numbers equal

$$1984-982=1002.$$

So unmarked numbers are more numerous by $20$.

The delicate point is identifying the interval $961\le m\le1023$ as exactly the ten-bit strings with first four bits equal to $1$.

Problem Understanding

We must determine whether, among the integers $1,2,\dots,1984$, there are more numbers representable as a sum of five nonnegative powers of two or more numbers that are not representable in that form.

This is a Type C problem, since we must determine and compare the two quantities.

The core difficulty is counting efficiently the integers that admit a representation as a sum of exactly five powers of two. The binary expansion converts the existence of such a representation into a condition on the number of ones in the binary representation.

The answer is that the unmarked numbers are more numerous. The reason is that a number can be represented as a sum of five powers of two exactly when its binary expansion contains at most five ones, and such numbers can be counted combinatorially.

Proof Architecture

Lemma 1. A positive integer $n$ can be represented as a sum of exactly five powers of two if and only if the number $s(n)$ of ones in its binary expansion satisfies $s(n)\le5$; this follows because binary expansion gives a representation with $s(n)$ summands and each splitting $2^k=2^{k-1}+2^{k-1}$ increases the number of summands by one.

Lemma 2. Among the integers from $0$ to $2047$, exactly

$$\sum_{k=0}^{5}\binom{11}{k}=1024$$

have at most five ones in binary; this follows by choosing positions of ones among $11$ binary places.

Lemma 3. Among the integers from $1985$ to $2047$, exactly

$$\sum_{j=0}^{3}\binom{6}{j}=42$$

have at most five ones in binary; this follows from the fixed leading pattern $1111$ in the lower ten bits.

The hardest direction is Lemma 1, namely proving that every number of summands between $s(n)$ and $n$ can be achieved.

The lemma most likely to fail under scrutiny is Lemma 3, because it requires a precise description of the interval $1985,\dots,2047$ in binary form.

Solution

Let $s(n)$ denote the number of ones in the binary expansion of $n$.

We first characterize the marked numbers.

The binary expansion of $n$ expresses it as a sum of exactly $s(n)$ powers of two. Thus $n$ is a sum of $s(n)$ powers of two.

Conversely, suppose a representation of $n$ contains a summand $2^k$ with $k\ge1$. Replacing this summand by

$$2^{k-1}+2^{k-1}$$

does not change the value of the sum and increases the number of summands by $1$.

Starting from the binary representation of $n$, which has $s(n)$ summands, we may repeatedly perform such splittings. If all summands are eventually split into ones, we obtain a representation of $n$ with $n$ summands. Since each splitting changes the number of summands by exactly $1$, every number of summands between $s(n)$ and $n$ occurs.

Hence $n$ can be represented as a sum of exactly five powers of two if and only if

$$s(n)\le5\le n.$$

Since every number with $s(n)\le5$ is positive and satisfies $n\ge s(n)$, the condition $5\le n$ is automatic whenever a representation with five positive summands exists. Therefore

$$n \text{ is marked } \Longleftrightarrow s(n)\le5.$$

Now count such numbers.

Since

$$2048=2^{11},$$

every integer from $0$ to $2047$ has an $11$-bit binary representation. Choosing the positions of the ones, the number of integers with at most five ones equals

$$\sum_{k=0}^{5}\binom{11}{k} =1+11+55+165+330+462 =1024.$$

We must exclude the integers from $1985$ to $2047$.

Write

$$n=1024+m.$$

Then

$$1985\le n\le2047 \quad\Longleftrightarrow\quad 961\le m\le1023.$$

The number $1023$ has binary form

$$1111111111_2,$$

while

$$961=1111000001_2.$$

Thus the numbers $961,\dots,1023$ are precisely the ten-bit strings whose first four bits are fixed equal to $1$, while the remaining six bits are arbitrary. There are $2^6=64$ such strings.

For $n=1024+m$, the leading bit contributes one additional $1$. Therefore $n$ has at most five ones if and only if the ten-bit string for $m$ has at most four ones.

Since the first four bits of $m$ are already ones, the remaining six bits must contain at most three ones. The number of such strings is

$$\sum_{j=0}^{3}\binom{6}{j} =1+6+15+20 =42.$$

Hence the number of marked integers in $1,\dots,1984$ is

$$1024-42=982.$$

The number of unmarked integers is

$$1984-982=1002.$$

Since

$$1002>982,$$

the unmarked numbers are more numerous. The difference is

$$1002-982=20.$$

$$\boxed{\text{Unmarked numbers are more numerous; there are }1002\text{ unmarked and }982\text{ marked.}}$$

Verification of Key Steps

The first delicate step is the characterization $s(n)\le5$. Starting from the binary representation, the number of summands is $s(n)$. Every splitting

$$2^k\mapsto 2^{k-1}+2^{k-1}$$

increases the number of summands by exactly one. After all possible splittings, every summand becomes $1$, producing $n$ summands. Thus every integer count between $s(n)$ and $n$ is attained. A careless argument might prove only that counts larger than $s(n)$ are possible, without showing that no gaps occur.

The second delicate step is describing the interval $961\le m\le1023$. Since

$$961=1111000001_2, \qquad 1023=1111111111_2,$$

all numbers in this interval have the first four binary digits equal to $1$. Any ten-bit string beginning with $1111$ represents a number at least $1111000000_2=960$, and all such numbers except $960$ lie in the interval. There are exactly $64$ such strings, corresponding to the six unrestricted trailing bits.

The third delicate step is counting the excluded marked numbers. The leading bit of $n=1024+m$ contributes one $1$. Since the first four bits of $m$ are already ones, $n$ can have at most five ones only when the last six bits contain at most three ones. The count is

$$\binom60+\binom61+\binom62+\binom63=42.$$

Replacing “at most three” by “at most four” would give an incorrect count.

Alternative Approaches

A different counting method uses symmetry. Among the $2048$ integers from $0$ to $2047$, complementing all $11$ bits pairs a number with $k$ ones to a number with $11-k$ ones. Since $11$ is odd, exactly half of the numbers have at most five ones, giving $1024$ immediately. The remainder of the argument then counts the correction coming from the interval $1985,\dots,2047$.

Another approach counts unmarked numbers directly. A number is unmarked exactly when its binary expansion contains at least six ones. Among all $11$-bit strings there are

$$\sum_{k=6}^{11}\binom{11}{k}=1024$$

such strings. One then adds back the numbers from $1985$ to $2047$ having at least six ones. This leads to the same final totals, but the presented solution keeps the characterization and counting aligned with the definition of marked numbers.