AMC 10 · 2019 · #13

학년 7 counting

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

graph-coloringfactorsfundamental-counting-principlecasework identify-subproblemscaseworksystematic-enumeration ↑ 선수 지식: factorsfundamental-counting-principle

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

문제

2부터 9까지의 여덟 개 정수에 각각 빨강, 초록, 파랑 중 한 색을 칠합니다. 규칙은 하나뿐입니다. 어떤 수는 목록에 함께 있는 자기 진약수와 같은 색일 수 없습니다. 규칙을 지키는 색칠이 몇 가지인지 세세요.

답을 골라 클릭하세요.

(A)

144

(B)

216

(C)

256

(D)

384

(E)

432

풀이 과정

전략 작은 문제로 쪼개기

수 여덟 개와 색 세 가지면 아무 제한 없는 색칠이 3⁸ = 6561가지라 하나씩 확인하기엔 너무 많다. 그래서 대신 구조를 찾는다. 각 수에서 그 배수로 화살표를 그려 보면 규칙이 묶는 쌍은 몇 개뿐이고, 그림은 서로 상관하지 않는 조각들로 갈라진다. 5와 7은 완전히 자유롭고, 나머지는 2와 3에 매달린다. 제약을 공유하지 않는 조각은 따로 세서 곱하면 되므로 문제는 작은 계산 몇 개로 줄어든다. 3, 6, 9가 있는 조각에서는 개수가 '3이 2의 색을 따라가는가'라는 예/아니오 하나에 달려 있으므로 짧은 두 경우로 마무리한다.

1STEP 1

실제로 부딪히는 쌍 찾기

실제로 부딪히는 쌍만 골라냅니다.

4:{2}, 6:{2,3}, 8:{2,4}, 9:{3}, 2,3,5,7:{ }

2STEP 2

서로 무관한 조각으로 나누기

문제가 독립적인 조각으로 나뉩니다.

{5,7} 자유; 2-4-8 사슬; 3-9; 6 은 2 와 3 양쪽에 연결

3STEP 3

자유로운 수 5와 7 칠하기

5와 7은 완전히 자유입니다.

3 × 3 = 9

4STEP 4

사슬 2, 4, 8 따라가기

2에서 4, 8로 이어지는 사슬을 따라갑니다.

3 · 2 · 1 = 6

5STEP 5

3이 2를 따라가는지로 경우 나누기

6이 두 수에 모두 걸려 경우가 갈립니다.

1 · 2₃이 2와 같음 + 2 · 1₃이 다름 = 4, 4 · 2 = 8

6STEP 6

조각들을 곱해서 합치기

조각들을 곱하면 432입니다.

9 · 6 · 8 = 432

정답

432

규칙이 전혀 없으면 색칠은 3⁸ = 6561가지이고, 432는 당연히 그보다 훨씬 작다. 크기도 그럴듯하다. 부딪히는 쌍이 여섯 개면 개수를 많이 깎되 거의 0까지 깎지는 않아야 하는데, 432/6561은 약 6.6%다. 구조로도 확인된다. 432 = 9 · 6 · 8에서 9 = 3²은 제한 없는 두 수, 6은 강제되는 사슬 2, 4, 8, 8은 {3, 6, 9} 조각에서 나온다. 모든 인수가 2와 3으로만 이루어져 있어 셋과 둘로 쌓아 올린 개수와 잘 맞고, 256 = 2⁸ 같은 선택지는 인수 3이 하나도 없으니 3가지 자유 선택으로 시작하는 3색 세기에서는 나올 수 없다.

💡핵심 정리

먼저 연결을 그려 보자. 서로 닿지 않는 부분은 따로 세서 곱하면 되고, 색이 셋뿐일 때 서로 다른 두 색에 막힌 수는 선택의 여지가 없다.

실제로 부딪히는 쌍 찾기
서로 무관한 조각으로 나누기
자유로운 수 5와 7 칠하기
사슬 2, 4, 8 따라가기
3이 2를 따라가는지로 경우 나누기
조각들을 곱해서 합치기