제 22 회 한국수학올림피아드 1차 시험 (중등부)

2008년 5월 24일 ; 제한시간 4시간

문제 15. 다음 그림과 같이 합동인 두 정오각뿔의 밑면을 붙여 만든 도형에서 모서리들을 길로 간주하자. 아래의 규칙에 따라 점 에서 점 로 이동했다가 다시 점 로 돌아오는 경로의 수를 구하여라.

[규칙1] 점 에서 점 로, 그리고 점 에서 로 이동할 때에는 다시 점 로 이동할 때에는 각각 적어도 세 개의 모서리를 지나간다.

[규칙2] 한 번 지나간 점이나 모서리는 다시 지나가지 않는다.

풀이 : 한 번 P 에서 Q 로, 혹은 Q 에서 P 로 가는데 A, B, C, D, E 중 최소한 두 개의 점은 지나가야 한다. 따라서 갈 때와 올 때 각각 점 두 개씩 거쳐 가는 방법과 세 개, 두 개씩 거쳐가는 방법 두 가지로 나누어 생각할 수 있다. 이때, 가거나 올 때 거쳐가는 점들은 각각 이웃해야 한다.

i) 갈 때와 올 때 각각 두 개씩만 거쳐 갈 경우

A, B, C, D, E 중 네 개를 선택하면, 그 네 점은 연속된 네 점이므로 이웃한 두 점으로 나누는 방법은 한 가지이다. 일반성을 잃지 않고, A, B, C, D 가 선택되었으면, 갈 때와 올 때 거쳐 가는 점을 선택하는 방법은 두 가지이다. (AB/CD) 혹은 (CD/AB).

그리고 AB 가 선택되었을 때, A 를 먼저 갈 수도 있고 B 를 먼저 갈 수도 있다. 이는 C, D 에도 적용되므로 A, B, C, D 가 선택되었을 때의 경우의 수는 2×2×2 = 8.

따라서 모든 가지수는 8×₅C₄ = 40 가지이다.

ii) 갈 때 올 때 거치는 점이 두 개, 세 개일 경우.

우선 갈 때 거치는 점을 고르는 방법은, 다섯 개의 점 중 이웃한 두 개의 점을 고르면 되므로 5 가지이다. 일반성을 잃지 않고 A, B 를 골랐다고 하면, 올 때는 C, D, E 를 거치게 된다.

갈 때는 A→B 혹은 B→A 로 올 수 있고, 올 때는 C→D→E 혹은 E→D→C 로 올 수 있다.

따라서 이 경우의 경우의 수는 5×2×2=20가지.

iii) 갈 때 세 개, 올 때 두 개 거치는 경우

ii) 와 마찬가지로 20가지.

∴ 40 + 20 + 20 = 80 가지

답 : 80