2009 IMO P5 (함수방정식)

 

다음 조건을 만족하는 함수 \(f:\mathbb{N} \to \mathbb{N} \)을 모두 구하여라. 

(조건) 모든 양의 정수 \(a, b\)에 대하여,  \(a, f(b), f(b+f(a)-1)\)을 세 변으로 하는 삼각형이 존재한다. 

(단, 세 꼭짓점이 일직선상에 있는 퇴화삼각형은 삼각형이 아닌 것으로 본다.)

 

 

hint1)

우리가 확신할 수 있는 값은 \(a\)뿐이다. 이걸 통해 등식을 찾을 수 있을까? 

 

hint2)

\(f(1)\)을 구하는게 문제를 관통하는 흐름이다. 

 

hint3)

등식을 얻었다면, 답을 예상할 수 있고 그렇다면 귀납적으로 해결해보자. 

 

sol)

주어진 식을 만족하는 함수 \(f\)가 존재한다고 가정하자.

\(P(x,y)\)는 주어진 조건에 \(a=x, b=y\)를 대입하여 정리한 결과로 표기한다.

 

Claim 1: \(f(1)=1\)이다.

\(k=f(1)-1\)이라 두고, \( k\geq 1\) 이라 가정하자. 

\(P(1,n)\):  모든 \(n\)에 대해 \(1, f(n), f(n+k)\) 가 삼각형의 세 변을 이루므로, 

$$ \min(f(n), f(n+k))\leq \max(f(n),f(n+k))<\min(f(n), f(n+k))+1 $$

에서 \(f(n)=f(n+k)\)가 성립한다. 이 함수는 \(f(1), f(2), ..., f(k)\)의 유한한 값들이 반복되는 

주기함수가 되므로, \(a>2\max(f(1),f(2), ... , f(k))\)를 잡아주면 삼각부등식이 성립할 수 없다.

따라서 \(k=0\) 즉, \(f(1)=1\)이다. 

 

 

Claim2. \(f(f(n))=n\)이며, 이 함수는 단사함수이다. 

\(P(n,1)\): 모든 \(n\)에 대해 \(1, n, f(f(n))\) 이 삼각형의 세 변을 이루므로,

$$ \min(n,f(f(n))=\max(n, f(f(n)) $$

이 성립하여,  모든 자연수 \(n\)에 대하여 \(f(f(n))=n\)을 얻는다.

이 조건을 만족하는 함수는 \(f(a)=f(b)\)일 때, \(a=f(f(a))=f(f(b))=b\)이므로, 

단사함수임을 알 수 있다. 

 

이제 \(r=f(2)-1\)로 두자.  

\(P(2,f(n))\): \(2, n, f(f(n)+r)\)이 삼각형의 세 변을 이루므로, 

$$ n-2<f(f(n)+r)<n+2 \rightarrow f(f(n)+r) \in \left\{n-1,n,n+1\right\} $$

이다. \(f(f(n)+r))=n\)이면, \(r=0\)이 되어 \(f(2)=1\)이므로 단사함수임에 모순이다. 

따라서 \(f(n+1)=f(n)+r\)  또는 \(f(n-1)=f(n)+r\)  이 성립한다.

즉, 인접한 두 항의 차이가 \(r\)이다. 

 

Claim3. \(f(n)=1+r(n-1)\)이다. 

\(f(1)=1, f(2)=1+r\)인 상태에서 귀납적으로 \(f(n)=1+r(n-1)\)임을 보이자.

 \(n\leq m\)인 모든 \(n\)에 대해 \(f(n)=1+r(n-1)\)이라 하자. 만약 \(f(m+1)=1+r(m-2)\)라면

이 값은 \(f(m-1)\)과 동일하므로 단사조건에 모순이다. 따라서 \(f(m+1)=1+rm\)이므로

강한 수학적귀납법에 의해 증명끝. 

 

이제 Claim3의 식을 \(f(f(n))=n\)에 대입하여 정리하면 \(r=1\)을 얻는다. 

따라서 구하는 함수는 모든 양의 정수 \(n\)에 대하여 \(f(n)=n\)이다. 

실제로 함수를 조건식에 대입시, 세 변은 \(a, b, a+b-1\)로 삼각부등식이 잘 성립함을 알 수 있다.