AMC 10 · 2023 · #16

Grade 8 arithmetic

combinations-basicdigit-countingsystematic-enumerationcombinatorial-identity easier-related-problemcomplementary-countingidentify-subproblems ↑ Prerequisites: combinations-basicsystematic-enumeration

📏 Long solution 💡 3 insights

Problem

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|$ ?

Pick an answer.

(A)

~512

(B)

~10

(C)

(D)

(E)

~511

View mode:

Toolkit + CCSS Solution

Understand

Restated: An $\textit{upno}$ has digits strictly increasing left-to-right (length $\ge 2$). A $\textit{downno}$ has digits strictly decreasing left-to-right (length $\ge 2$). Let $U$ be the total count of upnos and $D$ the total count of downnos. Find $|U - D|$.

Givens: Upno = $2+$ digit number with strictly increasing digits (e.g. $258$); Downno = $2+$ digit number with strictly decreasing digits (e.g. $8620$); Answer choices: (A) $512$, (B) $10$, (C) $0$, (D) $9$, (E) $511$

Unknowns: $|U - D|$

Understand

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #2 Make a Systematic List, #16 Change Focus / Count the Complement

Once you notice that picking a set of digits and writing them in order is the WHOLE choice, the counting collapses: $U$ = (subsets of $\{1,\dots,9\}$ of size $\ge 2$), $D$ = same PLUS the extra downnos that contain $0$. Tool #9 (small cases) builds the bijection insight, Tool #2 (systematic list) checks the small case by hand, and Tool #16 (focus on the difference $D - U$) reduces $|U-D|$ to a single subset count.

Execute — Answer: E

#9 Solve an Easier Related Problem 4.OA.B.4 Step 1

Easier case: count $2$-digit upnos and downnos by hand.
A $2$-digit upno is any pair $\{a,b\}\subset\{1,\dots,9\}$ with $a<b$, so there are $\binom{9}{2}=36$ of them.
A $2$-digit downno is any pair $\{a,b\}\subset\{0,1,\dots,9\}$ with $a>b$, so there are $\binom{10}{2}=45$.
The gap is $45-36=9$ — exactly the $9$ downnos ending in $0$ ($10,20,30,\dots,90$).

$$\binom{9}{2}=36,\ \binom{10}{2}=45,\ 45-36=9$$

💡 Trying the smallest case ($2$ digits) reveals the whole pattern: the only difference between upnos and downnos is the extra digit $0$ available to downnos.

#2 Make a Systematic List 7.SP.C.8 Step 2

Generalize: an upno is uniquely determined by its set of digits chosen from $\{1,2,\dots,9\}$ (size $\ge 2$) — write them in increasing order.
A downno is uniquely determined by its set of digits chosen from $\{0,1,\dots,9\}$ (size $\ge 2$) — write them in decreasing order.
So choosing the digit-set IS the entire problem.

$$U = \#\{S\subseteq\{1,\dots,9\}: |S|\ge 2\},\quad D = \#\{T\subseteq\{0,1,\dots,9\}: |T|\ge 2\}$$

💡 Once digits are picked, the order is forced — so counting upnos/downnos becomes counting subsets, a pure combinations question.

#16 Change Focus / Count the Complement 7.SP.C.8 Step 3

Split downno digit-sets $T$ into two disjoint families: those with $0\notin T$ and those with $0\in T$.
Sets with $0\notin T$ are exactly subsets of $\{1,\dots,9\}$ of size $\ge 2$ — they match the upno sets one-for-one.
So $D = U + (\text{number of downno sets that contain }0)$.

$$D - U = \#\{T\subseteq\{0,1,\dots,9\}: 0\in T,\ |T|\ge 2\}$$

💡 Pair each upno's digit-set with the same downno's digit-set; the leftover downnos are exactly the ones containing $0$. Counting the leftover is the whole job.

#16 Change Focus / Count the Complement 8.EE.A.1 Step 4

Count downno digit-sets containing $0$: pick any non-empty subset of the other $9$ digits $\{1,2,\dots,9\}$, then add $0$ to it (this guarantees size $\ge 2$).
The number of non-empty subsets of a $9$-element set is $2^9 - 1 = 511$.
So $D - U = 511$, hence $|U - D| = 511$.

$$|U - D| = 2^9 - 1 = 512 - 1 = 511 \;\Rightarrow\; \textbf{(E) }511$$

💡 Each of the $9$ non-zero digits is independently "in" or "out", giving $2^9$ subsets; subtract the empty one because we need at least one partner for $0$.

[1] #9 4.OA.B.4 Easier case: count $2$-digit upnos and downnos by hand. A $2$-digit upno is any

[2] #2 7.SP.C.8 Generalize: an upno is uniquely determined by its set of digits chosen from ${1

[3] #16 7.SP.C.8 Split downno digit-sets $T$ into two disjoint families: those with $0\notin T$ a

[4] #16 8.EE.A.1 Count downno digit-sets containing $0$: pick any non-empty subset of the other $

Review

Reasonableness: Sanity check the $2$-digit slice: downnos ending in $0$ are $10,20,\dots,90$ — exactly $9$ of them. The general formula predicts $2^9 - 1 = 511$ "$0$-ending" downnos of all lengths combined. Cross-check the totals: $U = 2^9 - 9 - 1 = 502$ (subsets of $\{1,\dots,9\}$ of size $\ge 2$) and $D = 2^{10} - 10 - 1 = 1013$, so $D - U = 1013 - 502 = 511$. The answer $511$ also matches one of the choices exactly — choice (E).

Alternative: Tool #13 (Convert to Algebra) using direct binomial sums: $U = \sum_{k=2}^{9}\binom{9}{k} = 2^9 - 1 - 9 = 502$, and $D = \sum_{k=2}^{10}\binom{10}{k} = 2^{10} - 1 - 10 = 1013$, so $|U-D| = 1013 - 502 = 511$ — same answer (E).

CCSS standards used (min grade 8)

4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (Hand-counting the $2$-digit warm-up cases ($\binom{9}{2}=36$ and $\binom{10}{2}=45$) by listing pairs — pure small-number combinatorics.)
7.SP.C.8 Find probabilities of compound events using organized lists, tables, and simulation (Recognizing that choosing a digit-set IS the whole problem (since order is forced), so counting upnos/downnos is counting subsets — the systematic-list / combinations skill behind compound-event counts.)
8.EE.A.1 Know and apply the properties of integer exponents (Evaluating $2^9 = 512$ and computing $2^9 - 1 = 511$ to count non-empty subsets of a $9$-element set.)

⭐ An upno is just a set of digits from $\{1,\dots,9\}$ written low-to-high; a downno can also use $0$ (placed at the end). The two counts match perfectly EXCEPT for downnos that include $0$, and those are in one-to-one correspondence with non-empty subsets of $\{1,\dots,9\}$. So $|U-D| = 2^9 - 1 = \textbf{(E) }511$.