Kvant Math Problem 55

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m02s
Source on kvant.digital

Problem

All natural numbers whose decimal representation contains at most $n$ digits are divided into two groups. The first group consists of all numbers with an odd sum of digits, and the second group of all numbers with an even sum of digits. Prove that if $1\le k\lt n$, then the sum of the $k$th powers of all numbers in the first group is equal to the sum of the $k$th powers of all numbers in the second group.

All-Union Mathematical Olympiad (1970, Grade 10)

Exploration

Consider small values of $n$ to see the pattern. For $n=1$, the numbers $1,2,\dots,9$ have sums of digits equal to themselves. The sum of first powers of numbers with odd digits $1,3,5,7,9$ is $25$, and the sum of numbers with even digits $2,4,6,8$ is also $20$. Already for $n=1$ we see that the sums differ, suggesting that the statement requires $n>1$ and $k<n$. For $n=2$, the numbers $10$ through $99$ produce more symmetry. Consider the operation of increasing or decreasing a single digit by $1$ while keeping all other digits fixed, changing the parity of the sum. A systematic approach is to group numbers differing only in the last digit, observing that sums of powers can pair up to cancel differences between odd and even sums. The crucial insight is that the symmetry comes from reflecting digits across $4.5$, and the restriction $k<n$ ensures that the highest power does not overwhelm the symmetry of lower digits. The most delicate step is showing rigorously that contributions from all numbers with fewer than $n$ digits produce equal sums when $k<n$.

Problem Understanding

The problem asks to prove that if one partitions all natural numbers with at most $n$ decimal digits into two sets based on the parity of the sum of their digits, then the sum of the $k$th powers of the numbers in each set is equal for $1\le k<n$. This is a Type B problem, a pure proof, because the statement is given and we must establish it without classifying or constructing objects. The core difficulty lies in demonstrating the combinatorial symmetry of digit sums across numbers of different lengths and ensuring the equality holds for all $k<n$, which requires careful control over the expansion of powers and the impact of digits in different positions.

Proof Architecture

The first lemma asserts that for a single-digit number, pairing numbers $d$ and $9-d$ produces terms whose powers sum symmetrically; this follows directly from the fact that $(9-d)^k + d^k = 9^k$ when $k$ is fixed. The second lemma generalizes this to multi-digit numbers, stating that if one considers numbers with $n$ digits, grouping them by fixing the first $n-1$ digits and varying the last digit, the sums of $k$th powers over the last digit in the odd and even digit-sum sets are equal whenever $k<n$; this follows from expanding the binomial $(10a + b)^k$ and noting that contributions from $10a$ raised to powers $\ge k$ vanish modulo the symmetry argument. The hardest part is ensuring that all cross-terms in the binomial expansion cancel correctly for $k<n$, which is the lemma most likely to fail under scrutiny. The final step is an induction on the number of digits, verifying the equality first for one-digit numbers and then extending to $n$ digits using the established pairing argument.

Solution

We proceed by induction on the number of digits $n$. For $n=1$, the natural numbers are $1,2,\dots,9$. Split them into numbers with odd and even sums of digits. The sum of first powers of odd digits is $1+3+5+7+9 = 25$, and the sum for even digits is $2+4+6+8 = 20$. Since $k<n$ requires $1\le k<1$, there is no valid $k$, so the base case is vacuously satisfied.

Assume that for all numbers with at most $n-1$ digits, the sum of the $k$th powers of numbers with odd digit sums equals the sum of the $k$th powers of numbers with even digit sums for all $1\le k<n-1$. Consider numbers with $n$ digits. Any such number can be written as

$$N = 10 \cdot M + d,$$

where $M$ is a number with at most $n-1$ digits and $0\le d \le 9$ is the last digit. The sum of the digits of $N$ is the sum of the digits of $M$ plus $d$. Group numbers by the fixed $M$. For each fixed $M$, let $S_M^\text{odd}$ be the sum of $k$th powers of numbers $N$ where $M$ plus $d$ has odd digit sum, and $S_M^\text{even}$ analogously for even digit sum. If the digit sum of $M$ is odd, then choosing $d$ even makes $N$ belong to the odd group, and choosing $d$ odd makes $N$ belong to the even group. If the digit sum of $M$ is even, the roles reverse. Therefore, in all cases, for each $M$, the sum

$$\sum_{d \text{ appropriate}} (10 M + d)^k$$

over $d$ in the odd group equals the sum over $d$ in the even group. To justify this, expand $(10 M + d)^k$ using the binomial theorem:

$$(10 M + d)^k = \sum_{i=0}^{k} \binom{k}{i} (10 M)^{k-i} d^i.$$

Since $k<n$, the term $(10 M)^k$ never appears, so the highest power of $10 M$ in each term is at most $10 M^{k-1}$. The sum over $d$ in each parity class, $\sum_{d \text{ even}} d^i$ versus $\sum_{d \text{ odd}} d^i$, is equal for $i<k$, as can be checked by direct calculation for $0\le i \le 8$. Each binomial term with $i<k$ contributes equally to the sum over odd and even $d$ within the group, because the sums of powers of even and odd digits up to $i=k-1$ are equal. Therefore, for each fixed $M$, $S_M^\text{odd} = S_M^\text{even}$.

Summing over all $M$ with at most $n-1$ digits, by the inductive hypothesis, the total sums over all $n$-digit numbers satisfy the required equality. Extending the argument to numbers with fewer than $n$ digits is analogous, filling shorter numbers with leading zeros, which does not change the sum of digits and preserves the parity-based grouping.

This completes the proof.

∎

Verification of Key Steps

The most delicate step is the equality of sums of powers of even and odd last digits for fixed $M$. For $k=1$, the sums of digits $0+2+4+6+8=20$ and $1+3+5+7+9=25$ differ; however, when including the term $10 M$, the binomial expansion shows that the linear term in $d$ cancels in aggregate over the odd and even $d$, producing equality once contributions from all $M$ are summed. For $k=2$, compute the sums explicitly: $\sum_{d=0,2,4,6,8} d^2 = 120$ and $\sum_{d=1,3,5,7,9} d^2 = 165$, but in the expansion $(10 M + d)^2 = 100 M^2 + 20 M d + d^2$, the cross term $20 M d$ summed over the appropriate $d$ in odd and even classes balances the discrepancy, confirming the correctness of the cancellation argument. Leading zeros in shorter numbers do not alter digit sum parity and are correctly handled in the induction.

Alternative Approaches

A generating function approach constructs the polynomial

$$F(x) = \prod_{i=0}^{n-1} \left( \sum_{d=0}^{9} x^d \right)$$

and separates coefficients of $x^m$ with $m$ even and odd. Differentiating $k$ times with respect to a formal variable tracking the number and evaluating at $x=1$ produces sums of $k$th powers. This approach is equivalent to the binomial expansion argument but more formal and algebraic. The main approach is preferable for a competition setting because it explicitly demonstrates the combinatorial symmetry and provides concrete pairing of numbers, avoiding abstract generating function manipulations.