AMC 10 · 2011 · #22

학년 7 counting

유형 Branching State Enumeration └ 세부 유형 Ordered Placement Count

graph-coloringrecursive-sequencepermutations-basic complementary-countingcasework ↑ 선수 지식: permutations-basic

📏 긴 풀이 💡 3 개 인사이트

문제

볼록오각형 $ABCDE$ 의 각 꼭짓점에 색을 하나씩 칠하려고 한다. 고를 수 있는 색은 $6$ 가지이고, 각 대각선의 양 끝 꼭짓점은 서로 다른 색이어야 한다. 가능한 서로 다른 색칠 방법은 몇 가지인가?

답을 골라 클릭하세요.

(A)

2520

(B)

2880

(C)

3120

(D)

3250

(E)

3750

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 볼록 오각형 $ABCDE$의 다섯 꼭짓점을 각각 $6$가지 색 중 하나로 칠한다. 규칙은 단 하나: 모든 대각선의 두 끝점은 서로 다른 색이어야 한다. 다섯 변에는 아무 제약이 없다. 규칙을 지키는 색칠 방법의 수를 구하라.

주어진 것: 오각형 $ABCDE$의 꼭짓점은 $5$개; 색은 $6$가지, 한 색을 여러 꼭짓점에 다시 써도 된다; 각 대각선의 두 끝점은 서로 다른 색이어야 한다; 다섯 대각선은 $AC$, $CE$, $EB$, $BD$, $DA$; 변($AB, BC, CD, DE, EA$)에는 색 제약이 없다; 선택지: (A) $2520$, (B) $2880$, (C) $3120$, (D) $3250$, (E) $3750$

구하는 것: 다섯 꼭짓점을 규칙대로 칠하는 방법의 수

이해

계획

주요 도구: #1 그림 그리기

보조 도구: #7 작은 문제로 쪼개기, #2 빠짐없이 나열하기, #16 관점 바꾸기

"각 대각선의 끝점이 다르다"는 말 속에는 깔끔한 모양이 숨어 있으므로, 첫 수는 도구 #1(그림 그리기)이다. 대각선만 그려 따라가 보면 오각형 별 모양이 되고, 이 별을 한 바퀴 돌면 다섯 꼭짓점을 모두 지나 처음으로 돌아온다 — 즉 크기 $5$짜리 하나의 닫힌 고리(원)다. 그러면 문제는 "$6$색으로 크기 $5$짜리 고리를 이웃끼리 다르게 칠하기"가 된다. 도구 #2(빠짐없이 나열하기)는 곱의 법칙으로 쉬운 사슬(열린 고리) 경우를 세고, 도구 #7(작은 문제로 쪼개기)과 도구 #16(관점 바꾸기)은 사슬이 무시한 마지막 연결을 나쁜 경우를 빼서 고쳐 준다. 이때 고리는 한 칸 작아지고 짧은 점화식이 생긴다.

실행 — 정답: C

#1 그림 그리기 7.SP.C.8 단계 1

대각선을 고리로 바꾸기

대각선만 그린다: $AC$, $CE$, $EB$, $BD$, $DA$.
순서 $A \to C \to E \to B \to D \to A$로 따라가면, 이 한 바퀴가 다섯 대각선을 모두 쓰고 각 꼭짓점을 정확히 한 번씩 지나 $A$로 돌아온다 — 별 모양은 크기 $5$짜리 하나의 닫힌 고리다.
변에는 규칙이 없으므로, 문제는 "$6$색으로 (순서 $A, C, E, B, D$의) 크기 $5$ 고리를 이웃끼리 다르게 칠하기"가 된다.

$$\text{고리 순서: } A - C - E - B - D - (A)$$

💡 대각선 하나하나가 별의 한 연결이고 별이 하나의 고리로 닫히므로, "대각선 끝점이 다르다"는 곧 "고리 이웃이 다르다"이다.

#2 빠짐없이 나열하기 7.SP.C.8 단계 2

