AMC 10 · 2012 · #22

학년 7 counting

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

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

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

문제

1부터 10 까지의 수를 각각 한 번씩 어떤 순서로 늘어놓습니다. 규칙은 이렇습니다: 두 번째 수부터는, 새로 적는 모든 수가 자기보다 정확히 1 크거나 1 작은 이웃 값을 이미 앞쪽 어딘가에 두고 있어야 합니다. 이 규칙을 지키는 서로 다른 나열이 몇 가지인지 세세요.

답을 골라 클릭하세요.

(A)

$\ 120$

(B)

512

(C)

$\ 1024$

(D)

181,440

(E)

$\ 362,880$

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

풀이 과정

전략 관점 바꾸기

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

1STEP 1

작은 버전을 먼저 시험

작은 n 을 손으로 세면 n = 2는 2 가지, n = 3은 4 가지, n = 4는 8 가지 — 매번 두 배입니다.

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

나열을 이동으로 바꾸기

그래서 나열은 9 번의 좌우 이동일 뿐이고, 왼쪽이 k 번이면 시작은 k + 1로 정해져 일대일 대응입니다.

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

4STEP 4

이동 문자열 세기

9 개의 자리를 각각 L 또는 R 로 독립적으로 채우므로, 곱셈 원리에 의해 2⁹ 개입니다.

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

5STEP 5

계산하고 선택지 고르기

2⁹ = 512 이고 선택지 중 이 값뿐이라 120, 1024, 181,440, 362,880은 모두 배제, 답은 (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 로 바꿔 줍니다.

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

작은 버전을 먼저 시험

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

나열을 이동으로 바꾸기

이동 문자열 세기

계산하고 선택지 고르기

비슷한 유형 더 풀어보기