Track / Stage 3 / 7 of 260 #7 of 2000

Problem 7

AMC 10/12, early questions

Combinatorics Difficulty 3.0 Find the answer

Define an $\textit{upno}$ to be a positive integer of $2$ or more digits where the digits are strictly
increasing moving left to right. Similarly, define a $\textit{downno}$ to be a positive integer
of $2$ or more digits where the digits are strictly decreasing moving left to right. For
instance, the number $258$ is an upno and $8620$ is a downno. Let $U$ equal the total
number of $upnos$ and let $D$ equal the total number of $downnos$ . What is $|U-D|$ ?
$\textbf{(A)}~512\qquad\textbf{(B)}~10\qquad\textbf{(C)}~0\qquad\textbf{(D)}~9\qquad\textbf{(E)}~511$

Your answer

Official solution

First, we know that $D$ is greater than $U$ , since there are less upnos than downnos. To see why, we examine what determines an upno or downno.
We notice that, given any selection of unique digits (notice that "unique" constrains this to be a finite number), we can construct a unique downno. Similarly, we can also construct an upno, but the selection can not include the digit $0$ since that isn't valid.
Thus, there are $2^{10}$ total downnos and $2^9$ total upnos. However, we are told that each upno or downno must be at least $2$ digits, so we subtract out the $0$ -digit and $1$ -digit cases.
For the downnos, there are $10$ $1$ -digit cases, and for the upnos, there are $9$ $1$ -digit cases. There is $1$ $0$ -digit case for both upnos and downnos.
Thus, the difference is $\left(\left(2^{10}-10-1\right)-\left(2^9-9-1\right)\right)=2^9-1=\boxed{\textbf{(E) }511}.$
~Technodoggo ~minor edits by lucaswujc

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.