AMC 10 · 2012 · #18

학년 7 counting

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

pattern-recognitioncombinations-basic easier-related-problem ↑ 선수 지식: pattern-recognition

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

문제

첫 수 뒤에 쓰는 모든 수는 앞에 이미 이웃한 값이 있어야 한다. 나열의 수를 세어라.

답을 골라 클릭하세요.

(A)

120

(B)

512

(C)

1024

(D)

181,440

(E)

362,880

풀이 과정

전략 관점 바꾸기

10 길이의 나열을 정면으로 세는 것은 무리이므로, 무엇을 셀지 관점을 바꿉니다(도구 #16). 먼저 문제를 줄여 보면(도구 #9) n = 2, 3, 4 에서 개수가 2, 4, 8로 나와 2^ n-1을 암시합니다. 수직선 그림(도구 #1)으로 핵심 구조가 드러납니다 — 지금까지 적은 값들은 항상 끊김 없는 한 덩어리를 이루며 그 왼쪽 끝이나 오른쪽 끝에서만 자랄 수 있습니다. 그러면 각 나열을 9 번의 왼쪽/오른쪽 이동 문자열로 다시 쓸 수 있고, 덩어리가 [1, 10]으로 끝나야 한다는 조건이 시작 수를 강제로 정해 줍니다. 그 문자열들을 세는 것은 곱셈 원리를 쓰는 단순한 나열(도구 #2)이라 2⁹이 되고, 그 값을 선택지에 맞추면(도구 #3) 답이 나옵니다.

1STEP 1

작은 버전을 먼저 시험

작은 경우가 매번 두 배임을 시사한다.

f(2) = 2, f(3) = 4, f(4) = 8 → f(n) = 2^ n-1 ?

2STEP 2

수들을 하나의 선분으로 보기

쓴 수들은 언제나 하나의 구간을 이룬다.

[L, R] ⟶ [L-1, R] 또는 [L, R+1]

3STEP 3

나열을 이동으로 바꾸기

따라서 새 수마다 왼쪽이냐 오른쪽이냐의 선택이다.

유효한 나열 ⟷ {L, R}의 9 번 이동 문자열, 시작 = (#L) + 1

4STEP 4

이동 문자열 세기

그런 선택이 연달아 아홉 번이다.

2 × 2 × … × 2₉ 개 = 2⁹

5STEP 5

계산하고 선택지 고르기

그러면 512, 보기 (B).

2⁹ = 512 → (B)

정답

512

작은 경우들이 들어맞습니다: 2²⁻¹ = 2, 2³⁻¹ = 4, 2⁴⁻¹ = 8이 손 계산과 일치했으니 2¹⁰⁻¹ = 512도 같은 규칙에 맞습니다. 두 번째 확인: 강제된 시작 값에 대해 합하면 Σ_k=0⁹ C(9, k) = 2⁹ (9 번 이동 중 왼쪽인 것을 고르는 방법), 역시 같은 512. 오답은 함정입니다: 1024 = 2¹⁰은 시작을 별도의 자유 선택으로 취급해 과다 계산한 것이고, 362,880 = 9! 과 181,440 = 9!/2는 이웃 규칙이 허용하는 것보다 훨씬 많은 자유를 상상한 값입니다.

💡핵심 정리

규칙이 덩어리의 왼쪽 끝이나 오른쪽 끝에만 덧붙이게 한다면, 수는 잊고 왼쪽/오른쪽 선택만 세세요 — 여기서는 그것이 겁나는 순서 문제를 2⁹ = 512로 바꿔 줍니다.

작은 버전을 먼저 시험
수들을 하나의 선분으로 보기
나열을 이동으로 바꾸기
이동 문자열 세기
계산하고 선택지 고르기

작은 버전을 먼저 시험

수들을 하나의 선분으로 보기

나열을 이동으로 바꾸기

이동 문자열 세기

계산하고 선택지 고르기

비슷한 유형 더 풀어보기