1990 USAMO Problems/Problem 4

From AoPSWiki

Problem

Find, with proof, the number of positive integers whose base- $n$ representation consists of distinct digits with the property that, except for the leftmost digit, every digit differs by $\pm 1$ from some digit further to the left. (Your answer should be an explicit function of $n$ in simplest form.)

Solution

Let a $k$ -good sequence be a sequence of distinct integers $\{ a_i \}_{i=1}^k$ such that for all integers $2\le i \le k$ , $a_i$ differs from some preceding term by $\pm 1$ .

Lemma. Let $a$ be an integer. Then there are $2^{k-1}$ $k$ -good sequences starting on $a$ , and furthermore, the terms of each of these sequences constitute a permutation of $k$ consecutive integers.

Proof. We induct on $k$ . For $k=1$ , the lemma is trivially true. Now, suppose the lemma holds for $k$ . If $\{ a_i \}_{i=1}^{k+1}$ is a $(k+1)$ -good sequence, then $\{ a_i \}_{i=1}^k$ is a $k$ -good sequence which starts on $a$ , so it is a permutation of $k$ consecutive integers, say $m, \dotsc, M$ . Then the only possibilities for $a_{k+1}$ are $m-1$ and $M+1$ ; either way, $\{ a_i \}_{i=1}^{k+1}$ constitutes a permutation of $k+1$ consecutive integers. Since there are $2^k$ possible sequences $\{a_i\}_{i=1}^k$ , and 2 choices of $a_{k+1}$ for each of these sequences, it also follows that there are $2^k \cdot 2 = 2^{k+1}$ $(k+1)$ -good sequences which start on $a$ . Thus the lemma holds by induction. $\blacksquare$

We now consider the number of desired positive integers with $k$ digits. Evidently, $k$ must be less than or equal to $n$ . We also note that the digits of such an integer must constitute a $k$ -good sequence. Since the minimum of this sequence can be any of the digits $0, \dotsc, n-k$ , unless the minimum is 0 and is the first digit (in which case the only possible sequence is an increasing arithmetic sequence), and there are $2^{k-1}$ $k$ -good sequences up to translation, it follows that there are $(n-k+1) 2^{k-1}-1$ desired positive integers with $k$ digits. Thus the total number of desired positive integers is $\begin{align*}\sum_{k=1}^n \bigl[ (n-k+1) 2^{k-1}-1 \bigr] &= -n + \sum_{k=1}^n \sum_{j=k}^n 2^{k-1} = -n + \sum_{j=1}^n ...$ which is equal to $2^{n+1} - 2(n+2)$ , our answer. $\blacksquare$