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
An upno has digits strictly increasing left-to-right (length ≥ 2). A downno has digits strictly decreasing left-to-right (length ≥ 2). Let U be the total count of upnos and D the total count of downnos. Find |U - D|.

Pick an answer.

(A)
~512
(B)
~10
(C)
~0
(D)
~9
(E)
~511

AMC 10 2023 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Solve an Easier Related Problem

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,…,9} of size ≥ 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.

1STEP 1

Warm up on 2-digit cases: upnos = C(9,2)=36, downnos = C(10,2)=45; the gap 9 is exactly the downnos ending in 0.

C(9, 2)=36, C(10, 2)=45, 45-36=9
2STEP 2

Generalize: each number is fixed by its digit-set, so U counts size-≥2 subsets of {1..9} and D counts size-≥2 subsets of {0..9}.

U = #{S⊆{1,…,9}: |S| ≥ 2}, D = #{T⊆{0,1,…,9}: |T| ≥ 2}
3STEP 3

0-free downno sets match the upno sets one-for-one, so the whole difference is D - U = the downnos whose set contains 0.

D - U = #{T⊆{0,1,…,9}: 0∈ T, |T| ≥ 2}
4STEP 4

Count 0-containing sets: any non-empty subset of {1..9} plus 0, giving 2⁹ - 1 = 511, so |U - D| = 511.

|U - D| = 2⁹ - 1 = 512 - 1 = 511 → (E) 511
Answer
~511
Sanity check the 2-digit slice: downnos ending in 0 are 10,20,…,90 — exactly 9 of them. The general formula predicts 2⁹ - 1 = 511 "0-ending" downnos of all lengths combined. Cross-check the totals: U = 2⁹ - 9 - 1 = 502 (subsets of {1,…,9} of size ≥ 2) and D = 2¹⁰ - 10 - 1 = 1013, so D - U = 1013 - 502 = 511. The answer 511 also matches one of the choices exactly — choice (E).
💡Key takeaway

An upno is just a set of digits from {1,…,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,…,9}. So |U-D| = 2⁹ - 1 = (E) 511.