Call a positive integer $n$ Distinct, if it does not have repeating digits, and for every digit $d$ in $n$,
if it is not the first digit in $n$, then either $d-1$ or $d+1$ appears before it. (for example 21345 is distinct). How many 9-digit integers are distinct?
$\textbf{(A)}\ 255\qquad\textbf{(B)}\ 256\qquad\textbf{(C)}\ 511$
$\qquad\textbf{(D)}\ 512\qquad\textbf{(E)}\ 767$
To solve this, we need the following:
Lemma: For using digits $1,2, \cdots, k$, where $k\le 9$, we can make $2^{k-1}$ distinct numbers.
Proof: For $k=1$, it is 1. For $k=2$, it is 12 and 21. Assume it is true for $k-1$, for the $k$ case, you can only put the $k$ before or after $k-1$, so just multiplies 2. QED.
Now, to answer our question, we will do the case work.
It will miss a number.
Case 1: if it misses 0, then we get $2^8=256$ distinct numbers.
Case 2: if it misses 1, 0 has to be in the front, but no digit can be at the second, so this is not possible.
case 3: misses 2, we must have 9876543 inside of it, cannot happen.
similarly, cannot miss 3, or 4, or 5, or 6, or 7, or 8. The only possibility is to miss 9. supposely,
we should have 256 distinct numbers. But one of them is not working, 012345678, so we get $256-1=$255.
The answer is 511.