# 2007 iTest Problems/Problem 35

## Problem 35

Find the greatest natural number possessing the property that each of its digits except the first and last one is less than the arithmetic mean of the two neighboring digits.

## Solution

We seek to maximize the number of digits in the number (call it $N$) first, so the first and last digits should be 9. Next recognize that $N$ should be symmetric (like 5445 or 93239), and that if there are ever consecutive digits the number cannot contain any digits less than the lower consecutive digit. If $N$ begins with 98, then it must be 9889. If $N$ begins with 97, it can either be 9779, 97679, or 976679. If $N$ begins with 96, it can either be 9669, 96569, 965569, 96469, 964469, 9643469, or 96433469. If $N$ begins with 95, it has the maximum value 95322359, which is less than 96433469. Clearly if $N$ starts with a lower second digit it is less than this number, so $N=\boxed{96433469}$. Note the differences between consecutive digits in this number.