Maths Olympiad Prep

Library / /443 of 520

Number theory Difficulty 7.4 National olympiad, round 2 Prove it

648 Let N={1,2,3,}6 \cdot 48 \text { Let } N=\{1,2,3, \cdots\} \text {. }

Prove whether there exists a function f:NNf: N \rightarrow N such that
f(1)=2f(f(n))=f(n)+nn\begin{array}{l} f(1)=2 \\ f(f(n))=f(n)+{ }_{n}^{n} \end{array}

for all nNn \in N,
f(n)<f(n+1)f(n)<f(n+1)

for all nNn \in N.

Solution

[Solution] Such a function exists.
We take α=5+12,β=512\alpha=\frac{\sqrt{5}+1}{2}, \beta=\frac{\sqrt{5}-1}{2}, clearly α=1+β,αβ=1\alpha=1+\beta, \alpha \beta=1, let f(n)=[αn+β],nNf(n)=[\alpha n+\beta], n \in N. We prove that f(n)f(n) satisfies the conditions f:NNf: N \rightarrow N, and
f(1)=[α+β]=[5]=2,f(n+1)=[(n+1)α+β]=[αn+β+α][αn+β+1]=f(n)+1>f(n).f(f(n))=[α[αn+β]+β]=[αn+β]+[β[αn+β]+β]=f(n)+[β[αn+β]+β].\begin{array}{l} f(1)=[\alpha+\beta]=[\sqrt{5}]=2, \\ \begin{aligned} f(n+1) & =[(n+1) \alpha+\beta] \\ & =[\alpha n+\beta+\alpha] \geqslant[\alpha n+\beta+1] \\ & =f(n)+1>f(n) . \\ f(f(n)) & =[\alpha[\alpha n+\beta]+\beta] \\ & =[\alpha n+\beta]+[\beta[\alpha n+\beta]+\beta] \\ & =f(n)+[\beta[\alpha n+\beta]+\beta] . \end{aligned} \end{array}

Clearly, αn+β\alpha n+\beta is not an integer, thus,
β[αn+β]+ββ(αn+β1)+β=n+β2>n.\begin{aligned} & \beta[\alpha n+\beta]+\beta & \beta(\alpha n+\beta-1)+\beta \\ = & n+\beta^{2}>n . \end{aligned}

So [β[αn+β]+β]=n[\beta[\alpha n+\beta]+\beta]=n.
From (1) we get
f(f(n))=f(n)+nf(f(n))=f(n)+n

Therefore, f(n)=[αn+β]f(n)=[\alpha n+\beta] satisfies all the conditions.
Note The function f(n)f(n) sought is not unique, there are multiple construction forms, such as:
(A) f(n)=[5+12n+12]f(n)=\left[\frac{\sqrt{5}+1}{2} n+\frac{1}{2}\right];
(B)
f(1)=2f(n)=n+max{i<n:f(i)n}\begin{array}{l} f(1)=2 \\ f(n)=n+\max \{i<n: f(i) \leqslant n\} \end{array}
The functions constructed by (A) and (B) can both be verified to satisfy the conditions given in the problem.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.