Number theoryDifficulty 7.4National olympiad, round 2Prove it
6⋅48 Let N={1,2,3,⋯}.
Prove whether there exists a function f:N→N such that f(1)=2f(f(n))=f(n)+nn
for all n∈N, f(n)<f(n+1)
for all n∈N.
Solution
[Solution] Such a function exists. We take α=25+1,β=25−1, clearly α=1+β,αβ=1, let f(n)=[αn+β],n∈N. We prove that f(n) satisfies the conditions f:N→N, and f(1)=[α+β]=[5]=2,f(n+1)f(f(n))=[(n+1)α+β]=[αn+β+α]⩾[αn+β+1]=f(n)+1>f(n).=[α[αn+β]+β]=[αn+β]+[β[αn+β]+β]=f(n)+[β[αn+β]+β].
Clearly, αn+β is not an integer, thus, =β[αn+β]+βn+β2>n.β(αn+β−1)+β
So [β[αn+β]+β]=n. From (1) we get f(f(n))=f(n)+n
Therefore, f(n)=[αn+β] satisfies all the conditions. Note The function f(n) sought is not unique, there are multiple construction forms, such as: (A) f(n)=[25+1n+21]; (B) f(1)=2f(n)=n+max{i<n:f(i)⩽n} 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.