국제수학올림피아드란 전세계에서 각국의 수학 괴물들을 모아 놓고 치루는 수학경시대회야.

-주로 고등학생들이 출전-

보통 수학 경시대회 하면, 엥? 그거 과학고 애들 스펙 쌓는 대회 아니냐? 라는 편견도 종종 있지만,

이 대회만은 무시할 수 없는게 이 대회 출신 중에 필즈상을 받는 수학자로 성장하는 경우가 종종 있거든

실제로, 100년 난제 푸앵카레의 추측을 푼 수학자 페렐만도 이 대회 만점자 출신이야

IMO 문제가 얼마나 어렵냐면, 이틀 동안 6문제를 푸는 데 하루에 4시간 30분을 줘 ㄷㄷ

우리나라도 꾸준히 참가하고 있고, 좋은 성적을 거둬오고 있어

특히 올해 2017 IMO에서는 우리나라가 1등을 했어

오늘 소개할 문제는 1988년도에 나온 정수 분야 문제야.

IMO에서 가장 어렵다는 6번 문제 중에서도 악명 높기로 소문난 문제지

문제 소개부터 할게

이 문제는 실제로 호주의 출제위원 여섯 명 중에 아무도 풀지 못 했고, 정수론 학자 4명에게 보냈는데 그들도 6시간동안 풀지 못 했대

너무 어려워서 내지 말까 하다가 그냥 냈는데, 참가자 중에 11명이 만점에 가까운 해답을 냈다고 해 ㄷㄷ

특히 베트남 만점자는 나중에 필즈상까지 받게 되지!

각설하고, 바로 풀이 들어갈게

[풀이] ========================================================

내가 좋아하는 예시를 통해서 문제를 분석해 보면,

a=b=1 일 때에는 q가 자연수 1이 되고 이 경우에는 완전제곱수가 되지.

그리고 a=2, b=8 일 때 분자가 68, 분모가 17이 되어서 q가 4가 되네. 이 경우 역시 완전제곱수...

일단 위 식이 성립하는, 즉 q가 자연수가 되는 q를 하나 잡아.

q에 대해서 위 식이 성립하는 (a,b) 집합을 생각하면

자연수의 집합이기 때문에 최소 원소를 생각할 수 있어

이 아이디어는 풀이에 핵심이 되는 아이디어야

예를 들어 q=4 이면 위에 나온 예시와 같이 (a,b) = (2,8) 이 되어서 공집합이 아닌데,

혹시나 q=4 가 되는 다른 (a',b') 라는 수가 있을 수 있으니까

그런 수들을 모아놓은 집합 (A,B) 를 정의하고 그 집합의 최소 원소를 (a,b) 라고 잡는 거지.

여기까지 하고 b와 aq의 크기를 비교해 볼게

준식을 정리하고 

다시 정리해 주면, q가 자연수니까 우변은 당연히 a² 보다 작아.

a<b 로 두었으니까 a² 은 ab 보다 작겠지?

즉, b(aq-b) < ab 라는 소리니까 b를 나눠주면

aq-b < a.

정리하면 aq - a < b 가 나와. 

다시 아까의 식으로 돌아와서, b가 aq보다 크다고 가정하고 자연수 c에 대해

b=aq+c 라고 둘게.

식에 대입하면,

다시 정리하면

a는 1보다 크고 c는 1 이상의 자연수인데, 즉 aqc > q 가 되어야 하는데 위 식이랑 안 맞지?

따라서 모순이 발생하기 때문에 우리가 한 가정인 자연수 c는 없어.

즉, c≤0 이고 

따라서 b≤aq

정리하면 이런 부등식을 얻지.

b가 자연수니까, 부등식에 맞게 임의의 자연수 r을 잡고

b = aq - r 이라고 정의할 수 있겠네. (단, 0≤r<a)

나머지 정리와 모양은 비슷한데 나머지가 마이너스인게 달라 보여.

어쨌든 준식에 대입하면,

이고, 정리하면 

라고 정리할 수 있어.

많이 보던 식이지?

(r,a) 를 집어넣었을 때 q가 나온다는 것은 

(r,a) 가 (A,B) 집합에 속한다는 거야.

근데 r은 a보다 작지?

이건 우리가 (a,b)가 최소 원소라고 정의한 것에 위배돼.

따라서 가능한 경우는 r=0 인 경우밖에 없어.

대입하면,

즉, q는 완전제곱수가 되네.

[풀이] ========================================================

풀이는 여기서 끝이 나고,

이렇게 풀이로 보면 쉬워보이지만 막상 문제를 만났을 때 이 많은 아이디어를 떠올리는 건 얼마나 어려울까

여담으로 우리나라 학부 정수론 교재 중에 이 문제를 연습문제로 넣어놓은 변태같은 교재가 있어

뭣모르고 덤볐다가 반나절 까먹기 쉽상인데, 그 피해자 중 한 명이 나야 ㅅㅂ

답지도 없어서 인터넷에 물어봤다가, 이 문제를 알게 되어서 소개해 봤어 ㅎㅎ