AMC 10 · 2025 · #24

학년 8 counting

유형 Branching State Enumeration └ 세부 유형 Constrained Sequence or Path Count

combinations-basiccombinatorial-identitysystematic-enumeration convert-to-algebra ↑ 선수 지식: combinations-basic

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

문제

양의 정수에서 어떤 숫자도 두 번 넘게 쓰이지 않고, $0$ 이 하나도 없으며, 어떤 숫자도 자기보다 큰 두 숫자와 이웃하지 않을 때, 그 수를 공정한(fair) 수라고 부른다. 예를 들어 $196, 23$ 과 $12463$ 은 공정하지만, $1546, 320,$ 그리고 $34321$ 은 그렇지 않다. 공정한 양의 정수는 몇 개인가?

답을 골라 클릭하세요.

(A)

511

(B)

2584

(C)

9841

(D)

17711

(E)

19682

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 어떤 양의 정수가 '공정한(fair)' 수라는 것은, 모든 자리 숫자가 서로 다르고, $0$이 하나도 없으며, 어떤 숫자도 자기보다 큰 두 이웃 사이에 끼어 있지 않다는 뜻이다. 공정한 양의 정수는 모두 몇 개인지 구하라.

주어진 것: 모든 자리 숫자는 서로 달라야 한다 (같은 숫자가 반복되지 않는다); $0$은 쓸 수 없으므로 모든 숫자는 $\{1,2,\dots,9\}$에서 고른다; 어떤 숫자도 자기보다 엄격히 큰 두 숫자 사이에 끼면 안 된다 (안쪽 '골짜기'가 없어야 한다); 공정한 예: $196,\ 23,\ 12463$; 공정하지 않은 예: $1546,\ 320,\ 34321$; 선택지: (A) $511$, (B) $2584$, (C) $9841$, (D) $17711$, (E) $19682$

구하는 것: 공정한 양의 정수의 총 개수

이해

계획

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

보조 도구: #16 관점 바꾸기, #7 작은 문제로 쪼개기, #5 패턴 찾기

복잡한 이웃 조건 위에서 '수가 몇 개인가'를 세는 문제이므로, 어떤 숫자 집합을 쓰는지에 따라 공정한 수를 정리하는 도구 #2(빠짐없이 나열하기)가 중심이 된다. 도구 #16(관점 바꾸기)이 핵심 재해석을 제공한다 — '자기보다 큰 두 이웃 사이에 끼지 않음'은 '숫자가 하나의 봉우리까지 올라갔다가 내려온다'와 같은 말이라서, 확인해야 할 규칙이 하나의 '모양'으로 바뀐다. 도구 #7(작은 문제로 쪼개기)은 '숫자 집합 하나를 고정하고 배열 수 세기' 다음 '모든 집합에 대해 더하기'로 문제를 나눈다. 도구 #5(패턴 찾기)는 그 합이 이항정리 꼴임을 알아채어 깔끔한 $3^9$으로 접는다.

실행 — 정답: C

#16 관점 바꾸기 6.NS.C.7 단계 1

규칙을 모양으로 바꾸기

골짜기가 될 수 있는 것은 안쪽 숫자뿐이다.
끝 숫자는 이웃이 하나뿐이기 때문이다.
서로 다른 숫자들이 한 번 내려갔다가 다시 올라간다면, 그 움푹한 곳의 바닥이 자기보다 큰 두 이웃을 가진 안쪽 숫자, 즉 금지된 골짜기가 된다.
따라서 공정한 수는 중간에 꺼질 수 없다: 왼쪽에서 오른쪽으로 읽을 때 하나의 가장 큰 숫자(봉우리)까지 엄격히 커졌다가 그 뒤로 엄격히 작아져야 한다.
공정한 수는 곧 서로 다른 $0$ 아닌 숫자들의 '산봉우리' 배열이다.

$$\text{공정} \iff d_1 < d_2 < \cdots < d_{\text{봉우리}} > \cdots > d_{n-1} > d_n$$

💡 두 높은 값 사이에 낮은 값이 오는 것을 금지하는 것은 곧 숫자가 오직 올라갔다가 오직 내려온다는 뜻이다.

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

한 숫자 집합의 산봉우리 세기

$\{1,\dots,9\}$에서 서로 다른 $k$개의 숫자로 이루어진 집합 하나를 고정하자.
산봉우리에서는 고른 숫자 중 가장 큰 것이 반드시 봉우리에 와야 한다.
옆에 자기보다 큰 것이 올 수 없기 때문이다.
나머지 숫자들은 각각 오르막(봉우리 왼쪽)이나 내리막(봉우리 오른쪽) 중 한쪽으로 간다.
각 숫자의 '쪽'을 정하고 나면 정확한 위치는 자동으로 결정된다: 왼쪽은 커지는 순서, 오른쪽은 작아지는 순서여야 한다.
그러므로 산봉우리를 만드는 일은 남은 $k-1$개의 숫자에게 각각 $2$개의 쪽 중 하나를 나눠주는 것과 같다.

$2 \times 2 \times \cdots \times 2 = 2^{\,k-1}\ \text{($k$개짜리 집합마다 산봉우리 수)}$

💡 가장 큰 숫자를 꼭대기에 고정하면, 남은 숫자들은 각각 왼쪽 비탈이냐 오른쪽 비탈이냐 하는 두 갈래 스위치만 켜면 된다.

#7 작은 문제로 쪼개기 7.SP.C.8 단계 3

모든 숫자 집합에 대해 더하기

