AMC 10 · 2011 · #16
학년 7 counting답을 골라 클릭하세요.
"각 대각선의 끝점이 다르다"는 말 속에는 깔끔한 모양이 숨어 있으므로, 첫 수는 도구 #1(그림 그리기)이다. 대각선만 그려 따라가 보면 오각형 별 모양이 되고, 이 별을 한 바퀴 돌면 다섯 꼭짓점을 모두 지나 처음으로 돌아온다 — 즉 크기 5짜리 하나의 닫힌 고리(원)다. 그러면 문제는 "6색으로 크기 5짜리 고리를 이웃끼리 다르게 칠하기"가 된다. 도구 #2(빠짐없이 나열하기)는 곱의 법칙으로 쉬운 사슬(열린 고리) 경우를 세고, 도구 #7(작은 문제로 쪼개기)과 도구 #16(관점 바꾸기)은 사슬이 무시한 마지막 연결을 나쁜 경우를 빼서 고쳐 준다. 이때 고리는 한 칸 작아지고 짧은 점화식이 생긴다.
대각선을 고리로 바꾸기
대각선이 하나의 고리로 다시 그려진다.
대각선 하나하나가 별의 한 연결이고 별이 하나의 고리로 닫히므로, "대각선 끝점이 다르다"는 곧 "고리 이웃이 다르다"이다.
7.SP.C.8Draw A Diagram먼저 열린 사슬로 세기
열린 사슬은 쉽게 세어진다.
사슬을 따라가면 새 꼭짓점은 왼쪽 이웃 하나만 피하므로 항상 안전한 색이 5개다.
열린 사슬을 따라가면 새 꼭짓점은 왼쪽 이웃 하나만 피하면 되므로, 언제나 같은 수의 안전한 색을 지닌다.
▸ 왜?
각 선택은 그 이웃 말고는 앞의 선택과 상관없이 이루어지므로, 개수가 곱해진다.
▸ 왜?
닿아 있는 꼭짓점만 같은 색이 금지되므로, 제약은 정확히 한 걸음 뒤까지만 미친다.
깨진 규칙 하나 찾기
규칙을 깨뜨릴 수 있는 것은 닫는 짝뿐이다.
열린 사슬은 양 끝이 부딪히는 경우까지 세므로, 부딪히는 경우만 빼면 된다.
7.SP.C.8Identify Subproblems양 끝 붙이기: 더 작은 고리
양 끝을 붙이면 더 작은 고리가 남는다.
느슨한 두 끝을 억지로 같게 하면 하나로 합쳐지면서 고리가 정확히 한 칸 작아진다.
7.SP.C.8Change Focus Count The Complement크기 4 고리까지 내려가기
그 작은 고리는 630이다.
더 작은 고리를 빼는 같은 규칙이 삼각형에서 멈추고, 삼각형 수는 단순한 곱이다.
6.EE.A.1Identify Subproblems크기 5 고리 마무리
빼면 3120, 보기 (C).
뺄셈 한 번으로 고리가 닫힌다: 자유로운 사슬에서 시작해 마지막 대각선이 금지하는 색칠을 덜어 낸다.
7.SP.C.8Identify Subproblems오각형 안에 숨은 대각선들은 하나의 다섯 꼭짓점 고리를 이룬다. 그래서 문제는 결국 "6색으로 크기 5 고리를 이웃끼리 다르게 칠하기"이다: 쉬운 열린 사슬을 세고(6 · 5⁴ = 3750), 마지막 연결을 깨는 630을 빼면 3120에 도달한다.
- 대각선을 고리로 바꾸기
- 먼저 열린 사슬로 세기
- 깨진 규칙 하나 찾기
- 양 끝 붙이기: 더 작은 고리
- 크기 4 고리까지 내려가기
- 크기 5 고리 마무리