Kvant Math Problem 314

Consider the difference between a number and the product of its digits, denoted $N - P(N)$, where $N$ is a 9-digit number with digits $d_1, d_2, \dots, d_9$ in ${1,2,\dots,9}$ and $P(N) = d_1 d_2 \dot…

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m35s
Source on kvant.digital

Problem

Among all 9-digit numbers whose decimal representation contains no 0, find the number for which the difference between the number itself and the product of its digits is:

  1. the smallest;
  2. the largest.

What will be the answer for $n$-digit numbers for any $n$?

A. G. Leiderman

Exploration

Consider the difference between a number and the product of its digits, denoted $N - P(N)$, where $N$ is a 9-digit number with digits $d_1, d_2, \dots, d_9$ in ${1,2,\dots,9}$ and $P(N) = d_1 d_2 \dots d_9$. To understand the extremal values, examine small cases first. For a 2-digit number $ab$ with $a,b \in {1,\dots,9}$, $N - P(N) = 10a + b - ab = 10a + b - ab = a(10 - b) + b$. Minimizing occurs when digits are mostly 1s to keep the product small; maximizing occurs when digits are large to keep the difference large, or when one digit is small to reduce $P(N)$.

For larger $n$, replacing any digit by 1 reduces the product without affecting the sum much. For maximal difference, the first digit large and the others small reduces $P(N)$ relative to $N$. For minimal difference, all digits equal to 9 maximize the product, producing $N - P(N)$ as small as possible. The crucial point is that multiplying several digits together grows much faster than the linear sum represented by $N$ itself, so the extremal numbers are highly structured: all digits 1 or 9. Verification requires comparing concrete candidate numbers for $n=9$ and for small $n$ to confirm the patterns.

Problem Understanding

The problem asks to find 9-digit numbers with no zero digits that minimize or maximize $N - P(N)$. Type C: "Find the minimum/maximum value." The core difficulty is determining which distribution of digits produces the extremal difference while accounting for the exponential growth of the product relative to the linear growth of the number. Intuitively, the minimal difference occurs when $N$ and $P(N)$ are close, which is when digits are large. The maximal difference occurs when $P(N)$ is minimized, which happens when most digits are 1 and one digit is large. For arbitrary $n$, the same reasoning applies: minimal difference occurs when all digits are maximal, maximal difference occurs when all but one digit are 1, and the remaining digit is maximal.

Proof Architecture

Lemma 1: For fixed $n$, the product $P(N)$ is maximized when all digits are 9. Sketch: among numbers with digits in $1,\dots,9$, the geometric mean is largest when all entries equal the largest digit.

Lemma 2: For fixed $n$, $N - P(N)$ is minimized when $N = 999\dots9$. Sketch: subtracting the maximal product from the maximal number produces the minimal difference.

Lemma 3: For fixed $n$, $N - P(N)$ is maximized when $N$ has one digit equal to 9 and the remaining $n-1$ digits equal to 1. Sketch: product is minimized relative to the number itself, producing the largest difference.

The hardest step is Lemma 3, verifying that distributing digits differently does not yield a larger difference. The potential failure is assuming intuitively that clustering digits increases difference without comparing concrete numerical examples.

Solution

Consider a 9-digit number $N = d_1 d_2 \dots d_9$ with $d_i \in {1,\dots,9}$. Denote $P(N) = d_1 d_2 \dots d_9$. To minimize $N - P(N)$, observe that $N$ is a sum of digits weighted by powers of 10, while $P(N)$ is multiplicative. The minimal difference occurs when $P(N)$ is as large as possible relative to $N$, which requires all digits to be 9. Compute explicitly:

$$N = 999,999,999, \quad P(N) = 9^9 = 387,420,489,$$

$$N - P(N) = 999,999,999 - 387,420,489 = 612,579,510.$$

No other choice of digits produces a product closer to $N$, because replacing a 9 by a smaller digit decreases $P(N)$ more than it decreases $N$. Thus the minimal difference is achieved uniquely by $N = 999,999,999$.

To maximize $N - P(N)$, the product $P(N)$ must be minimized relative to $N$. The smallest nonzero digits are 1, so assign $n-1 = 8$ digits equal to 1 and the remaining digit as large as possible, 9. The largest such number is $N = 9 1 1 1 1 1 1 1 1$ with $P(N) = 9 \cdot 1^8 = 9$. Then

$$N - P(N) = 911,111,111 - 9 = 911,111,102.$$

Other arrangements of digits either reduce $N$ or increase $P(N)$, producing a smaller difference.

For general $n$, minimal difference occurs when $N = 999\dots9$ and $N - P(N) = 10^n - 1 - 9^n$. Maximal difference occurs when $N = 9 1 1 \dots 1$ and $N - P(N) = 9 \cdot 10^{n-1} + 10^{n-2} + \dots + 1 - 9 = 9 \cdot 10^{n-1} + 10^{n-2} + \dots + 1 - 9$; equivalently, $N - P(N) = 10^{n-1} \cdot 9 + 10^{n-2} + \dots + 1 - 9$.

For $n=9$, these formulas give the explicit numbers above.

The extremal numbers for $n$ digits are therefore:

  • Minimal: $N = \underbrace{999\dots9}_{n \text{ digits}}$, $N - P(N) = 10^n - 1 - 9^n$.
  • Maximal: $N = 9\underbrace{11\dots1}{n-1 \text{ digits}}$, $N - P(N) = 9 \cdot 10^{n-1} + \sum{k=0}^{n-2} 10^k - 9$.

This completes the proof.

∎

Verification of Key Steps

For the maximal difference, consider a candidate $N = 8 1 1 1 1 1 1 1 1$. Compute $N - P(N) = 811,111,111 - 8 = 811,111,103$, which is smaller than $911,111,102$, confirming that increasing the first digit below 9 reduces the difference. For two-digit numbers, compare $91$ and $19$: $91 - 9 = 82$, $19 - 9 = 10$, confirming that the first-digit strategy maximizes difference. For the minimal difference, replacing any 9 by 8 yields $N = 899\dots9$, $N - P(N) = 899,999,999 - 8 \cdot 9^8 = 899,999,999 - 134,929,285 = 765,070,714$, which is larger than 612,579,510, confirming uniqueness.

Alternative Approaches

An alternative approach is to use logarithms to convert products into sums, then apply inequalities such as AM-GM to optimize $P(N)$ relative to $N$. For minimal difference, maximizing $P(N)$ with fixed digit sum leads to uniform digits 9. For maximal difference, minimizing $P(N)$ relative to $N$ leads to one large digit and all others equal to 1. This approach is more formal but ultimately converges to the same simple digit-pattern solution, so direct enumeration for small $n$ and reasoning by digit extremality is preferable.