Let be a strictly increasing function, such that and are both arithmetic progressions in . Show that itself is an arithmetic progression.
Consider set . We claim that this set is bounded, thus finite.
It is bounded below by by the strict monotonicity. If it was not bounded from above, we have . Now, since and that is strictly increasing, Thus This is impossible because Thus is bounded, and thus finite.
We claim that . If , for large enough, we must have , which contradicts the monotonicity of . If , we then have which is unbounded for . But we know that which is bounded. This is a contradiction. Thus .
Apply to both sides of , we have
Consider the minimal element of , let it be , attained at . Let and in , we thus have $f(a\eta +a+b)=af(\eta+1)+b=af(\eta)+a\mu+b.$
Because is the minimal element of , it is thus necessary that In particular, the equality is attained if and only if Let Thus equality IS attained and we must have .
Recall that , letting in the problem’s condition gives and Since that implies
Let the maximal element of be , and repeat the same argument above, we would also have . Thus is a single-element set, or, the difference is a constant for all . This proves the statement.
Comment: Superficial investigation can only lead one to and , and it becomes difficult to move on from here as one has to disentangle the iteration of the function. The problem only gives very limited information about the values attained by , and the information accumulate near the range of the iteration. We see that this range is in general not the same as , and thus we have to find an argument to integrate the scattered local information. The definition of and plays this role by interacting directly with the function values elsewhere (considering s values and differences between two consecutive terms, where the ‘equality of the global inequality implies all local equalities’ is really the fruit of the global consideration in defining ).
After knowing that implies , iterating the linear function to try to give a full description of the set of positive integers on which the consecutive difference is minimalised is a natural idea — but turns out uneconomical: it is not clear how to force the subset that minimalise the consecutive difference and the subset that maximises the difference to intersect in that manner. In fact if that could be done the second problem condition becomes unused in deriving the solution–uncommon for Olympiad problems. Thus we seek to show that the subset of on which the consecutive difference is minimised (maximised) intersects the image of instead, which is already done.
I reckon this problem is quite nice (except its original formulation in terms of sequences which uses sub-sub-scripts which is painful to read), as one does not have access to any function value at any point (thus avoiding some ad hoc phenomena) but instead requires conceptual consideration. It is impossible to gauge the consideration of the function with any non-trivial solution, as there isn’t any.
When the functional equation acts on integer sets, it is almost always (practically, the ‘almost’ is redundant in Olympiads) important to consider properties characteristic of integers (extremal elements, number theory, discreteness, etc.) as if a solution without these considerations is possible the problem proposer would just define it on a wider domain. Because direct comparison of values maybe impossible, it might also be useful to consider asymptotic behaviours of certain auxiliary functions to gain information about parameters (here the proof that .)
The problem is proposed by Gabriel Carroll, USA, and appeared in the IMO 2009 as Q3.