170128 함수방정식

미국 가는 비행기에서 친구와 푼 문제이다. 각자 발견한 아이디어를 합쳐보니 꽤 재밌는 풀이가 나와 포스팅해본다.

$$ \text{ Find all function } f : \mathbb{N} \to \mathbb{N} \text{ s.t. } \\ \forall a,b\in \mathbb{N} (f(a)+b)\cdot 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\in A\)에 대해 \(x+y \in A\)임을 쉽게 보일 수 있다. \(\cdots (*)\)

(step 2)

\(a+f(a)\)는 부동점이므로 이를 활용해 보자.

\(P(a, a+f(a)) : f(2a+f(a)) = \frac{[2a+f(a)]^2}{a+2f(a)}\)

따라서 \(a + 2f(a) | (2a+f(a))^2 \)이고, 식을 정리하면 \(a + 2f(a) | 9a^2\)이다.

따라서 a에 1을 대입하면 \(1+2f(1) | 9\)이고, 이로부터 \(f(1) = 1 \vee 4\)이다.

(step 3)

\(f(1) = 1\)인 경우, 재귀적으로 모든 \(k\in \mathbb{N}\)에 대해 \(f(2^k) = 2^k\)임을 보일 수 있다. 이 때 모든 수는 이진법으로 나타낼 수 있으므로, \((*)\)에 의해 \(f(x) = x\)가 되고, 이는 주어진 함수방정식을 만족한다.

(step 4)

\(f(1) = 4\)인 경우, 마찬가지로 모든 \(k \in \mathbb{N}\) 에 대해 \(f(5 \cdot 2^k) = 5 \cdot 2^k\)임을 알 수 있다. 즉, \(A\)는 무한집합이다.

이 때, 적당한 \(A\)의 원소 \(p\)를 잡자.

\(P(p,1) : (p+1)\cdot f(p+4) = (p+4)^2 \)

이 때 \(p+1 | (p+4)^2 \Rightarrow p+1 | 9\)인데, \(p\)의 값이 8보다 커지면 모순. 따라서 조건을 만족하는 해는 \(f(x) = x\) 뿐이다. \(\blacksquare\)