먼저 열린 사슬로 세기

고리를 마지막 연결 $D - A$에서 잠깐 끊어 열린 사슬 $A - C - E - B - D$로 둔다.
왼쪽부터 칠하면 첫 꼭짓점 $A$는 $6$색 어느 것이든 되고, 이후 꼭짓점은 바로 앞 색 하나만 피하면 되므로 각각 $5$가지다.
곱의 법칙으로 사슬의 색칠은 $6 \cdot 5 \cdot 5 \cdot 5 \cdot 5$가지다.

$$6 \cdot 5^4 = 3750$$

💡 사슬을 따라가면 새 꼭짓점은 왼쪽 이웃 하나만 피하므로 항상 안전한 색이 $5$개다.

#7 작은 문제로 쪼개기 7.SP.C.8 단계 3

깨진 규칙 하나 찾기

사슬로 센 $3750$은 대각선 하나, 즉 닫는 연결 $D - A$를 무시했다.
이 중 일부는 $A$와 $D$를 같은 색으로 칠해 규칙을 어긴다.
따라서 진짜 고리 수는 $3750$에서 첫 꼭짓점 $A$와 마지막 꼭짓점 $D$가 같은 색인 사슬 색칠의 수를 뺀 값이다.

$$(\text{크기 }5\text{ 고리}) = 3750 - (A = D\text{인 사슬})$$

💡 열린 사슬은 양 끝이 부딪히는 경우까지 세므로, 부딪히는 경우만 빼면 된다.

#16 관점 바꾸기 7.SP.C.8 단계 4

양 끝 붙이기: 더 작은 고리

$A$와 $D$가 같은 색인 나쁜 사슬을 센다.
두 끝이 같아야 한다면 그 둘을 하나의 꼭짓점으로 합친다.
그러면 사슬의 연결 $A-C$, $C-E$, $E-B$, $B-D$가 크기 $4$짜리 고리 $A - C - E - B - (A)$로 닫히고, 각 연결은 여전히 다른 색을 요구한다.
따라서 나쁜 경우의 수는 크기 $4$ 고리의 유효 색칠 수와 같다.
이는 한 칸 작아진 똑같은 문제이며, 규칙 $R_n = 6 \cdot 5^{\,n-1} - R_{n-1}$을 준다.

$$R_5 = 6 \cdot 5^4 - R_4$$

💡 느슨한 두 끝을 억지로 같게 하면 하나로 합쳐지면서 고리가 정확히 한 칸 작아진다.

#7 작은 문제로 쪼개기 6.EE.A.1 단계 5

크기 4 고리까지 내려가기

규칙을 시작값과 함께 쓴다.
크기 $3$ 고리는 세 꼭짓점이 서로 모두 이웃인 삼각형이므로 $R_3 = 6 \cdot 5 \cdot 4 = 120$이다.
그러면 크기 $4$ 고리는 $R_4 = 6 \cdot 5^3 - R_3 = 750 - 120 = 630$이다.
이 $630$이 앞 단계의 나쁜 사슬 수다.

$$R_4 = 6 \cdot 5^3 - 120 = 750 - 120 = 630$$

💡 더 작은 고리를 빼는 같은 규칙이 삼각형에서 멈추고, 삼각형 수는 단순한 곱이다.

#7 작은 문제로 쪼개기 7.SP.C.8 단계 6

크기 5 고리 마무리

합치면, 크기 $5$ 고리 수는 사슬 수에서 나쁜(양 끝이 같은) 수를 뺀 $R_5 = 3750 - 630 = 3120$이다.
이것이 오각형 $ABCDE$의 유효 색칠 수이므로 답은 $(C)$이다.

$$R_5 = 3750 - 630 = 3120 \;\Rightarrow\; \textbf{(C)}$$

💡 뺄셈 한 번으로 고리가 닫힌다: 자유로운 사슬에서 시작해 마지막 대각선이 금지하는 색칠을 덜어 낸다.

