| [ QuizWit ] in KIDS 글 쓴 이(By): whiz (<아직도꿈>) 날 짜 (Date): 1998년 8월 16일 일요일 오후 08시 23분 46초 제 목(Title): Re: [문제] 우주 정거장... - 증명 *** 8월 18일 (화요일) 11시 45분에 증명을 개정함. 흠. '증명'해 봅시다. 다 풀어진 거지만, 정리해 두자는 의미죠. <== pomp야 두고보자. 이 은혜(?) 잊지 않으마. 이제 노가다가 시작되니, 읽기 싫으신 분은 q를 눌러주세요. 편의상, 점과 그 점에 씌여진 숫자를 구별하지 않았습니다. 정의 1 : 꼭지점(정거장)에서 나온 선분(통로)의 개수를 degree라 한다. 정의 2 : 꼭지점에서 가지치기가 없다는 것은, degree가 2이하라는 것이다. 정의 3 : maximal degree는 degree의 최대값이다. 보조정리 1 : 양끝을 제외하고는 가지치기가 없는 '임의의 부분'은 '등차수열'을 이룬다 <증명> 각 꼭지점에 씌여진 숫자를 각각 a(j), 즉, a(1) a(2) a(3) ... a(n) o-------o--------o-------o...o------o 이라고 하면, (단, 양끝점 a(1)과 a(n)은 가지칠 수 있음) a(k) + a(k+2) = 2 a(k+1) 이므로 당연하다. 보조정리 2 : '고리'가 존재하면, 더 이상 가지치기는 없다. <증명> 고리에 씌여진 수를 차례로 a, b, c, ..., z 라고 하면 조건에 의하여 a+c \le 2b (여기에서 \le 는 '작거나 같다'구요) b+d \le 2c . . . x+z \le 2y y+a \le 2z 가 됩니다. (등호는, 각 경우에 더 이상의 가지치기가 없을 때 성립) 양변을 더하면 2(a+b+...+z) \le 2 (a+b+...+z) 인데 실제로는 양변이 같으므로, 위에서 각 경우 모두 등호가 성립해야 한다. 보조정리 3 : '고리'가 존재하면, 모든 숫자는 같아야 한다. <증명> 보조정리 1에서, a,b,...,y,z 는 등차수열이다. 같은 방법으로 b,c,...,z,a 도 등차수열이다. 따라서, a=b=c=...=z 일 수 밖에 없다. 이것을 정리하면, 다음 정리를 얻는다. 정리 1 : pomp의 우주정거장은 '트리'이거나 '모든 숫자가 같은 고리'이다. 이제 '트리' 구조의 우주정거장만 생각하자. 보조정리 4 : maximal degree는 4이하이다. <증명> 귀류법으로 증명한다. degree가 5이상인 점을 x라 하고, x 주변의 점을 b(1), b(2), ... , b(k) 라고 하면, (단, k는 5 이상) 2x = b(1) + b(2) + ... + b(k)에서, b(i) 중 적어도 하나는 2x/5 이하이다. (예를 들어, b(i)중 최소를 고른다) 이 b(i)에 대하여, 2 b(i) = x + *** 이어야 하는데, 오른쪽 변이 4x/5 이하가 되어 모순이다. 정리 2 : maximal degree가 4인 pomp 우주정거장은 딱 하나이다. <증명> 보조정리 4와 같은 방법을 쓰면, b(1)=...=b(4) 이어야 하고, 각 b(i)에 대하여, *** 부분은 없어야 한다. 따라서, x | x - x -- x | x 꼴만 가능하다. 이제부터 maximal degree는 3이라고 가정하자. 보조정리 5 : degree가 3인 점은, 주위의 세 점보다 각각 숫자가 작지않다. <증명> degree가 3인 점을 a, 주위의 세 점을 x,y,z라 하자. 먼저, a \le 2y 와 a \le 2z 는 당연하다. 따라서, 양변을 더하면 a \le y+z 인데, y+z = 2a-x 이므로, x \le a 이다. 같은 방법으로 y,z 도 a 이하이다. 위에서 x=a인 경우는 a=2y, a=2z가 성립하는 경우뿐이다. 보조정리 6 : degree가 3인 점 A 주위의 세 점 P,Q,R에 대하여, A=P 이면, Q,R은 더 이상 연결된 점이 없고, Q=R=A/2이다. <증명> 위의 보조정리 5에서 등호가 성립하는 경우이다. 보조정리 7 : degree가 3인 점은 기껏해야 두 개 존재한다. <증명> A를 degree가 3인 점이라고 하고, 그 중의 한 개의 가지에 존재하는 또다른 degree가 3인 점을 B라고 하자. 이때, 보조정리 5와 보조정리 1에서 A,B위의 모든 숫자는 같아야 한다. 또한 보조정리 6에서 A,B는 주변에 A=B의 반만큼의 숫자를 가지는 점 C,D,E,F 만 갖게 된다. 정리 3 : 보조정리 7에 해당하는 모양은 다음과 같다. x x | | x--2x--2x--...--2x--2x--x 이제 maximal degree가 3인 점은 하나뿐이라고 가정해도 되고, 그 모양을 다음과 같다고 하자. A X B o--o...o--o--o...o--o | o C' : : o C 보조정리 8 : AX, BX, CX의 꼭지점의 개수를 각각 p,q,r 이라고 하면, 1/p + 1/q + 1/r = 1 이다. <증명> 당연히 p,q,r 은 모두 2 이상이다. (왜냐하면 C가 degree 3) 이때, X=pA=qB가 된다. (왜냐하면 AX, BX가 등차수열이고, 둘째항은 첫째항의 두배이어야 하므로) C' = 2X - (p-1)A - (q-1)B = pA + qB - (p-1)A - (q-1)B = A+B 이다. 또한 CX에서, X=rC, C'=(r-1)C 이다. 즉, X=pA=qB=rC이고, C'=(r-1)C=A+B 가 된다. 따라서, rC = A+B+C = r/p C + r/q C + C 가 되고, 양변을 rC로 나누면 원하는 결과를 얻는다. 정리 4 : degree가 3인 점이 하나뿐인 것은, 세 종류이다. <증명> 보조정리 8의 해를 구하면 (p,q,r)=(2,4,4),(2,3,6),(3,3,3)이다. 각각을 그려보면, x -- 2x -- 3x -- 4x -- 3x -- 2x -- x | 2x x -- 2x -- 3x -- 4x -- 5x -- 6x -- 4x -- 2x | 3x x -- 2x -- 3x -- 2x -- x | 2x | x 가 된다. -- I think. Therefore I am ................. single. 나는 생각한다. 고로 나는 존재한다 ....... 이렇게 홀로. |