AMC 10 · 2013 · #12
학년 7 counting
답을 골라 클릭하세요.
도로 일곱 개를 나열하는 방법은 너무 많아서 무작정 경로를 적어 보는 것은 가망이 없다. 두 가지 생각이 이 일을 손으로 끝낼 수 있고 확신할 수 있는 크기로 줄여 준다. 첫째, 도로가 아니라 도로의 '끝'을 센다. 한 도시에 붙은 도로 끝의 개수가 그 도시에 몇 번 들를 수 있는지를 결정하며, 이것이 나열을 시작하기도 전에 모든 경로의 모양을 못박는다. 둘째, 도시 C와 E는 도로가 두 개뿐이라 들어가면 반드시 나머지 하나로 나와야 한다. 선택의 여지가 없는 강제된 우회로이므로, 이를 접어 넣으면 도시가 셋뿐인 그림이 남는다. 이 접기가 되돌릴 수 있어야 한다. 그렇지 않으면 작은 그림은 다른 질문에 답하는 셈이 되므로, 되돌릴 수 있다는 사실은 가정하지 않고 증명한다. 그러면 짧고 완전함이 증명된 목록이 남고, 접으면서 버린 선택은 마지막에 곱셈으로 되살린다.
도시마다 도로 개수 세기
도시별 도로 수를 세는 것이 첫 수다.
모든 도로에는 끝이 두 개 있으므로, 도시마다 도로를 세어 더하면 각 도로가 정확히 두 번씩 세어진다.
모든 길에는 끝이 둘 있으므로, 도시마다의 길을 모두 더하면 각 길이 정확히 두 번 세어진다.
▸ 왜?
각 길은 정확히 두 도시에 속하므로, 도시를 따라 더하면 두 번 지나게 된다.
▸ 왜?
도시를 지나갈 때는 길을 둘씩 쓰므로, 길이 홀수 개인 도시는 출발점이나 도착점일 수밖에 없다.
홀수는 시작과 끝을 못박는다
홀수가 시작과 끝을 고정한다.
어떤 곳을 지나가는 일은 항상 도로를 두 개씩 쓰므로, 홀수 개의 도로가 붙은 곳은 여행이 시작되거나 끝나는 곳일 수밖에 없다.
2.OA.C.3Organize Information In More WaysC와 E는 강제된 우회로
도로가 둘뿐인 도시는 강제된 우회로다.
도로가 정확히 두 개인 도시는 갈림길이 아니라 복도라서, 한 번 들어가면 나가는 길이 하나뿐이다.
7.SP.C.8Solve An Easier Related Problem접어 넣고, 되돌아가는지 확인하기
그것을 접어 넣으면 더 작은 그림이 남는다.
복도를 문 하나로 줄여도 여행이 사라지지 않는다. 언제든 그 문을 다시 복도로 늘일 수 있기 때문이다.
4.OA.A.3Draw A Diagram순서와 쌍둥이로 나누기
개수가 순서 곱하기 선택으로 나뉜다.
여정을 정하는 일과 똑같아 보이는 두 도로 중 어느 쪽으로 갔는지 정하는 일은 별개의 결정이므로, 두 개수는 곱해진다.
7.SP.C.8Identify Subproblems도시 순서를 모두 나열하기
가능한 도시 순서는 넷이다.
어떤 도시가 몇 번 나오는지 알고 나면 남은 자유는 배치뿐이고, 이웃이 같으면 안 된다는 규칙이 대부분의 배치를 곧바로 지워 버린다.
7.SP.C.8Make A Systematic List순서 하나를 실제 경로로 되펴기
각각이 실제 경로로 되펴진다.
줄여 놓은 경로 하나가 합법적인 일곱 도로 주행으로 다시 부풀어 오르는지 확인하면, 그 지름길이 손실이 아니라 번역이었음이 확인된다.
7.SP.C.8Solve An Easier Related Problem두 개수를 곱하기
곱하면 16, 보기 (E).
빠짐없는 여정 목록에 각 여정을 실현하는 고정된 방법 수를 곱하면, 빠뜨림도 중복도 없이 전체 개수가 나온다.
4.OA.A.3Make A Systematic List먼저 도시마다 도로 끝의 개수를 세라. 짝수면 언제나 지나가는 곳이고 홀수면 여행이 시작되거나 끝나는 곳이다. 그리고 도로가 두 개뿐인 도시는 접어서 없앨 수 있는 복도다.
- 도시마다 도로 개수 세기
- 홀수는 시작과 끝을 못박는다
- C와 E는 강제된 우회로
- 접어 넣고, 되돌아가는지 확인하기
- 순서와 쌍둥이로 나누기
- 도시 순서를 모두 나열하기
- 순서 하나를 실제 경로로 되펴기
- 두 개수를 곱하기