AMC 10 · 2009 · #21

학년 7 counting

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

recursive-sequencepattern-recognitionpermutations-basic easier-related-problemcasework ↑ 선수 지식: recursive-sequencepermutations-basic

📏 긴 풀이 💡 3 개 인사이트

문제

한 줄에 앉은 열 사람이 다시 앉는데, 각자 제자리이거나 바로 옆자리다. 가능한 앉기의 개수를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

120

(D)

$2^{10}$

(E)

$2^2 3^8$

풀이 과정

전략 더 쉬운 문제로 줄이기

이 문제를 어렵게 만드는 것은 충돌 조건이고, 그것을 붙잡는 방법은 줄의 끝을 보는 것이다. 그 좌석에 닿을 수 있는 사람이 가장 적기 때문이다. 도구 #14(극단의 원리)가 그 지점을 골라 준다. 거기서 문제 전체가 정확히 두 경우로 갈라지고, 각 경우가 좌석 한 덩어리를 써 버리면서 더 짧은 줄에 대한 똑같은 문제를 남긴다 — 이것이 도구 #9(더 쉬운 문제로 줄이기)이고 풀이 전체의 엔진이다. 도구 #4(변수 도입하기)는 S_n 이라는 이름을 주어, 두 경우를 말로 설명하는 대신 하나의 식으로 쓸 수 있게 한다. 도구 #2(빠짐없이 나열하기)는 두 가지 일을 한다. 끝 좌석에 앉을 수 있는 사람의 짧은 목록을 만들고, 작은 줄을 손으로 전부 확인해 규칙이 짐작이 아니라 검증된 것이 되게 한다. 도구 #5(패턴 찾기)가 그 규칙을 좌석 열 개까지 끌고 간다. 도구 #3(가능성 지우기)는 각 오답이 어떤 실수의 기록인지 밝히고, 계산 없이 크기만으로 큰 선택지 둘을 지우며 문제를 닫는다.

1STEP 1

일대일 대응으로 모형화하기

규칙은 모두가 많아야 한 자리만 움직인다는 것이다.

|σ(k) - k| ≤ 1 for all k, σ one-to-one; 2 · 3⁸ · 2 = 2² 3⁸ = 26244

2STEP 2

끝 좌석에 누가 앉는지 묻기

끝 자리는 두 사람만 앉을 수 있다.

σ(k) = 1 → k ∈ {1, 2}

3STEP 3

제자리와 맞바꿈만 가능함을 보이기

그것을 따라가면 제자리와 맞바꿈만 일어난다.

{legal reseatings} ⟷ {ways to cut a row of 10 into pieces of length 1 and 2}

4STEP 4

경우 나눔을 규칙으로 바꾸기

그것은 줄을 짧은 조각으로 자르는 방법이다.

S_n = S_n-1 + S_n-2 (n ≥ 3), S₁ = 1, S₂ = 2

5STEP 5

규칙을 열까지 돌리기

마지막 조각으로 나누면 간단한 점화식이 나온다.

S₃ = 3, S₄ = 5, S₅ = 8, S₆ = 13, S₇ = 21, S₈ = 34, S₉ = 55, S₁₀ = 89

6STEP 6

오답들을 읽어 내기

굴려 올리면 89, 보기 (A).

S₁₀ = 89 ＜ 2⁹ = 512 ＜ 2¹⁰ = 1024 ＜ 2² 3⁸ = 26244 → (A)

정답

서로 다른 종류의 오류를 잡는 세 가지 확인. 첫째, 전부 나열이 아직 가능한 곳에서 규칙을 시험했다. 1, 2, 3, 4 명짜리 줄을 손으로 세면 1, 2, 3, 5가 나오는데 이는 S_n = S_n-1 + S_n-2의 예측과 정확히 같다. 이것이 중요한 이유는 규칙을 먼저 증명하고 표는 확인만 했기 때문이다 — 작은 경우에서 1, 2, 3, 5, 8을 읽고 계속 그럴 것이라 가정하는 것은 열 명에 대해 아무것도 증명하지 못한다. 둘째, 핵심 대응의 양방향을 모두 세웠지 편한 쪽만 세우지 않았다. 가능한 배치가 반드시 제자리와 이웃 맞바꿈으로만 이루어진다는 것은 절반일 뿐이고, 나머지 절반은 제자리와 이웃 맞바꿈을 배열한 어떤 것이든 실제로 열 좌석을 모두 채우고 아무도 한 칸을 넘게 움직이지 않는 진짜 배치라는 것이다. 두 번째 절반이 없으면 합이 과다 계수일 수 있고, 첫 번째 절반이 없으면 긴 순환 같은 배치를 빠뜨렸을 수 있다 — 끝 좌석 논증이 배제하는 것이 바로 그 가능성이다. 셋째, 크기. 이웃한 쌍이 9 개이고 어떤 두 쌍도 겹칠 수 없으므로 답은 2⁹ = 512 보다 훨씬 작고 10 보다는 훨씬 커야 하는데, 89가 그 구간에 편안하게 놓인다.

💡핵심 정리

줄 맨 끝 좌석에 대해서만 물어보자. 거기 앉은 사람은 제자리에 앉았거나 하나뿐인 이웃과 자리를 바꿨고, 어느 쪽이든 더 짧은 줄에 대한 똑같은 문제가 남는다. 그래서 가짓수는 1, 2, 3, 5, 8, … 로 자라고 열 번째가 89 다.

일대일 대응으로 모형화하기
끝 좌석에 누가 앉는지 묻기
제자리와 맞바꿈만 가능함을 보이기
경우 나눔을 규칙으로 바꾸기
규칙을 열까지 돌리기
오답들을 읽어 내기