Kvant Math Problem 1075

Consider the problem in terms of digit patterns.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m01s
Source on kvant.digital

Problem

Find the largest natural number whose decimal representation satisfies the condition that each digit (except for the first and last) is strictly less than the half-sum of its two neighboring digits.

S. E. Rukshin

Leningrad City Mathematical Olympiad (1987)

Exploration

Consider the problem in terms of digit patterns. Let a number be $d_1 d_2 \dots d_n$ with digits $d_i \in {0,1,\dots,9}$. The condition is that for each internal digit $d_i$ with $1 < i < n$,

$$d_i < \frac{d_{i-1} + d_{i+1}}{2}.$$

Equivalently, $2d_i < d_{i-1} + d_{i+1}$. Examine small examples. For a three-digit number $d_1 d_2 d_3$, the inequality reduces to $2d_2 < d_1 + d_3$, so $d_2 < (d_1 + d_3)/2$. If $d_1 = d_3 = 9$, then $d_2 < 9$; choosing $d_2 = 8$ works. Increasing the number means choosing digits as large as possible, so starting with $d_1 = 9$ is natural. If $d_2 = 9$, then $2\cdot9 = 18 \not< 18$, so $d_2 = 8$ is maximal. Extending to more digits, notice that any local maximum cannot occur at an internal position: the condition forbids $d_i$ from being greater than or equal to the average of its neighbors. Hence digits must alternate weakly: a peak cannot be flanked by digits smaller than itself. Attempting a sequence $9,8,9,8$ satisfies $2 \cdot 8 < 9+9 = 18$, giving $16<18$, valid. Extending further suggests a pattern alternating between $9$ and $8$, ending with a $9$ for maximal value. Test longer sequences: $9,8,9,8,9$ works; $9,8,9,8,9,8,9$ works as well. Check if any digit can exceed $9$—no, digits are at most $9$. The pattern $9,8,9,8,\dots,9$ seems promising. Consider an internal digit $d_i = 7$ between $8$ and $9$: $2\cdot7 = 14 < 17$, satisfied. But lowering $d_i$ reduces the total number. Hence the largest number likely has the first, last, and every other internal digit $9$, with intervening digits $8$.

Problem Understanding

The task is to find the largest natural number whose decimal digits satisfy that each internal digit is strictly less than the half-sum of its neighbors. This is a Type C problem: find the maximal value of a number under digit constraints. The core difficulty is understanding the constraints on consecutive digits and recognizing the maximal pattern of alternation between digits, taking into account that increasing one digit may force reduction in neighbors. Intuitively, the largest number starts with $9$ and continues as long as the pattern $9,8,9,8,\dots$ can be maintained, ending with $9$.

Proof Architecture

Lemma 1: For any internal digit $d_i$, $d_i$ cannot be greater than both neighbors; if $d_{i-1}$ and $d_{i+1}$ are equal, $d_i$ must be strictly smaller. This follows directly from $2d_i < d_{i-1} + d_{i+1}$.

Lemma 2: If $d_1 = 9$ and $d_2 < 9$, the sequence that maximizes the number alternates $9$ and $8$ until the last digit, which is $9$. This follows from Lemma 1 and the requirement to maximize each digit.

Lemma 3: Any internal sequence longer than two digits cannot contain consecutive $9$s. This is because two $9$s would require an internal digit $2d_i < 9+9 = 18$, so $d_i < 9$, forbidding a second $9$ at an internal position.

Lemma 4: Extending the alternation as long as possible produces the maximal number, because reducing any $9$ to $8$ reduces the total value. The hardest step is proving that the alternation pattern cannot be extended further to achieve a larger number by introducing a different digit arrangement.

Solution

Let the number be $d_1 d_2 \dots d_n$. The inequality for internal digits reads $2d_i < d_{i-1} + d_{i+1}$. To maximize the number, choose $d_1 = 9$. For $d_2$, $2d_2 < d_1 + d_3 \le 18$, so $d_2 \le 8$. Setting $d_2 = 8$ is optimal. Then $d_3$ satisfies $2d_3 < d_2 + d_4 \le 8 + 9 = 17$, so $d_3 \le 8$, but maximizing requires $d_3 = 9$. Continue alternation: $d_4 = 8$, $d_5 = 9$, etc. Lemma 3 ensures that no two $9$s are consecutive internally, confirming alternation.

To determine length, the last digit should be $9$ to maximize value. Any sequence ending with $8$ can be increased by setting the last digit $9$ and adjusting the penultimate digit to satisfy the inequality: if $d_{n-1} = 8$ and $d_n = 9$, then $2\cdot8 = 16 < 9 + d_{n-2}$, requiring $d_{n-2} \ge 7$, possible in the alternation pattern.

Hence the maximal number is an odd-length sequence beginning and ending with $9$, alternating $9,8,9,8,\dots,9$. Explicitly, for $n$ digits, the number is

$$989898\cdots 9$$

with as many pairs $98$ as possible. The exact length can be arbitrary, but the maximal decimal representation for a fixed length $n$ is this alternating pattern. For illustration, the largest number of length five is $98989$, of length seven is $9898989$, etc. This completes the construction and verification.

Verification of Key Steps

Consider the crucial step of verifying that no internal digit can exceed $9$ and that no consecutive internal $9$s are allowed. For three digits $d_1 d_2 d_3$ with $d_1=d_3=9$, the inequality gives $2d_2 < 18$, so $d_2 \le 8$. Setting $d_2=8$ is maximal. Extending to $d_4$ with $d_3 = 9$ and $d_5 = 9$ gives $2d_4 < 9 + 9 = 18$, so $d_4 \le 8$, confirming the alternation is necessary. Testing sequences $998$ or $899$ fails the inequality, verifying the alternation is forced. Independent calculation with $d_1 d_2 d_3 d_4 d_5 = 9 8 9 8 9$ confirms all inequalities: $2\cdot8 =16 < 9+9 =18$ and $2\cdot9 =18 < 8+8=16$ fails for internal $9$, so only $9$ at positions $1,3,5$ works.

Alternative Approaches

An alternative method involves viewing the inequality as a convexity condition: each internal digit must lie strictly below the average of its neighbors, forbidding local maxima. Under this interpretation, the largest number corresponds to a sequence where peaks and valleys alternate, starting and ending with a peak $9$. This approach is more abstract and geometric, but requires the same analysis of maximal digits and parity of positions. The main approach is preferable because it directly constructs the maximal number digit by digit, immediately producing the extremal sequence without invoking convexity arguments.