KöMaL: English issue, December 2002

Order KöMaL!

Competitions Portal

	English Issue, December 2002
	Previous page	Contents	Next page	ORDER FORM

Solutions of problems B

B. 3429. Let $q=\frac{1+\sqrt{5}}{2}$ , and let $f\colon\mathbb{N}\to\mathbb{N}$ be a function, such that for all positive integers n,

$\big|f(n)-qn\big|<\frac{1}{q}.$

Prove that f(f(n))= f(n)+n.

Solution. As $\frac{1}{q}>\big|f(0)\big|$ , obviously f(0)=0. For any other n, the value of f is a positive integer, otherwise f(n)=0<n would imply $\frac{1}{q}>\big|f(n)-qn\big|=|-qn|$ and hence $n<\frac{1}{q^2}<1$ , which is impossible. It is easy to check, furthermore, that $q(q-1)=\frac{\sqrt{5}+1}{2}\cdot\frac{\sqrt{5}-1}{2}=1$ . Thus for any natural number n,

|f(f(n))- f(n)-n| = |f (f(n))- qf(n)+(q-1) f(n)- q(q-1)n| =
= |f (f(n))- qf(n)+ (q-1) (f(n)-qn)|.

As the inequality |a+b| $\le$ |a|+|b| holds for all real numbers a, b, the above absolute value can be at most

|f (f(n))-qf(n)|+ | (q-1) (f(n)-qn)|= |f(f(n))-qf(n)|+ (q-1) |f(n)-qn|,

which is less than $\frac{1}{q}+(q-1)\frac{1}{q}=1$ according to the condition. Hence

|f(f(n))- f(n)-n|<1,

which can only happen if f(f(n))- f(n)-n=0, as f(f(n)), f(n) and n are integers.

G. Bóka, Szolnok

Támogatóink:

ELTE

English Issue, December 2002

Solutions of problems B