AMC 10 · 2015 · #20

학년 7 geometry-3d

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

parity-coloringspatial-visualizationsystematic-enumeration work-backwards ↑ 선수 지식: parity-coloring

📏 긴 풀이 💡 3 개 인사이트

문제

개미 에린은 정육면체의 한 꼭짓점에서 출발해 정확히 7개의 모서리를 따라 기어가며, 8개의 꼭짓점을 모두 한 번씩만 방문합니다(즉 모든 꼭짓점을 지나는 하나의 경로). 멈췄을 때 도착한 꼭짓점은 출발한 꼭짓점과 모서리로 직접 연결되어 있지 않아서, 한 번에 집(출발점)으로 돌아갈 수 없습니다. 이런 경로가 몇 개인지 세는 문제입니다.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 거꾸로 풀기

모든 꼭짓점 경로를 무작정 뒤지는 것은 불가능하므로, 먼저 문제를 **줄인 다음** 셉니다. 정육면체를 그리고(도구 #1) 꼭짓점을 입체 체스판처럼 색칠합니다(도구 #17). 모든 모서리는 어두운색↔밝은색을 뒤집으므로, 7개(홀수)의 모서리를 지나는 여정은 반드시 반대 색에서 끝납니다. '집으로 돌아갈 수 없다'는 단서(도구 #3, 가능성 지우기)는 도착점을 단 하나의 먼 꼭짓점으로 못 박습니다. 양 끝이 고정되면, 그 먼 꼭짓점에서 **거꾸로 풀어** 세는 것이 쉽습니다(도구 #11). 처음 몇 걸음만 실제 선택이고 나머지는 강제됩니다. 마지막에 빠짐없이 나열하기(도구 #2)로 합계를 교차 확인합니다. 대수는 전혀 필요 없습니다 — 색칠과 작은 곱셈이 전부입니다.

1STEP 1

정육면체를 그리고 출발점 S를 표시하세요. 각 꼭짓점에 모서리가 3개씩 모이므로, 7개 모서리로 8개 꼭짓점을 잇는 하나의 경로예요.

8개 꼭짓점, 12개 모서리, 각 꼭짓점에 3개의 모서리

2STEP 2

꼭짓점을 입체 체스판처럼 칠하면 모든 모서리가 색을 뒤집어요. 어두운 S에서 시작하면 짝수 걸음은 어두운색, 홀수 걸음은 밝은색에 도착해요.

어두운색 → 밝은색 → 어두운색 → 밝은색→…

3STEP 3

7은 홀수라 밝은 꼭짓점에서 끝나요: S의 이웃 3개 또는 먼 꼭짓점. '집으로 가는 모서리 없음'이 이웃을 지워 먼 꼭짓점 F만 남아요.

7 홀수→도착은 밝은색; S와 이웃 아님→도착=F (먼 꼭짓점)

4STEP 4

S에서 F까지 모든 꼭짓점을 지나는 경로를 거꾸로 세요: F로 들어오는 마지막 모서리는 3가지, 그 앞은 2가지, 나머지는 강제예요.

3_F로 들어오는 마지막 모서리×2_그 앞×(나머지는 모두 강제)

5STEP 5

독립인 선택을 곱해요: 3 × 2 = 6개의 경로가 먼 꼭짓점에서 끝나요. S에서 앞으로 확인해도 같아 (A)와 일치해요.

3× 2 = 6 → (A)

정답

6이 그럴듯할까요? 정육면체의 대칭성 때문에 S에서 나가는 3개의 모서리는 서로 바꿔도 똑같으므로, 경로는 똑같은 3무리로 나뉩니다. 6 = 3× 2는 출발 모서리마다 경로가 2개라는 뜻이고, 이는 손으로 직접 나열할 만큼 작아서 실제로 적어 보면 각각 정확히 2개임이 확인됩니다. 색칠 논증도 도착 꼭짓점을 빠뜨리지 않았음을 보장합니다: 홀수인 7개의 모서리는 밝은색 도착을 강제하고, S와 닿지 않는 밝은 꼭짓점은 먼 꼭짓점뿐입니다. 셈과 홀짝 논증이 모두 6, 즉 (A)에 일치합니다. 더 큰 선택지(12, 18, 24)는 출발 모서리당 경로가 2개보다 많아야 하는데, 손으로 나열한 목록이 그것을 배제합니다.

💡핵심 정리

정육면체를 체스판처럼 색칠하면, 홀수인 7걸음 여정은 반드시 먼 꼭짓점에서 끝나고, 거기로 가는 모든-꼭짓점 경로는 3× 2 = 6개뿐이에요.

비슷한 유형 더 풀어보기