미국 가는 비행기에서 친구와 푼 문제이다. 각자 발견한 아이디어를 합쳐보니 꽤 재밌는 풀이가 나와 포스팅해본다.
Find all function f:N→N s.t. ∀a,b∈N(f(a)+b)⋅f(a+f(b))=(a+f(b))2
(step 1)
P(a,a):f( a +f(a) )=a+f(a)
즉, x+f(x)꼴로 나타내어 지는 수들은 모두 부동점이다.
f의 부동점들의 집합을 A라고 하자.
그렇다면 x,y∈A에 대해 x+y∈A임을 쉽게 보일 수 있다. ⋯(∗)
(step 2)
a+f(a)는 부동점이므로 이를 활용해 보자.
P(a,a+f(a)):f(2a+f(a))=a+2f(a)[2a+f(a)]2
따라서 a+2f(a)∣(2a+f(a))2이고, 식을 정리하면 a+2f(a)∣9a2이다.
따라서 a에 1을 대입하면 1+2f(1)∣9이고, 이로부터 f(1)=1∨4이다.
(step 3)
f(1)=1인 경우, 재귀적으로 모든 k∈N에 대해 f(2k)=2k임을 보일 수 있다. 이 때 모든 수는 이진법으로 나타낼 수 있으므로, (∗)에 의해 f(x)=x가 되고, 이는 주어진 함수방정식을 만족한다.
(step 4)
f(1)=4인 경우, 마찬가지로 모든 k∈N 에 대해 f(5⋅2k)=5⋅2k임을 알 수 있다. 즉, A는 무한집합이다.
이 때, 적당한 A의 원소 p를 잡자.
P(p,1):(p+1)⋅f(p+4)=(p+4)2
이 때 p+1∣(p+4)2⇒p+1∣9인데, p의 값이 8보다 커지면 모순. 따라서 조건을 만족하는 해는 f(x)=x 뿐이다. ■