AMC 10 · 2025 · #24

학년 8 counting
유형 Branching State Enumeration └ 세부 유형 Constrained Sequence or Path Count
combinations-basiccombinatorial-identitysystematic-enumeration convert-to-algebra ↑ 선수 지식: combinations-basic
📏 중간 풀이 💡 3 개 인사이트
문제
어떤 양의 정수가 '공정한(fair)' 수라는 것은, 모든 자리 숫자가 서로 다르고, 0이 하나도 없으며, 어떤 숫자도 자기보다 큰 두 이웃 사이에 끼어 있지 않다는 뜻이다. 공정한 양의 정수는 모두 몇 개인지 구하라.

답을 골라 클릭하세요.

(A)
511
(B)
2584
(C)
9841
(D)
17711
(E)
19682

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

풀이 과정
전략 빠짐없이 나열하기

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

1STEP 1

규칙을 모양으로 바꾸기

골짜기는 안쪽 자리에만 생기므로, 공정한 수는 하나의 봉우리까지 올랐다가 내려오는 산 모양이다.

공정 ⇔ d₁ ＜ d₂ ＜ … ＜ d_봉우리 ＞ … ＞ d_n-1 ＞ d_n
2STEP 2

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

k개를 고정하면 가장 큰 것은 봉우리에 강제되고 나머지 k-1개는 좌우만 고르므로 2^(k-1)개다.

2 × 2 × … × 2 = 2^ k-1 (k개짜리 집합마다 산봉우리 수)
3STEP 3

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

k개를 고르는 방법이 C(9,k)가지이므로, k=1부터 9까지 C(9,k)·2^(k-1)을 모두 더한다.

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

합을 접어 마무리하기

이항정리로 합을 접으면 3⁹−1의 절반이 되어 9841, 즉 (C)이고 19682는 함정 (E)이다.

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

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

  • 규칙을 모양으로 바꾸기
  • 한 숫자 집합의 산봉우리 세기
  • 모든 숫자 집합에 대해 더하기
  • 합을 접어 마무리하기

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.