AMC 10 · 2021 · #16

학년 4 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Logic-Deduction / Elimination

digit-constraintsdivisibility-rulesdigit-sumsystematic-enumeration systematic-enumerationcasework ↑ 선수 지식: divisibility-rulesdigit-sum

📏 중간 풀이 💡 3 개 인사이트

📘 쉬운 버전 보기 →

문제

Call a positive integer an uphill integer if every digit is strictly greater than the previous digit. For example, $1357, 89,$ and $5$ are all uphill integers, but $32, 1240,$ and $466$ are not. How many uphill integers are divisible by $15$ ?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: "오름 정수"는 왼쪽에서 오른쪽으로 자릿수가 엄격하게 커지는 양의 정수입니다 ($1357$, $89$ 처럼). $15$ 로 나누어떨어지는 오름 정수가 몇 개인지 세어보세요.

주어진 것: 오름 정수는 자릿수가 왼쪽에서 오른쪽으로 엄격하게 증가; 예: $1357, 89, 5$ 는 오름 정수, $32, 1240, 466$ 은 아님; $15$ 로 나누어떨어지는 것만 찾기; 선택지: (A) $4$, (B) $5$, (C) $6$, (D) $7$, (E) $8$

구하는 것: $15$ 로 나누어떨어지는 오름 정수의 개수

이해

계획

주요 도구: #2 빠짐없이 나열하기

보조 도구: #9 더 쉬운 문제로 줄이기, #5 패턴 찾기

도구 #9 (더 쉬운 문제) — $15$ 의 배수 판정을 두 갈래로 쪼갭니다. "$5$ 의 배수" 조건에서 끝자리는 $0$ 또는 $5$ 인데, 오름 정수에서 끝이 $0$ 이면 그 앞 자리는 음수가 되어야 해서 불가능. 그러니 끝자리는 반드시 $5$ 이고, 나머지 자리는 모두 $\{1, 2, 3, 4\}$ 에서 골라옵니다. 후보 풀이 "모든 오름 정수" 에서 "$\{1,2,3,4\}$ 의 부분집합 뒤에 $5$" 로 줄어듭니다. 도구 #2 (체계적 나열) 로 크기 순으로 모든 부분집합을 나열하고, 도구 #5 (패턴 — $3$ 의 배수 판정) 로 자릿수 합이 $3$ 의 배수인 것만 남깁니다. 남은 개수가 답.

실행 — 정답: C

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

$15$ 의 배수 판정을 분해합니다.
$15 = 3 \times 5$ 이고 $\gcd(3, 5) = 1$ 이므로 $15$ 의 배수 $\Leftrightarrow$ $3$ 의 배수이면서 $5$ 의 배수.
$5$ 의 배수는 끝자리가 $0$ 또는 $5$.
오름 정수가 $0$ 으로 끝나려면 앞 자리들이 $0$ 보다 작아야 하는데 불가능.
따라서 끝자리는 $5$ 로 고정.

$15 = 3 \times 5,\ \gcd(3,5)=1$; 끝자리 $= 5$

💡 어려운 "$15$ 의 배수" 조건을 두 개 쉬운 조건으로 쪼개고, 그중 더 쉬운 "$5$ 의 배수" 로 끝자리를 잠급니다.

#2 빠짐없이 나열하기 4.OA.B.4 단계 2

자릿수가 엄격하게 증가하면서 끝이 $5$ 이므로 나머지 자리는 $\{1, 2, 3, 4\}$ 에서만 오고 증가 순서로 배열됩니다.
그래서 질문은 "$\{1, 2, 3, 4\}$ 의 부분집합 중 그 합에 $5$ 를 더한 값이 $3$ 의 배수인 것은 몇 개?" 로 바뀝니다.
순서 규칙은 부분집합의 크기 순.

$T \subseteq \{1,2,3,4\}$ 골라 $T$ 의 자릿수를 증가 순으로 쓰고 끝에 $5$ 붙임

💡 $5$ 까지 올라가는 자릿수를 고른다 — 순서는 "오름" 이 강제하니 집합만 고르면 끝.

#5 패턴 찾기 4.OA.B.4 단계 3

크기 $0$ ("$5$" 만): 자릿수 합 $= 5$.
$3$ 의 배수 아님.
통과.

$$5 \to 5\not\equiv 0\pmod{3}$$

💡 $5$ 혼자는 $5$ 의 배수이지만 $3$ 의 배수가 아니라 $15$ 의 배수가 아님.

#2 빠짐없이 나열하기 4.OA.B.4 단계 4

크기 $1$ ($5$ 앞에 한 자리): $15, 25, 35, 45$.
자릿수 합: $6, 7, 8, 9$.
$3$ 의 배수는 $6, 9$.
그래서 $\textbf{15}$, $\textbf{45}$ 통과 — $2$ 개.

$$15{:}\,1{+}5{=}6\checkmark,\ 25{:}\,7,\ 35{:}\,8,\ 45{:}\,4{+}5{=}9\checkmark$$

💡 $5$ 외 한 자리만 더 골라 자릿수 합을 확인.

#2 빠짐없이 나열하기 4.OA.B.4 단계 5

