1986년에 치루어진 제 27회 IMO에서 최고의 변별력을 가진 문제는 3번 문제였습니다. 풀이에 이용되는 핵심 아이디어인 불변성의 원리를 알아봅시다.
불변성의 원리란 문제 해결과정에서 여전히 변하지 않고 그대로 남는 것을 관찰하는 원리입니다. 즉, 불변량을 관찰하는 문제 해결 전략이죠. 예제들을 해결하며 더 자세히 알아봅시다.
Question 1.
홀수 $n$에 대하여 칠판에 $1$, $2$, $\cdots$, $2n$의 자연수가 적혀있다. 칠판의 적혀있는 임의의 두 자연수 $a$, $ b$에 대하여 두 자연수를 지우고 $\left\vert a-b \right\vert$를 적는다. 이 과정을 반복하여 맨 마지막에 남는 수가 홀수임을 증명하여라.
sol) $a+b$와 $\left\vert a-b \right\vert$의 기우성(짝홀성)이 같으므로, 과정이 반복되어도 칠판에 적힌 자연수들의 총합의 기우성은 바뀌지 않는다. 이것이 이 문제에서의 불변량이다. 따라서 맨 마지막에 남는 수는 처음 적혀있던 수들의 총합인 $$1+2+\cdots+2n=n(2n+1)$$와 기우성이 같으므로, 맨 마지막에 남는 수는 홀수이다.
Question 2.
정육각형의 각 꼭짓점에 $1$, $0$, $1$, $0$, $0$, $0$ 이 순서대로 적혀 있다. 임의의 인접한 두 수를 1씩 증가시키는 과정이 가능할 때, 이 과정을 반복하여 정육각형의 꼭짓점에 쓰인 모든 수들을 같게 만드는 것이 가능한지 판별하여라.
sol) 각 꼭짓점에 쓰인 숫자들을 순서대로 $a_1$, $b_1$, $a_2$, $b_2$, $a_3$, $b_3$라 정의하자. 이때 $a$들은 짝수번째 꼭짓점들에 쓰인 수, $b$들은 홀수번째 꼭짓점들에 쓰인 수라고 생각할 수 있다. 인접한 두 수를 $1$씩 증가시키면 짝수번째 꼭짓점과 홀수번째 꼭짓점의 수가 각각 $1$씩 증가한다. 따라서 다음과 같은 불변식을 찾을 수 있다. $$I=\left(a_1+a_2+a_3\right)-\left(b_1+b_2+b_3\right)$$ 처음 상황에서는 $I=2$ 인데, 모든 수가 같을 때는 $I=0$ 이므로 모든 수를 같게 만드는 것은 불가능하다.
예제 2문제를 해결하며 불변성의 원리가 무엇인지 알아보았으니, 이제 이를 이용하여 1986 IMO 3번 문제를 해결해봅시다.
1986 IMO 3.
오각형의 각 꼭짓점에 정수가 매겨져 있고, $5$개의 정수의 합은 양수이다. 연속적인 꼭짓점에 매겨진 세 정수를 $x$, $y$, $z$라 하자. $y<0$인 경우에 $(x, y, z)$를 $(x+y, -y, y+z)$로 바꾸자. 정수들 중 음수가 존재하면 이 알고리즘은 계속될 때, 이 알고리즘이 항상 멈추게 되는지 판정하여라.
sol) $(x, y, z)$에서 $(x+y, -y, y+z)$가 되는 과정에서 $5$개의 정수의 합은 바뀌지 않으므로, 알고리즘이 시행되더라도 5개의 정수의 합은 바뀌지 않고 그대로 양수이다. $5$개의 꼭짓점에 적힌 정수를 $x_1$, $x_2$, $x_3$, $x_4$, $x_5$라고 정의한 후, 다음과 같은 함수를 정의하자.
\begin{align}&f(x _{1}, x _{2}, x _{3}, x _{4}, x _{5})\\&=(x _{1} -x _{3}) ^{2} +(x _{2} -x _{4}) ^{2} +(x _{3} -x _{5}) ^{2} +(x _{4} -x _{1}) ^{2} +(x _{5} -x _{2}) ^{2}\end{align}
$x_1$을 중심으로 과정이 한 번 실행되었을 때, $f$값의 변화를 살펴보자. (이때 $x_1$은 음수이다.)
\begin{align}&f_{new}-f_{old}\\&={(-x_1-x_3)^2+(x_1+x_2-x_4)^2+(x_3-x_1-x_5)^2+(x_4+x_1)^2+(x_1+x_5+x_1)^2}\\&-((x_1-x_3)^2+(x_2-x_4)^2+(x_3-x_5)^2+(x_4-x_1)^2+(x_5-x_1)^2)\\&=2x_1(x_1+x_2+x_3+x_4+x_5)<0\end{align}
알고리즘이 멈추지 않는다면 $f$의 값은 계속해서 감소하므로 $f_0>f_1>f_2>\cdots$을 만족하는 음이 아닌 정수의 수열을 찾을 수 있어야 한다. 그러나 이런 수열은 존재하지 않으므로 알고리즘은 항상 멈추게 된다.
Exponential 17 김지하
댓글