combinations-basicdigit-countingsystematic-enumerationcombinatorial-identityeasier-related-problemcomplementary-countingidentify-subproblems↑ 선수 지식:combinations-basicsystematic-enumeration
📏 긴 풀이💡 3 개 인사이트
문제
Define an upno to be a positive integer of 2 or more digits where the digits are strictly increasing moving left to right. Similarly, define a 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∣?
문제 재정리: $\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|$
이해
문제 재정리: $\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$
계획
주요 도구: #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$ 가지. 공집합 한 가지를 빼면 $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.8Downno 의 자릿수 집합 $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) 와 정확히 일치.
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$.
⭐ Upno 는 $\{1,\dots,9\}$ 에서 고른 자릿수 집합을 작은 수부터 적은 것이고, downno 는 $0$ 도 쓸 수 있는 집합을 큰 수부터 적은 것 (단 $0$ 은 맨 끝). 두 개수는 $0$ 을 포함하는 downno 만큼 차이가 나는데, 그 수는 $\{1,\dots,9\}$ 의 공집합 아닌 부분집합 수와 같으므로 $|U-D| = 2^9 - 1 = \textbf{(E) }511$.