2010 JMO #3

3. 2010개의 섬이 있고, 그 섬들을 연결하는 2009개의 다리가 있다. 어떤 두 개의 섬에 대해서도 1개의 다리가 둘을 연결하거나 다리가 없거나 둘 중의 하나라 하고, 다리의 양 끝은 서로 다른 두 개의 섬이라 하자. 또한, 임의의 두 섬을 골라도 한 섬에서 다른 섬으로 다리를 몇 번 건넘으로써 갈 수 있다고 한다.
이제, 모든 섬이 한 통의 편지를 임의의 섬에 보낸다고 한다. (단, 자기 자신에게 편지를 보내는 것도 가능하다.) 이 때, 다음 사실이 판명되었다.
“섬 A와 섬 B가 다리로 연결되어 있으면, 섬 A의 편지의 목적지와 섬 B의 편지의 목적지는 서로 다리로 연결된 두 섬이거나, 같은 섬이다.
이 때, 다음 (1)과 (2) 중 적어도 하나가 성립함을 보여라.
(1) 자기 자신에게 편지를 보낸 섬이 존재한다.
(2) 서로 편지를 교환하고, 다리로 연결되어 있는 두 섬이 존재한다.

그래프로 바꾸면 단순그래프인데 2010개의 점, 2009개의 변을 갖고 있고 연결그래프가 되어야 한다. 곧 이 그래프는 수형도로 회로가 없다. 편의상 도시 X가 편지를 보낸 도시를 f(X)라 하자. 그러면 보여야할 것은 f(X)=XX가 존재함을 보이거나 f(X)=Y,f(Y)=XX,Y가 존재함을 보이면 된다. 귀류법으로 그런 경우가 없음을 가정하자. 그리고 수형도이기 때문에 X에서 f(X)로 가는 경로는 유일하게 존재하는데 그 길이를 d(X)라고 하자.

먼저 임의의 도시 X_0을 택한다. 그리고 d(X_0) \geq 2임을 가정하자. 그러면 X_0에서 f(X_0)으로 가는 경로가 있는데 그 경로에서 X_0 바로 다음 점을 X_1이라 한다. 마찬가지로 X_1에서 f(X_1)으로 가는 경로에서 X_1의 다음 점을 X_2라 하고, 계속 정의한다. 그러면 0 \leq d(X_{i+1})-d(X_i) \leq 2임을 보일 수 있다. 그런데 d(X_{i+1})=d(X_i)인 경우는 X_i에서 f(X_i)까지 이어진 경로 위에 f(X_{i+1})이 없음을 의미한다. 즉 새로운 점이 하나 필요하게 된다. 따라서 d(X_{i+1})=d(X_i)인 경우는 무수히 많이 나올 수 없어서 d(X_i)는 계속 감소해야만 한다. 그러면서도 0이 되어선 안 된다. (d(X_i)=0이면 X_i=f(X_i), 모순) 그러면 언젠가 d(X_n)=1n이 존재하게 된다. (만약 d(X_0)=1이었다면 바로 n=0인 경우로 보면 된다.)

이제 m \geq n인 경우 X_{m+1}=f(X_m)이 되어야 한다. 이 때 앞에서와 비슷한 논의로 계속 새로운 점이 나올 수 없어서 언젠가 f(X_m)=X_m이거나 f(X_m)=X_{m-1}이 되어야 한다. 이는 모순. 끝

풀기 전에 좀 브레인스토밍하다보면 문제가 어떤 의미인지 또 어떤 풀이인지 감은 잡히는데 그걸 표현하는게 다소 짜증나는 문제

Advertisements
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: