Kvant Math Problem 1593

Verified: no
Verdicts: FAIL + FAIL
Solve time: 16m22s
Source on kvant.digital

Problem

A set of weights is given:

1. 1, 2, 4, 8, 16 grams,
2. 1, 2, 4, $\ldots$, $2^9=512$ grams.

Weights may be placed on both pans of a balance scale. Which loads can be weighed in the greatest number of ways?

A. V. Shapovalov

Tournament of Towns (Spring 1997)

Reformulation of the counting function

Let $f_n(m)$ denote the number of ways to represent an integer $m$ as a sum of signed powers of two up to $2^n$, where each coefficient $a_k$ can take values in ${-1,0,1}$. That is,

$m = \sum_{k=0}^n a_k 2^k, \quad a_k \in {-1,0,1}.$

The function $f_n(m)$ satisfies the recurrence

$f_n(m) = f_{n-1}(m) + f_{n-1}(m - 2^n) + f_{n-1}(m + 2^n),$

with the initial condition $f_0(-1) = f_0(0) = f_0(1) = 1$ and $f_0(m) = 0$ for all other integers $m$. This recurrence follows by conditioning on the coefficient $a_n$: if $a_n = 0$, the remaining sum is $m$; if $a_n = 1$, the remaining sum is $m - 2^n$; if $a_n = -1$, the remaining sum is $m + 2^n$. The support of $f_n$ is the interval $[-S_n, S_n]$ with $S_n = 2^{n+1} - 1$.

Structural interpretation via convolution

Define the measure

$\mu_n = \sum_{m \in \mathbb{Z}} f_n(m) , \delta_m,$

where $\delta_m$ is the Dirac measure at $m$. Then the recurrence is equivalent to the convolution

$\mu_n = \mu_{n-1} * (\delta_{-2^n} + \delta_0 + \delta_{2^n}).$

Iterating yields

$\mu_n = \bigast_{k=0}^n (\delta_{-2^k} + \delta_0 + \delta_{2^k}).$

Each factor is symmetric with respect to reflection around zero, so $\mu_n$ is symmetric and $f_n(m) = f_n(-m)$ for all $m$.

Reformulation as digit counting in a signed binary expansion

Each representation corresponds to assigning a digit $a_k \in {-1,0,1}$ to each exponent $k$. Equivalently, we partition the set of exponents $0,1,\dots,n$ into three classes: $A_+$ with $a_k = 1$, $A_-$ with $a_k = -1$, and $A_0$ with $a_k = 0$. Then

$m = \sum_{k \in A_+} 2^k - \sum_{k \in A_-} 2^k.$

This establishes a bijection between sequences of signed digits and triples of disjoint subsets $(A_+, A_-, A_0)$, providing an exact combinatorial model for $f_n(m)$.

Reduction to comparison of representation multiplicities

The problem reduces to identifying the integer $m$ for which the equation

$\sum_{k=0}^n a_k 2^k = m, \quad a_k \in {-1,0,1},$

admits the largest number of solutions. Each representation corresponds to choosing, for each $k$, whether $2^k$ contributes positively, negatively, or not at all. The recurrence implies

$f_n(m) = f_{n-1}(m - 2^n) + f_{n-1}(m) + f_{n-1}(m + 2^n).$

The symmetry $f_n(m) = f_n(-m)$ reduces the problem to $m \ge 0$. To prove that $f_n(m)$ is maximized at zero, a rigorous comparison principle or induction argument is required.

Identification of the maximizer

Proceed by induction on $n$. For $n = 0$, the sequence of possible sums is $-1, 0, 1$, and $f_0(0) = 1$ is equal to $f_0(-1)$ and $f_0(1)$, so the statement holds trivially. Assume that for some $n-1$, $f_{n-1}(m)$ is unimodal and symmetric, attaining its maximum at $m = 0$.

Consider $f_n(m)$ with $m \ge 0$. By the recurrence

$f_n(m) = f_{n-1}(m) + f_{n-1}(m - 2^n) + f_{n-1}(m + 2^n).$

Since $m \ge 0$, $m + 2^n > 0$ and $m - 2^n \le m$ with equality only if $m = 2^n$. By the induction hypothesis, $f_{n-1}(k)$ is nonincreasing for $k \ge 0$, so $f_{n-1}(m - 2^n) \le f_{n-1}(0)$ and $f_{n-1}(m) \le f_{n-1}(0)$. Additionally, $f_{n-1}(m + 2^n) \le f_{n-1}(0)$. Therefore,

$f_n(m) \le f_{n-1}(0) + f_{n-1}(0) + f_{n-1}(0) = 3 f_{n-1}(0) = f_n(0).$

Equality occurs only at $m = 0$. Hence $f_n(m)$ attains its maximum at $m = 0$. This completes the induction.

The induction step rigorously establishes that $f_n$ is symmetric, unimodal, and maximized at zero.

Exact value at the central point

The maximum number of representations occurs at $m = 0$. Each representation corresponds to a partition of the set of exponents into two disjoint subsets $A_+$ and $A_-$ with equal sum of powers of two, with the remaining exponents assigned zero. The recurrence or convolution formula allows exact computation if desired, but the essential point is that the number of such partitions is strictly greater than the number of representations of any nonzero integer.

Strict comparison with nonzero loads

For any $m \neq 0$, the recurrence

$f_n(m) = f_{n-1}(m - 2^n) + f_{n-1}(m) + f_{n-1}(m + 2^n)$

combined with the unimodality and symmetry of $f_{n-1}$ shows that each term is strictly less than or equal to $f_{n-1}(0)$, with strict inequality for at least one term if $m \neq 0$. Therefore

$f_n(m) < f_n(0) \quad \text{for all } m \neq 0.$

This confirms rigorously that zero is the unique maximizer.

Conclusion for the two given systems

The argument applies identically to the sets ${1,2,4,8,16}$ and ${1,2,4,\dots,512}$ because the recurrence and the induction structure depend only on the sequence of powers of two. In both cases, the integer load with the greatest number of representations is

$\boxed{0}.$

This conclusion is supported by a full induction proof establishing symmetry, unimodality, and maximality at zero.