폴리매스 대한수학회 3번 부분증명

증명할 내용: [eqn: lambda GEQ 1]일 때, 양단이동이 벼룩을 옮기는 최선의 방법이다.

1. 기호 정의

일단 [eqn: n]개의 점의 위치를 작은 것부터 나열한 순서쌍 [eqn: (a _{1`} ,a _{2`} ,...`,a _{n} )``]을 생각하자. 이 때, 두 순서쌍 [eqn: (a _{1`} ,a _{2`} ,...`,a _{n} )``]과 [eqn: (b _{1`} ,b _{2`} ,...`,b _{n} )``]에 대해서 [eqn: a _{i} GEQ b _{i} ,`a _{n} -a _{i} GEQ b _{n} -b _{i} ``(1 LEQ i LEQ n)]이 성립하면 순서쌍 [eqn: (a _{1`} ,a _{2`} ,...`,a _{n} )``]이 순서쌍 [eqn: (b _{1`} ,b _{2`} ,...`,b _{n} )``]보다 빠른 순서쌍이다.

벼룩이 더 오른쪽에 있을수록 더 빠른 순서쌍이 되므로 두 순서쌍에서 대응하는 벼룩의 좌표를 비교하였다. 그리고 가장 오른쪽에 있는 점과의 거리가 멀면 멀수록 이동했을 때 더 멀리 갈 수 있다.

그리고 순서쌍에서 두 점 [eqn: a _{k} ,`a _{n}]을 잡아 이동하는 시행을 [eqn: f(k)]라고 정의하자.

2. [eqn: n=3]일 때의 양단이동과 그 외의 이동의 비교

먼저, [eqn: n=3]일 때 양단이동이 그 외의 이동 방법보다 더 빠르다는 것을 증명하자.

일단 이것을 증명하기 위해서는 [eqn: n=3]일 때 [eqn: f(1) -> f(1)]을 통해 나온 순서쌍이

[eqn: f(2) -> f(1)]을 통해 나온 순서쌍보다 더 빠른 순서쌍임을 증명해야 한다.

증명)

초기 순서쌍을 [eqn: (a _{1} ,`a _{2} ,`a _{3} )]라고 하자. 이 때 [eqn: f(1) -> f(1)]을 통해 나온 순서쌍과

[eqn: f(2) -> f(1)]을 통해 나온 순서쌍을 비교하면 다음과 같다.

[eqn: f(1) -> f(1)]: [eqn: (a _{1} ,`a _{2} ,`a _{3} ) -> (a _{2} ,a _{3} ,(1+ lambda )a _{3} - lambda a _{1} ) -> (a _{3} ,(1+ lambda )a _{3} - lambda a _{1} ,(1+ lambda ) LEFT { (1+ lambda )a _{3} - lambda a _{1} RIGHT } - lambda a _{2} )]

[eqn: f(2) -> f(1)]: [eqn: (a _{1} ,`a _{2} ,`a _{3} ) -> (a _{1} ,a _{3} ,(1+ lambda )a _{3} - lambda a _{2} ) -> (a _{3} ,(1+ lambda )a _{3} - lambda a _{2} ,(1+ lambda ) LEFT { (1+ lambda )a _{3} - lambda a _{2} RIGHT } - lambda a _{1} )]

빠른 순서쌍의 정의를 이용해 두 순서쌍을 비교하면 다음과 같다.

[eqn: a _{3} GEQ a _{3} `,(1+ lambda )a _{3} - lambda a _{1} GEQ (1+ lambda )a _{3} - lambda a _{2`} ,# (1+ lambda ) LEFT { (1+ lambda )a _{3} - lambda a _{1} RIGHT } - lambda a _{2} GEQ (1+ lambda ) LEFT { (1+ lambda )a _{3} - lambda a _{2} RIGHT } - lambda a _{1} ``]

이므로 일단 좌표의 값은 [eqn: f(1) -> f(1)]의 경우가 모두 [eqn: f(2) -> f(1)] 이상이다.

그럼 이제 거리를 계산해 보자.

[eqn: (1+ lambda ) LEFT { (1+ lambda )a _{3} - lambda a _{1} RIGHT } - lambda a _{2} -a _{3} GEQ (1+ lambda ) LEFT { (1+ lambda )a _{3} - lambda a _{2} RIGHT } - lambda a _{1} `-a _{3} `]이고,

[eqn: (1+ lambda ) LEFT { (1+ lambda )a _{3} - lambda a _{1} RIGHT } - lambda a _{2} - LEFT { (1+ lambda )a _{3} - lambda a _{1} RIGHT } GEQ # (1+ lambda ) LEFT { (1+ lambda )a _{3} - lambda a _{2} RIGHT } - lambda a _{1} `- LEFT { (1+ lambda )a _{3} - lambda a _{2} RIGHT } `]

[eqn: - lambda (1+ lambda )a _{1} - lambda a _{2} + lambda a _{1} GEQ - lambda (1+ lambda )a _{2} - lambda a _{1} + lambda a _{2} `], [eqn: lambda ( lambda -1)a _{2} GEQ lambda ( lambda -1)a _{1} `] 이므로 거리도

[eqn: f(1) -> f(1)]의 경우가 모두 [eqn: f(2) -> f(1)] 이상이다. 그러므로 [eqn: f(1) -> f(1)]을 통해 나온 순서쌍이 [eqn: f(2) -> f(1)]을 통해 나온 순서쌍보다 더 빠른 순서쌍이 된다.

이제 이 사실을 이용하여 [eqn: n=3]일 때 임의의 이동을 [eqn: m]번 시행한 것보다 양단이동을 [eqn: m]번 시행한 것이 벼룩을 더 오른쪽으로 보냄을 증명하자.

증명)

만약 양단이동을 [eqn: m]번 시행한 것보다 벼룩을 더 오른쪽으로 보낼 수 있는 방법이 존재한다고 가정하자. 그러면 이 방법은 [eqn: f(1)]과 [eqn: f(2)]을 총 [eqn: m]개 배열한 것으로 나타낼 수 있다. 일단 [eqn: m]개의 배열에서 마지막에 [eqn: f(2)]가 있는 것보다는 [eqn: f(1)]이 있는 것이 벼룩을 더 오른쪽으로 보낼 수 있는 방법이다. 그런데 마지막 시행을 [eqn: f(1)]으로 고정한 이 배열은 [eqn: f(1)]이 [eqn: m]개 있지 않은 이상 [eqn: f(2)] 다음 [eqn: f(1)]이 오는 경우가 존재하게 된다. 그러나 [eqn: f(2) -> f(1)]의 시행은 [eqn: f(1) -> f(1)]의 시행보다 더 느린 순서쌍을 만들어내므로

[eqn: f(2) -> f(1)]을 [eqn: f(1) -> f(1)]으로 고치는 시행을 반복하면 결국 모든 배열이 [eqn: f(1)]이 되게 되고, 이것은 양단이동을 [eqn: m]번 시행한 것과 같은 배열이 된다. 순서쌍의 빠르기를 비교하면 (임의의 이동을 [eqn: m]번 시행한 순서쌍)<(기존의 이동을 수정하여 더 빠르게 만든 순서쌍)=(양단이동을 [eqn: m]번 시행한 순서쌍)이 된다. 그러므로 [eqn: n=3]일 때 임의의 이동을 [eqn: m]번 시행한 것보다 양단이동을 [eqn: m]번 시행한 것이 벼룩을 더 오른쪽으로 보내게 된다.

3. 수학적 귀납법의 사용

[eqn: n=3]일 때 양단이동이 최선의 이동 방법임을 증명했으므로 “[eqn: n=k]일 때 양단이동이 최선의 방법이라면, [eqn: n=k+1]일 때도 양단이동이 최선의 방법이다.”라는 명제만 증명하면 증명이 끝난다.

증명)

[eqn: n=k+1]일 때, 만약 양단이동을 [eqn: m]번 시행한 것보다 벼룩을 더 오른쪽으로 보낼 수 있는 방법이 존재한다고 가정하자. 그러면 이 방법은 [eqn: f(1),`f(2),`...`,`f(k)]을 총 [eqn: m]개 배열한 것으로 나타낼 수 있다. 일단 [eqn: m]개의 배열에서 마지막에 [eqn: f(1)]이 있는 것이 벼룩을 더 오른쪽으로 보낼 수 있는 방법이다. 그런데 마지막 시행을 [eqn: f(1)]으로 고정한 이 배열은 [eqn: f(1)]이 [eqn: m]개 있지 않은 이상 [eqn: f(2),`...`,`f(k)]로만 구성된 구간이 존재하게 된다. [eqn: f(2),`...`,`f(k)]로만 구성된 구간은 순서쌍 [eqn: (a _{2`} ,a _{3} ,`...,`a _{k+1} )]에 대해 임의의 이동을 시행한 것

과 같다. 그런데 [eqn: n=k]일 때는 양단이동이 최선의 이동 방법이므로 이 구간의 시행을 모두 [eqn: f(2)]로 바꾼 배열이 더 빠른 순서쌍을 만들어낸다. 그러면 바뀐 배열은 [eqn: f(1)]과 [eqn: f(2)]가 [eqn: m]개 배열되어 있는 수열인데, 이번에도 [eqn: f(2) -> f(1)]을 [eqn: f(1) -> f(1)]으로 고치는 시행을 반복하면 결국 모든 배열이 [eqn: f(1)]이 되게 되고, 이것은 양단이동을 [eqn: m]번 시행한 것과 같은 배열이 된다. ([eqn: f(2) -> f(1)]과 [eqn: f(1) -> f(1)]을 순서쌍 [eqn: (a _{1} ,a _{2} ,a _{n} )]에 시행하는 것으로 보면 된다.) 그러므로 [eqn: n=k]일 때 양단이동이 최선의 방법이라면, [eqn: n=k+1]일 때도 양단이동이 최선의 방법이다.