크기 $2$ ($\{1,2,3,4\}$ 에서 두 개): $C(4, 2) = 6$ 개.
$125, 135, 145, 235, 245, 345$.
자릿수 합: $8, 9, 10, 10, 11, 12$.
$3$ 의 배수는 $9, 12$.
그래서 $\textbf{135}$, $\textbf{345}$ 통과 — $2$ 개.

$135{:}\,9\checkmark,\ 345{:}\,12\checkmark$ (나머지는 $\div 3$ 실패)

💡 $\{1,2,3,4\}$ 에서 두 개씩 골라 차례로 적고, 끝에 $5$ 붙여 합을 확인.

#2 빠짐없이 나열하기 4.OA.B.4 단계 6

크기 $3$ (세 개): $C(4, 3) = 4$ 개.
$1235, 1245, 1345, 2345$.
자릿수 합: $11, 12, 13, 14$.
$3$ 의 배수는 $12$ 만.
그래서 $\textbf{1245}$ 통과 — $1$ 개.

$$1245{:}\,1{+}2{+}4{+}5{=}12\checkmark$$

💡 같은 절차 — 나열, 자릿수 합, $\div 3$ 확인.

#2 빠짐없이 나열하기 4.OA.B.4 단계 7

크기 $4$ ($\{1, 2, 3, 4\}$ 전체): $\textbf{12345}$.
자릿수 합 $= 1+2+3+4+5 = 15$, $3$ 의 배수.
통과 — $1$ 개.
크기 $\ge 5$ 는 불가능 ($5$ 앞에 쓸 수 있는 숫자가 $4$ 개뿐).
합계: $2 + 2 + 1 + 1 = 6$.
따라서 답은 $(C)\ 6$.

$12345{:}\,15\checkmark$; 합 $=2+2+1+1=\textbf{6}\;\Rightarrow\;(C)$

💡 각 크기별 개수를 더하면 — $15$ 의 배수인 오름 정수는 모두 $6$ 개.

[1] #9 4.OA.B.4 $15$ 의 배수 판정을 분해합니다. $15 = 3 \times 5$ 이고 $\gcd(3, 5) = 1$ 이므로 $15$ 의 배수 $\Leftr

[2] #2 4.OA.B.4 자릿수가 엄격하게 증가하면서 끝이 $5$ 이므로 나머지 자리는 $\{1, 2, 3, 4\}$ 에서만 오고 증가 순서로 배열됩니다. 그래서 질문은

[3] #5 4.OA.B.4 크기 $0$ ("$5$" 만): 자릿수 합 $= 5$. $3$ 의 배수 아님. 통과.

[4] #2 4.OA.B.4 크기 $1$ ($5$ 앞에 한 자리): $15, 25, 35, 45$. 자릿수 합: $6, 7, 8, 9$. $3$ 의 배수는 $6, 9$. 그

[5] #2 4.OA.B.4 크기 $2$ ($\{1,2,3,4\}$ 에서 두 개): $C(4, 2) = 6$ 개. $125, 135, 145, 235, 245, 345$.

[6] #2 4.OA.B.4 크기 $3$ (세 개): $C(4, 3) = 4$ 개. $1235, 1245, 1345, 2345$. 자릿수 합: $11, 12, 13, 14$

[7] #2 4.OA.B.4 크기 $4$ ($\{1, 2, 3, 4\}$ 전체): $\textbf{12345}$. 자릿수 합 $= 1+2+3+4+5 = 15$, $3$ 의

검토

합리성 확인: 확인: $15, 45, 135, 345, 1245, 12345$ 모두 끝이 $5$ ($5$ 의 배수) 이고 자릿수 합 $6, 9, 9, 12, 12, 15$ 가 모두 $3$ 의 배수 — 진짜 $15$ 의 배수. 빠뜨린 경우는 없음: $\{1,2,3,4\}$ 의 부분집합은 $2^4 = 16$ 개이고 우리는 그 $16$ 개 각각의 자릿수 합을 $3$ 으로 나누어 확인. 통과한 $6$ 개가 정답 (C) 와 일치.

대안 접근: 도구 #5 (패턴) — $5 \equiv 2 \pmod 3$ 이므로 추가 자릿수들의 합이 $\equiv 1 \pmod 3$ 이어야 함. $\{1, 2, 3, 4\}$ 를 $3$ 으로 나눈 나머지로 분류하면 $\{3\}, \{1, 4\}, \{2\}$. 각 부분집합의 잔여를 더해 $\equiv 1$ 인 부분집합을 세면 더 깔끔하게 $6$ 이 나옵니다.

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

4.OA.B.4 인수 쌍과 배수, 소수·합성수 판별 ($15 = 3 \times 5$ 인 소인수 분해로 "$15$ 의 배수" 를 "$3$ 의 배수 AND $5$ 의 배수" 로 쪼개고, $3$ 의 자릿수 합 규칙과 $5$ 의 끝자리 규칙을 후보마다 적용.)

⭐ 이 AMC 10 문제는 사실 4학년 때 배운 배수 판정법과 꼼꼼한 나열만 알면 풀 수 있어요! $15$ 의 배수 $=$ $3$ 의 배수이면서 $5$ 의 배수. 그러니 끝자리는 $5$, 나머지는 $\{1,2,3,4\}$ 에서 고르고 자릿수 합이 $3$ 의 배수면 끝 — 모든 부분집합을 나열하면 정확히 $6$ 개가 남습니다.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: C

검토

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

비슷한 유형 더 풀어보기