AMC 8 · 2025 · #21

학년 6 logiccounting

유형 Constraint Graph Coloring └ 세부 유형 Degree-Driven Extreme Pinning

logical-deductionsystematic-enumerationinterval-arithmetic caseworklogical-deductionsystematic-enumeration ↑ 선수 지식: logical-deductionsystematic-enumeration

📏 긴 풀이 💡 4 개 인사이트 📊 도형

문제

A 부터 G 까지의 7 개 교실에 1 학년부터 7 학년까지를 한 학년씩 배정하려고 합니다. 그림에 표시된 산책로로 직접 이어진 두 교실은 학년 차이가 반드시 2 이상이어야 합니다. 이때 g(C) + g(E) + g(F) 의 값을 구하세요.

답을 골라 클릭하세요.

(A)

~12

(B)

~13

(C)

~14

(D)

~15

(E)

~16

AMC 8 2025 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이 과정

전략 가능성 지우기

그림이 이미 주어져 있으니 도구 #1 은 "산책로를 하나씩 빠짐없이 읽어 목록으로 적기" 가 됩니다. 도구 #15 (다르게 정리하기) 로 이 산책로 목록을 "각 교실의 이웃 수(차수)" 표로 다시 정리하면, C 와 F 가 차수 5 로 가장 제약이 많다는 사실이 한눈에 보입니다. 본격적인 풀이는 도구 #3 (가능성 지우기) 가 끌고 갑니다 — 차수 5 인 교실에는 학년 1 또는 7 만 들어갈 수 있다는 점을 "이웃이 쓸 수 있는 학년이 5 개 남아야 한다" 는 계산으로 좁히고, 이어서 같은 가능성 지우기 방식으로 g(D), g(G), g(E) 가 순서대로 강제됩니다.

1STEP 1

그림을 보고 연결을 모두 적으면 산책로 12 개가 있습니다.

산책로 12 개

2STEP 2

산책로를 교실별 이웃 수로 다시 세면 C 와 F만 차수 5 로 가장 까다롭습니다.

deg(A)=4, deg(B)=3, deg(C)=5, deg(D)=2, deg(E)=3, deg(F)=5, deg(G)=2

3STEP 3

차수 5 인 교실은 이웃에게 5 개 학년이 필요한데, k = 1 또는 k = 7일 때만 그만큼 남습니다.

k=1 :{3,4,5,6,7} (5 ✓) | k=2 :{4,5,6,7} (4) | k=3 :{1,5,6,7} (4) | … | k=7 :{1,2,3,4,5} (5 ✓)

4STEP 4

F 도 마찬가지이므로 {g(C), g(F)} = {1, 7} 이고, 대칭이라 g(C) = 1, g(F) = 7 로 둡니다.

{g(C), g(F)} = {1, 7}

5STEP 5

6 은 F 의 이웃을 피해 D 로, 2 는 C 의 이웃을 피해 G 로 가서 g(D) = 6, g(G) = 2 입니다.

g(D) = 6, g(G) = 2

6STEP 6

E 는 1, 6, 7 과 이어져 g(E) ∈ {3, 4} 이고, 3 이면 A·B 가 4, 5 라 A-B 위반이므로 g(E) = 4.

g(E) = 4

7STEP 7

요구된 세 교실의 학년을 더합니다.

g(C) + g(E) + g(F) = 1 + 4 + 7 = 12 → (A)

정답

~12

완성된 배정 g(C)=1, g(G)=2, g(B)=3, g(E)=4, g(A)=5, g(D)=6, g(F)=7 을 12 개의 산책로에 대입해 보면, 모든 연결된 쌍의 차이가 2 이상 (가장 빠듯한 곳이 A-B 의 |5-3|=2) 으로 조건을 만족합니다. 합 1 + 4 + 7 = 12 는 선택지 (A) 와 일치합니다. 반대 경우 g(C)=7, g(F)=1 도 대칭적으로 풀려 같은 합 7+4+1=12 가 나오므로 답이 유일하게 결정됩니다.

💡핵심 정리

이 AMC 8 문제는 사실 6학년 때 배운 "두 학년의 차이가 2 이상" 이라는 절댓값 추론만 알면 풀 수 있어요!

비슷한 유형 더 풀어보기