Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1990 USAMO Problems/Problem 4"
(→‎Solution)
Line 16: Line 16:
 
&= -n + \sum_{j=1}^n (2^k-1) = - 2n -1 + \sum_{j=0}^n 2^k,
 
&= -n + \sum_{j=1}^n (2^k-1) = - 2n -1 + \sum_{j=0}^n 2^k,
 
\end{align*} </cmath>
 
\end{align*} </cmath>
−
which is equal to <math>2^{n+1} - 2(n+2)</math>, our answer.  <math>\blacksquare</math>
+
which is equal to <math>2^{n+1} - 2(n+1)</math>, our answer.  <math>\blacksquare</math>
  
  

Revision as of 21:59, 10 July 2016

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 \sum_{k=1}^j 2^{k-1} \\ &= -n + \sum_{j=1}^n (2^k-1) = - 2n -1 + \sum_{j=0}^n 2^k, \end{align*} which is equal to $2^{n+1} - 2(n+1)$, our answer. $\blacksquare$


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

1990 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_USAMO_Problems/Problem_4&oldid=79248"