어떤 $k$개의 숫자를 쓸지 고르는 방법은 $\binom{9}{k}$가지이고, 그런 집합마다 $2^{k-1}$개의 공정한 수가 나온다.
$k$를 $1$부터 $9$까지 돌리면 가능한 모든 자릿수를 덮으므로, 총합은 $\binom{9}{k}\,2^{k-1}$을 더한 것이다.
($k=1$ 항은 $\binom{9}{1}\cdot2^{0}=9$로, 한 자리 수 아홉 개를 정확히 센다.)

$$\text{총합}=\displaystyle\sum_{k=1}^{9}\binom{9}{k}\,2^{\,k-1}$$

💡 먼저 숫자 집합을 고르고 그 집합을 산봉우리로 배열하면, 각 공정한 수를 딱 한 번씩만 센다.

#5 패턴 찾기 8.EE.A.1 단계 4

합을 접어 마무리하기

$\tfrac12$을 밖으로 빼내 지수를 $2^{k}$로 만든 뒤, 이항정리 $\sum_{k=0}^{9}\binom{9}{k}2^{k}=(1+2)^9=3^9=19683$과 비교한다.
완전한 이항 합에는 빠져 있던 $k=0$ 항 $\binom{9}{0}2^{0}=1$이 들어 있으므로, 반으로 나누기 전에 그것을 빼야 한다.
그러면 $\tfrac{3^9-1}{2}=\tfrac{19682}{2}=9841$, 즉 선택지 (C)가 된다.
$3^9-1=19682$는 함정 선택지 (E)임에 유의하라: 봉우리를 고정하기 때문에 생기는 $\tfrac12$을 잊으면 거기에 빠진다.

$$\displaystyle\sum_{k=1}^{9}\binom{9}{k}2^{k-1}=\frac{1}{2}\left(3^9-1\right)=\frac{19682}{2}=9841\ \Rightarrow\ \textbf{(C)}$$

💡 $\binom{9}{k}2^{k}$ 항들의 합은 사실 위장한 $(1+2)^9$이라서, 전체 개수가 하나의 $3$의 거듭제곱으로 접힌다.

[1] #16 6.NS.C.7 골짜기가 될 수 있는 것은 안쪽 숫자뿐이다. 끝 숫자는 이웃이 하나뿐이기 때문이다. 서로 다른 숫자들이 한 번 내려갔다가 다시 올라간다면, 그

[2] #2 7.SP.C.8 $\{1,\dots,9\}$에서 서로 다른 $k$개의 숫자로 이루어진 집합 하나를 고정하자. 산봉우리에서는 고른 숫자 중 가장 큰 것이 반드시

[3] #7 7.SP.C.8 어떤 $k$개의 숫자를 쓸지 고르는 방법은 $\binom{9}{k}$가지이고, 그런 집합마다 $2^{k-1}$개의 공정한 수가 나온다. $k$를

[4] #5 8.EE.A.1 $\tfrac12$을 밖으로 빼내 지수를 $2^{k}$로 만든 뒤, 이항정리 $\sum_{k=0}^{9}\binom{9}{k}2^{k}=(1+2

검토

합리성 확인: 총 개수는 쉬운 두 기준 사이에 있어야 한다. 한 자리 공정한 수는 $9$개이고, 아홉 숫자를 모두 쓰면 $2^{8}=256$개의 산봉우리가 나오며 그 사이의 여러 자릿수도 있으므로, 수천 단위의 총합이 타당하다 — $9841$은 들어맞지만 아주 작은 (A) $511$은 아니다. 두 큰 함정이 방법을 확인해 준다: $19682=3^9-1$(E)은 필요한 $\tfrac12$을 빼먹은 값이고, $17711$(D)은 이 개수와 무관한 피보나치 유사값이다. 봉우리 숫자가 고정되고 나머지 $k-1$개 숫자가 각각 쪽을 고른다는 사실을 지키는 값은 $9841=\tfrac{3^9-1}{2}$뿐이다.

대안 접근: 숫자 집합으로 묶는 대신, 숫자 $1,\dots,9$ 각각을 '안 씀', '오르막', '내리막'의 세 역할 중 하나에 독립적으로 배정한다. 이는 $3^9$가지 라벨링이다. 봉우리는 실제로 쓰인 숫자 중 가장 큰 것으로 자동 결정되므로, 그 가장 큰 숫자에 대한 '오르막/내리막' 선택은 중복된다. 각 유효한 라벨링을 그 쌍둥이와 짝지으면 정확히 절반만 서로 다르고, 여기서 '전부 안 씀' 라벨링 하나를 빼면 다시 $\tfrac{3^9-1}{2}=9841$이 나온다.

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

6.NS.C.7 유리수의 순서 관계와 절댓값 이해하기 (서로 다른 숫자들이 안쪽 골짜기 없이 놓이려면 하나의 봉우리까지 엄격히 커졌다가 엄격히 작아져야 함을 논증하는 데 사용.)
7.SP.C.8 정리된 목록, 표, 시뮬레이션으로 복합 사건의 확률 구하기 (곱셈 원리와 조합 원리로 집합마다 산봉우리 $2^{k-1}$개, 각 크기의 집합 $\binom{9}{k}$개를 세는 데 사용.)
8.EE.A.1 정수 지수의 성질 알고 적용하기 ($\sum \binom{9}{k}2^{k}=3^9$임을 알아보고 $3^9=19683$을 계산해 마무리하는 데 사용.)
7.NS.A.3 유리수의 사칙연산이 포함된 실생활 문제 해결하기 (마지막 계산 $\tfrac{3^9-1}{2}=\tfrac{19682}{2}=9841$을 수행하는 데 사용.)

⭐ 서로 다른 숫자들이 중간에서 꺼질 수 없다면, 그 수는 하나의 봉우리까지 올라갔다가 다시 내려와야 한다 — 그러니 가장 큰 숫자를 꼭대기에 고정하고 나머지 숫자는 각각 어느 쪽 비탈로 갈지만 고르면 된다.