AMC 10 · 2023 · #16

학년 8 arithmetic

combinations-basicdigit-countingsystematic-enumerationcombinatorial-identity easier-related-problemcomplementary-countingidentify-subproblems ↑ 선수 지식: combinations-basicsystematic-enumeration

📏 긴 풀이 💡 3 개 인사이트

문제

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

답을 골라 클릭하세요.

(A)

~512

(B)

~10

(C)

(D)

(E)

~511

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $\textit{upno}$ 는 자릿수가 왼쪽에서 오른쪽으로 엄격히 증가하는 $2$ 자리 이상의 양의 정수이고, $\textit{downno}$ 는 자릿수가 엄격히 감소하는 $2$ 자리 이상의 양의 정수입니다. $U$ 를 upno 의 총 개수, $D$ 를 downno 의 총 개수라 할 때 $|U - D|$ 를 구하세요.

주어진 것: Upno = 자릿수가 엄격히 증가하는 $2$ 자리 이상의 수 (예: $258$); Downno = 자릿수가 엄격히 감소하는 $2$ 자리 이상의 수 (예: $8620$); 선택지: (A) $512$, (B) $10$, (C) $0$, (D) $9$, (E) $511$

구하는 것: $|U - D|$

이해

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #2 빠짐없이 나열하기, #16 관점 바꾸기

자릿수 집합을 고르고 순서대로 적기만 하면 되므로 세기 문제로 단번에 환원됩니다. $U$ 는 $\{1,\dots,9\}$ 의 크기 $\ge 2$ 부분집합의 개수, $D$ 는 $\{0,1,\dots,9\}$ 의 크기 $\ge 2$ 부분집합의 개수. 도구 #9(작은 사례) 가 일대일 대응을 발견하게 하고, 도구 #2(체계적 나열) 가 작은 사례를 손으로 확인, 도구 #16(차이에만 집중) 이 $|U-D|$ 를 한 가지 부분집합 세기로 줄여 줍니다.

실행 — 정답: E

#9 더 쉬운 문제로 줄이기 4.OA.B.4 단계 1

쉬운 사례: 두 자리 upno 와 downno 를 손으로 세어 봅니다.
두 자리 upno 는 $\{a,b\}\subset\{1,\dots,9\}$ ($a<b$) 의 쌍이니 $\binom{9}{2}=36$ 개.
두 자리 downno 는 $\{a,b\}\subset\{0,1,\dots,9\}$ ($a>b$) 의 쌍이니 $\binom{10}{2}=45$ 개.
차이는 $45-36=9$ — 정확히 $0$ 으로 끝나는 downno $9$ 개 ($10, 20, \dots, 90$).

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

💡 가장 작은 사례 ($2$ 자리) 가 전체 패턴을 보여 줍니다 — upno 와 downno 의 유일한 차이는 downno 에만 허용되는 추가 자릿수 $0$ 입니다.

#2 빠짐없이 나열하기 7.SP.C.8 단계 2

일반화: upno 는 $\{1,2,\dots,9\}$ 에서 고른 크기 $\ge 2$ 의 부분집합 하나로 완전히 결정 (증가 순서로 배열).
Downno 는 $\{0,1,\dots,9\}$ 에서 고른 크기 $\ge 2$ 의 부분집합 하나로 완전히 결정 (감소 순서로 배열).
즉 자릿수 집합 선택이 곧 문제입니다.

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

💡 자릿수만 정해지면 순서는 자동 — 그래서 upno/downno 세기가 부분집합 세기로 바뀝니다.

#16 관점 바꾸기 7.SP.C.8 단계 3

Downno 의 자릿수 집합 $T$ 를 두 그룹으로 가릅니다: $0\notin T$ 와 $0\in T$.
$0$ 을 포함하지 않는 집합은 $\{1,\dots,9\}$ 의 크기 $\ge 2$ 부분집합과 같으므로 upno 의 집합과 일대일 대응 — 즉 $D = U + (0$ 을 포함하는 downno 집합 수$)$.

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

💡 각 upno 의 자릿수 집합을 같은 자릿수 집합의 downno 와 짝지으면, 남는 downno 가 바로 $0$ 을 포함하는 것들. 그 수만 세면 끝.

