Call a positive integer $\textit{fair}$ if no digit is used more than once, it has no 0s, and no digit is adjacent to two greater digits. For example, $196$, $23$, and $12463$ are fair, but $1546$, $320$, and $34321$ are not fair. How many fair positive integers are there?
$\textbf{(A) } 511 \qquad\textbf{(B) } 2584 \qquad\textbf{(C) } 9841 \qquad\textbf{(D) } 17711 \qquad\textbf{(E) } 19682$
Difficulty: 91/100 — A challenging combinatorics problem which is easy to understand yet somewhat difficult to execute.
Core Concepts:permutations, binomial theorem
Challenges: Finding a general formula for the number of $n$-digit numbers which satisfy the condition.
Techniques: Interpret the condition as a "mountain," with the largest number at the peak and the smallest numbers on the edges. Once you achieve the desired sum, the binomial theorem can be applied to finish the problem.
Error-prone Steps: Forgetting to divide the sum by $2$ when the binomial theorem is applied.
Ideal Time: Experienced: ≤ 4 min
Intermediate: ≤ 10 min
Beginner: would not solve