전설적인 IMO 문제

양의 정수 가 있어 이 정수라면, 이 값은 완전제곱수이다.

1988년 호주에서 열린 IMO(국제수학올림피아드)의 6번 문제. IMO 역사에서 아직도 전설적인 문제로 남아있고, IMO 사상 가장 어려운 문제라고도 일컬어지고 있다. 단순히 정답률만 따지면 2017년 3번 문제가 가장 어려운 문제로 등극할 수도 있지만 (7명만이 1점 이상의 점수를 받았고 2명만이 7점 만점을 받았다) 위 문제의 경우 그와 관련된 아래의 유명한 일화 덕에 서사를 갖췄단 점에서 “전설적인 문제”라는 타이틀을 쉽게 뺏기게 될 것 같지는 않다.

Arthur Engel은 자신의 저서 “Problem Solving Strategy”에서 이 문제에 얽힌 일화를 소개했다. 당시 IMO 문제 출제위원회에 있던 6명의 수학자들은 이 문제를 풀지 못했고, 이 문제를 호주의 정수론학자 네 명에게 보내 6시간 안에 풀게 했으나 아무도 풀지 못했다. 그럼에도 이들은 이 문제를 후보 문제에 올렸고, (엄청 어렵단 뜻으로 ** (double asterisk) 표시를 붙였다고 한다) jury meeting(단장 회의)을 통해 이 문제가 IMO 문제로 출제된다. 그리고 11명의 고등학생들이 이 문제를 풀었다.

특히 이 문제는 지금까지도 이어져 내려오는 간결한 풀이가 있어 그 전설 타이틀의 수성에 힘을 보태고 있다. 로 고정하고, 이 에 대해 인 중에서 그 합 가 최소인 것을 잡는다. 일반성을 잃지 않고 라고 하면, 이란 이차방정식의 해로 가 하나 주어지게 된다. 그러면 Vieta의 정리(근과 계수의 원리)에 의해 다른 해 는 이자 로 표현된다. 여기서 는 에서 를 대체할 수 있는 값이므로, 곧 임을 염두에 둔다.

만약 이라면 는 양의 정수가 되는데 이므로 결국 는 와 같은 식을 만족시키면서 두 수의 합은 더 작아지므로 최소성에 모순이 된다. 따라서 인데, 만약 이면 가 성립하지만 이므로 모순이 되어 이어야 한다. 곧 상수항 도 0이어야 해서 으로 완전제곱수가 된다.

이렇게 주어진 비율을 상수로 고정시킨 후 근과 계수의 관계로 다른 해를 찾아내어 그 해로 옮기는(“점프”하는) 방식은 지금은 이미 올림피아드 정수론 문제에서 정석으로 굳혀진 방법론이 되었으며, Vieta jumping이라 불리는 기법으로 정립되었다. 이 문제처럼 두 변수의 다항식의 비율로 주어진 식이 양의 정수를 대입해 정수 값을 가지면 어떤 특징을 가진다는 유형의 문제에서 식을 변형시켜 2차 대칭식으로 만들어 Vieta jumping을 쓰는 경우가 많다. 또한 역방향으로 점프해 해의 값을 크게 키우면 조건을 만족시키는 모든 해를 찾는 것도 가능한 아주 유용한 툴이다.

Numberphile 채널에서 올라왔던 이 문제를 다뤘던 영상들.

참고로 당시 이 문제에서 7점을 받은 루마니아 학생 Nicușor Dan은 1987년과 1988년 IMO에서 42점 만점을 받았는데 후에 프랑스 에콜 노말 슈페리외르로 유학한 후 1998년 루마니아로 돌아와 그 학교를 모델로 한 대학의 창립멤버가 되어 수학 교수로 재직하고 있다고 한다. 그러면서도 정치인으로서도 활동하기 시작해 USR(Save Romania Union)이란 당을 창당했으며(진보와 보수를 어우르며 현재 루마니아 원내 제3당을 차지하고 있다), 부카레스트 시장 선거에도 출마했는데 2016년 선거의 경우 30.52%의 표를 차지해 2위로 낙선하기도 했다고.

근데 저 설명만 가지고 현재 한국 정치인에 들어맞는 사람을 찾으면… 이공계 출신에 진보 보수 양쪽 인물이 포진된 당을 창당하고 시장 선거에 나가 낙선한 인물… 앗 아닙니다

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2016/08/17)

9. 양의 정수 a,b가 있어 ab+1이 a^2+b^2을 나눈다면, 그 몫은 완전제곱수이다.

— Elegant Math (@elegant_math) August 17, 2016