#16 관점 바꾸기 8.EE.A.1 단계 4

$0$ 을 포함하는 downno 의 자릿수 집합 세기: 나머지 $9$ 개 자릿수 $\{1,2,\dots,9\}$ 에서 공집합이 아닌 부분집합을 고른 뒤 $0$ 을 더하면 됩니다 (크기 $\ge 2$ 자동 보장).
$9$ 원 집합의 공집합 아닌 부분집합은 $2^9 - 1 = 511$ 개.
따라서 $D - U = 511$, 즉 $|U - D| = 511$.

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

💡 $9$ 개 비영(非零) 자릿수 각각이 "포함/제외" 의 두 가지 — $2^9$ 가지. 공집합 한 가지를 빼면 $0$ 의 짝이 항상 있는 경우의 수.

[1] #9 4.OA.B.4 쉬운 사례: 두 자리 upno 와 downno 를 손으로 세어 봅니다. 두 자리 upno 는 ${a,b}\subset{1,\dots,9}

[2] #2 7.SP.C.8 일반화: upno 는 $\{1,2,\dots,9\}$ 에서 고른 크기 $\ge 2$ 의 부분집합 하나로 완전히 결정 (증가 순서로 배열). Do

[3] #16 7.SP.C.8 Downno 의 자릿수 집합 $T$ 를 두 그룹으로 가릅니다: $0\notin T$ 와 $0\in T$. $0$ 을 포함하지 않는 집합은 ${

[4] #16 8.EE.A.1 $0$ 을 포함하는 downno 의 자릿수 집합 세기: 나머지 $9$ 개 자릿수 $\{1,2,\dots,9\}$ 에서 공집합이 아닌 부분집합을

검토

합리성 확인: 두 자리 사례 점검: $0$ 으로 끝나는 두 자리 downno 는 $10, 20, \dots, 90$ 의 $9$ 개 — 정확히 맞음. 일반 공식은 모든 길이를 합쳐서 $2^9 - 1 = 511$ 개의 "$0$ 끝" downno 를 예측. 총 개수 교차 확인: $U = 2^9 - 9 - 1 = 502$, $D = 2^{10} - 10 - 1 = 1013$ 이고 $D - U = 1013 - 502 = 511$. 선택지 (E) 와 정확히 일치.

대안 접근: 도구 #13(대수로 바꾸기) — 이항 합으로 직접 계산: $U = \sum_{k=2}^{9}\binom{9}{k} = 2^9 - 1 - 9 = 502$, $D = \sum_{k=2}^{10}\binom{10}{k} = 2^{10} - 1 - 10 = 1013$, $|U-D| = 1013 - 502 = 511$ — 같은 답 (E).

사용된 CCSS 표준 (최저 학년 8)

4.OA.B.4 약수쌍·배수 찾기, 소수/합성수 판별 (두 자리 사례 ($\binom{9}{2}=36,\ \binom{10}{2}=45$) 를 손으로 쌍을 나열하며 세는 단순 조합 계산에 사용.)
7.SP.C.8 표·목록·시뮬레이션으로 복합 사건의 확률 구하기 (자릿수 집합을 고르면 순서가 강제되므로 upno/downno 세기가 부분집합(=조합) 세기가 됨을 인식하는 데 사용.)
8.EE.A.1 정수 지수의 성질을 알고 적용 ($2^9 = 512$ 를 계산하고 $9$ 원 집합의 공집합 아닌 부분집합 수 $2^9 - 1 = 511$ 을 구하는 데 사용.)

⭐ Upno 는 $\{1,\dots,9\}$ 에서 고른 자릿수 집합을 작은 수부터 적은 것이고, downno 는 $0$ 도 쓸 수 있는 집합을 큰 수부터 적은 것 (단 $0$ 은 맨 끝). 두 개수는 $0$ 을 포함하는 downno 만큼 차이가 나는데, 그 수는 $\{1,\dots,9\}$ 의 공집합 아닌 부분집합 수와 같으므로 $|U-D| = 2^9 - 1 = \textbf{(E) }511$.