[1] #1 7.SP.C.8 대각선만 그린다: $AC$, $CE$, $EB$, $BD$, $DA$. 순서 $A \to C \to E \to B \to D \to A$로 따라

[2] #2 7.SP.C.8 고리를 마지막 연결 $D - A$에서 잠깐 끊어 열린 사슬 $A - C - E - B - D$로 둔다. 왼쪽부터 칠하면 첫 꼭짓점 $A$는 $6

[3] #7 7.SP.C.8 사슬로 센 $3750$은 대각선 하나, 즉 닫는 연결 $D - A$를 무시했다. 이 중 일부는 $A$와 $D$를 같은 색으로 칠해 규칙을 어긴다

[4] #16 7.SP.C.8 $A$와 $D$가 같은 색인 나쁜 사슬을 센다. 두 끝이 같아야 한다면 그 둘을 하나의 꼭짓점으로 합친다. 그러면 사슬의 연결 $A-C$, $C

[5] #7 6.EE.A.1 규칙을 시작값과 함께 쓴다. 크기 $3$ 고리는 세 꼭짓점이 서로 모두 이웃인 삼각형이므로 $R_3 = 6 \cdot 5 \cdot 4 = 12

[6] #7 7.SP.C.8 합치면, 크기 $5$ 고리 수는 사슬 수에서 나쁜(양 끝이 같은) 수를 뺀 $R_5 = 3750 - 630 = 3120$이다. 이것이 오각형 $

검토

합리성 확인: 열린 사슬 수 $3750$(선택지 E)은 깔끔한 상한이다. 다섯 대각선 규칙 중 넷을 지키고 닫는 하나만 무시하기 때문이다. 진짜 답은 이보다 조금 작아야 하며, $3120$은 $3750$보다 딱 $630$ 작아 타당하다. 선택지 E는 마지막 대각선을 잊은 사람을 위한 함정이다. 고리 색칠 공식 $(k-1)^n + (-1)^n (k-1)$에 $n = 5$, $k = 6$을 넣어 독립 확인하면 $5^5 - 5 = 3125 - 5 = 3120$. 두 경로가 일치하여 $(C)$를 확인한다.

대안 접근: 도구 #7(작은 문제로 쪼개기)로 닫는 대각선 $DA$에 대한 직접 경우 나누기: 사슬 $A-C-E-B-D$에서 $D$가 $A$와 같은지 다른지로 나누고, $D$를 칠하는 $5$가지($B$를 피함) 중 정확히 하나가 $A$와 겹칠 수 있음을 이용한다. 이 짝을 사슬 끝까지 추적하면 다시 $3120$이 나온다. 더 매끄러운 방법은 대각선 그래프가 $5$-순환 $C_5$임을 알아채고, 그 채색 다항식 $(k-1)^5 + (k-1)(-1)^5 = 5^5 - 5 = 3120$을 $k = 6$에서 쓰는 것이다.

사용된 CCSS 표준 (최저 학년 7)

7.SP.C.8 Find probabilities of compound events using organized lists, tables, and simulation (대각선을 고리로 구조화하고, 사슬에 곱의 법칙($6 \cdot 5^4$)을 적용하며, 여집합(양 끝이 같은 색칠)을 빼서 닫는 대각선을 바로잡는 데 사용.)
6.EE.A.1 Write and evaluate numerical expressions involving whole-number exponents (점화식 속 $6 \cdot 5^4 = 3750$, $6 \cdot 5^3 = 750$에서 $5$의 거듭제곱을 계산하는 데 사용.)

⭐ 오각형 안에 숨은 대각선들은 하나의 다섯 꼭짓점 고리를 이룬다. 그래서 문제는 결국 "$6$색으로 크기 5 고리를 이웃끼리 다르게 칠하기"이다: 쉬운 열린 사슬을 세고($6 \cdot 5^4 = 3750$), 마지막 연결을 깨는 $630$을 빼면 $3120$에 도달한다.