AMC 10 · 2015 · #22

학년 9 counting

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

permutations-basicrecursive-sequencemodular-arithmetic easier-related-problemsystematic-enumeration ↑ 선수 지식: permutations-basicrecursive-sequence

📏 긴 풀이 💡 4 개 인사이트

문제

모두가 원 둘레에 다시 앉되 자기 자리나 양옆 자리를 가질 수 없다. 앉는 방법의 수를 세어라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #4(변수 도입하기)로 의자에 0부터 5까지 번호를 붙이고 각자의 이동을 시계 방향 이동 칸수로 재면, 말로 된 두 규칙이 "2, 3, 4"라는 짧은 목록 하나로 바뀐다. 이 세 수는 각각 -1, 0, 1과 정확히 3만큼 차이가 나므로, 도구 #15(다르게 정리하기)로 도착 의자 전체를 세 칸 되돌린다. 이 회전은 되돌릴 수 있으므로 어려운 앉기와 "제자리 또는 옆자리" 앉기가 일대일로 짝지어진다. 그다음 도구 #9(더 쉬운 문제로 줄이기)로 쉬운 규칙을 원이 아니라 일직선에서 먼저 다룬다. 일직선에서는 맨 끝 사람에게 가능한 미래가 둘뿐이고 각각이 더 짧은 줄을 되돌려 준다 — 이것이 점화식 F_n = F_n-1 + F_n-2이고, 이 풀이 전체를 떠받치는 주장이므로 인용하지 않고 직접 논증한다. 도구 #2(빠짐없이 나열하기)로 짧은 줄을 모두 적어 확인하여, 점화식이 짐작한 패턴이 아니라 검증된 값에서 출발하게 한다. 마지막으로 도구 #7(작은 문제로 쪼개기)로 한 사람의 행선지에 따라 경우를 나누어 원을 닫으면, 각 갈래가 이미 센 일직선 문제로 줄어든다.

1STEP 1

이동을 칸수로 재기

각 이동을 칸수로 잰다.

d_i = σ(i) - i (mod 6), d_i ∈ {2, 3, 4}

2STEP 2

도착 의자를 세 칸 회전시키기

회전하면 금지가 다루기 좋은 범위가 된다.

τ(i) = σ(i) - 3 (mod 6) ⟺ τ(i) - i ∈ {-1, 0, 1} (mod 6)

3STEP 3

원을 일직선으로 펴기

원을 펴면 익숙한 점화식이 나온다.

F_n = F_n-1 + F_n-2 (n ≥ 3)

4STEP 4

짧은 줄은 직접 나열해 확인

짧은 줄은 손으로 확인한다.

F₁ = 1, F₂ = 2, F₃ = 3, F₄ = 5, F₅ = 8

5STEP 5

사람 0에서 원을 닫기

원을 닫으면 경우가 셋으로 나뉜다.

8 + 6 + 6

6STEP 6

더하고 다시 회전시키기

더하면 20, 보기 (D).

8 + 6 + 6 = 20 → (D) 20

정답

회전한 규칙이 아니라 원래 규칙으로 답을 검사하자. 쉬운 배열 중 (0,1), (2,3), (4,5)가 각각 맞바꾸는 것을 잡아 도착 의자마다 3을 더하면, 사람 0은 의자 4, 사람 1은 의자 3, 사람 2는 의자 0, 사람 3은 의자 5, 사람 4는 의자 2, 사람 5는 의자 1로 간다. 도착 의자 4, 3, 0, 5, 2, 1은 모두 다르고, 각자 2, 3, 4칸 중 하나만큼 움직였을 뿐 0이나 1칸은 아니다 — 규칙에 맞는다. 크기도 그럴듯하다: 탁자 전체가 함께 움직이는 세 가지(모두 2칸, 모두 3칸, 모두 4칸)만으로도 이미 3가지이고, 각 의자에 한 사람이라는 조건을 무시한 위쪽 어림은 3⁶ = 729이므로 20은 그 사이에 자연스럽게 놓인다. 다만 선택지 14부터 24가 모두 이 그럴듯한 구간 안에 있으므로 크기만으로는 고를 수 없고, 경우 나누기를 반드시 해야 한다. 세 갈래 8, 6, 6은 사람 0의 자리로 갈라지므로 중복이 없고, 8과 6은 손으로 확인한 F₅와 F₄에 기대고 있다.

💡핵심 정리

완성된 그림을 돌려서 어려운 규칙을 쉬운 규칙으로 바꾸고, 원을 일직선으로 펴서 맨 끝 사람의 선택지를 둘로 줄이고, 작은 경우는 직접 적어 확인하라 — 그러면 개수가 한 단계씩 스스로 쌓여 20에 이른다.

이동을 칸수로 재기
도착 의자를 세 칸 회전시키기
원을 일직선으로 펴기
짧은 줄은 직접 나열해 확인
사람 0에서 원을 닫기
더하고 다시 회전시키기