AMC 10 · 2011 · #22
학년 7 counting답을 골라 클릭하세요.
AMC 10 2011 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
"각 대각선의 끝점이 다르다"는 말 속에는 깔끔한 모양이 숨어 있으므로, 첫 수는 도구 #1(그림 그리기)이다. 대각선만 그려 따라가 보면 오각형 별 모양이 되고, 이 별을 한 바퀴 돌면 다섯 꼭짓점을 모두 지나 처음으로 돌아온다 — 즉 크기 5짜리 하나의 닫힌 고리(원)다. 그러면 문제는 "6색으로 크기 5짜리 고리를 이웃끼리 다르게 칠하기"가 된다. 도구 #2(빠짐없이 나열하기)는 곱의 법칙으로 쉬운 사슬(열린 고리) 경우를 세고, 도구 #7(작은 문제로 쪼개기)과 도구 #16(관점 바꾸기)은 사슬이 무시한 마지막 연결을 나쁜 경우를 빼서 고쳐 준다. 이때 고리는 한 칸 작아지고 짧은 점화식이 생긴다.
대각선을 고리로 바꾸기
대각선 AC, CE, EB, BD, DA만 따라가면 A → C → E → B → D → A로 닫히는 고리 하나다.
대각선 하나하나가 별의 한 연결이고 별이 하나의 고리로 닫히므로, "대각선 끝점이 다르다"는 곧 "고리 이웃이 다르다"이다.
7.SP.C.8Draw A Diagram먼저 열린 사슬로 세기
D - A를 끊어 열린 사슬 A - C - E - B - D를 왼쪽부터 칠하면 6 · 5 · 5 · 5 · 5 = 3750가지.
사슬을 따라가면 새 꼭짓점은 왼쪽 이웃 하나만 피하므로 항상 안전한 색이 5개다.
7.SP.C.8Make A Systematic List깨진 규칙 하나 찾기
이 사슬 수는 닫는 대각선 D - A를 무시했으니, A와 D가 같은 색인 경우를 빼야 한다.
열린 사슬은 양 끝이 부딪히는 경우까지 세므로, 부딪히는 경우만 빼면 된다.
열린 사슬은 양 끝이 부딪히는 것까지 허락해 지나치게 세므로, 그것을 빼야 한다.
▸ 왜?
각 고리는 멀리 있는 고리와 상관없이 칠해지므로, 사슬의 개수는 평범한 곱이다.
▸ 왜?
전부 센 뒤 규칙을 어긴 것을 덜어 내는 것이 셈을 정직하게 지킨다.
양 끝 붙이기: 더 작은 고리
A와 D를 같게 하면 한 점으로 합쳐져 사슬이 크기 4 고리로 닫히니, 나쁜 수는 곧 4 고리 수다.
느슨한 두 끝을 억지로 같게 하면 하나로 합쳐지면서 고리가 정확히 한 칸 작아진다.
7.SP.C.8Change Focus Count The Complement크기 4 고리까지 내려가기
시작값은 삼각형인 크기 3 고리로 6 · 5 · 4 = 120. 그러면 크기 4 고리는 750 - 120 = 630.
더 작은 고리를 빼는 같은 규칙이 삼각형에서 멈추고, 삼각형 수는 단순한 곱이다.
6.EE.A.1Identify Subproblems크기 5 고리 마무리
사슬에서 나쁜 경우를 빼면 3750 - 630 = 3120, 오각형 ABCDE의 답은 (C).
뺄셈 한 번으로 고리가 닫힌다: 자유로운 사슬에서 시작해 마지막 대각선이 금지하는 색칠을 덜어 낸다.
7.SP.C.8Identify Subproblems오각형 안에 숨은 대각선들은 하나의 다섯 꼭짓점 고리를 이룬다. 그래서 문제는 결국 "6색으로 크기 5 고리를 이웃끼리 다르게 칠하기"이다: 쉬운 열린 사슬을 세고(6 · 5⁴ = 3750), 마지막 연결을 깨는 630을 빼면 3120에 도달한다.
- 대각선을 고리로 바꾸기
- 먼저 열린 사슬로 세기
- 깨진 규칙 하나 찾기
- 양 끝 붙이기: 더 작은 고리
- 크기 4 고리까지 내려가기
- 크기 5 고리 마무리