AMC 10 · 2025 · #23

학년 12 counting

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

combinations-basicbinomial-theoremdigit-constraintsfundamental-counting-principle pattern-recognitionidentify-subproblems ↑ 선수 지식: combinations-basicbinomial-theorem

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

문제

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

답을 골라 클릭하세요.

(A)

511

(B)

2584

(C)

9841

(D)

17711

(E)

19682

풀이 과정

전략 빠짐없이 나열하기

'자기보다 큰 두 이웃 사이에 갇히지 않는다'는 규칙은 곧바로 세기 어려우므로, 먼저 이 규칙을 모양으로 바꾼다. 유효한 자릿수 배열이 실제로 어떻게 생겼는지를 보면, 한 봉우리까지 올라갔다가 다시 내려오는 모양이어야 함을 알 수 있고, 그러면 세는 일이 두 개의 깔끔한 작은 문제로 나뉜다. 먼저 쓸 자릿수의 집합을 고정하고 그 집합이 만드는 산 모양 배열의 수를 세면 그것이 2의 거듭제곱으로 간단히 나온다. 그다음 그 개수를 가능한 모든 자릿수 집합에 대해 더하면, 이항정리가 그 합 전체를 하나의 3의 거듭제곱으로 접어 준다. 어떤 자릿수를 쓰는지로 묶어서 세면 중복 없이 정돈된 계산이 된다.

1STEP 1

골짜기 없음은 곧 산 모양

숫자가 다 다르니 매 단계 오르거나 내린다. 골짜기(내렸다 오름)를 금하면 한 봉우리까지 올랐다 내려오는 모양만 남는다.

d₁ ＜ d₂ ＜ … ＜ d_peak ＞ … ＞ d_k

2STEP 2

한 집합에서 산 모양 세기

k개 숫자를 고정. 가장 큰 수는 봉우리, 나머지는 각자 오름·내림 쪽만 골라 위치가 정해져 집합마다 2^k-1개.

k개 자릿수 집합마다 2^k-1 개의 공정한 수

3STEP 3

모든 집합 크기에 대해 더하기

k개 집합은 C(9, k)가지이고 각각 2^k-1개이니, k = 1..9로 더하면 총수가 하나의 합이 된다.

총합 = Σ_k=1⁹ C(9, k) 2^k-1

4STEP 4

이항정리로 합 접기

$\frac{1}{2}$ 을 빼내면 이항정리로 Σ C(9,k)2^k = 3⁹ = 19683, 따라서 $\frac{3⁹ - 1}{2}$ = 9841, 보기 (C).

1/2(Σ_k=0⁹C(9, k)2^k - 1) = (3⁹ - 1)/2 = 19682/2 = 9841

정답

9841

9841은 함정 값 19682 = 3⁹ - 1의 정확히 절반인데, 이것은 타당하다. 봉우리를 가장 큰 숫자로 못 박으면 이진 선택 하나가 사라져 원래의 2^k 셈이 2로 나뉘기 때문이다. 작은 경우가 방법 전체를 확인해 준다. 숫자를 {1, 2, 3}에서만 쓰면 공식은 C(3,1)2⁰ + C(3,2)2¹ + C(3,3)2² = 3 + 6 + 4 = 13을 예측하고,

\frac{3³ - 1}{2}

\frac{26}{2}

= 13과 일치한다. 손으로 나열해도 13개다. 한 자리 1, 2, 3; 두 자리 12, 21, 13, 31, 23, 32; 세 자리 123, 132, 231, 321이며, 213은 1이 더 큰 2와 3 사이에 끼어 있어 올바르게 제외된다.

💡핵심 정리

헷갈리는 규칙을 모양으로 바꿔라. '자기보다 큰 두 숫자 사이에 갇힌 숫자가 없다'는 말은 곧 수가 하나의 봉우리까지 올라갔다가 내려온다는 뜻이고, 그러면 각 숫자의 쪽만 고르면 된다.

골짜기 없음은 곧 산 모양
한 집합에서 산 모양 세기
모든 집합 크기에 대해 더하기
이항정리로 합 접기

골짜기 없음은 곧 산 모양

한 집합에서 산 모양 세기

모든 집합 크기에 대해 더하기

이항정리로 합 접기

비슷한 유형 더 풀어보기