For any $f:\mathbb{Z_+}\to \mathbb{Z_+}$ there exist $f(a)\le f(a+b)\le f(a+2\cdot b)$

Question

I am preparing for the USAJMO, however I got stuck on the following question. I would really appreciate any help/hint.

For any function ( not necessarily having Bijectivity ) $f:\mathbb{Z^+} \to \mathbb{Z^+}$ :
Prove that there exist positive integers $a$ and $b$ so that $f(a) \le f(a+b) \le f(a+2 \cdot b)$.

I can prove it pretty easily if $f$ is a monotonically increasing/decreasing function. However I have no clue how to prove the general case where $f$ is not necessarily monotonic. Any help is appreciated.

OP thinking :
A point I already got : monotonically decreasing function must have a lower bound, .... so if it is eventually from some value $f(x)$ must be the lowest value onwards ....
But I am not so sure when/if function $f$ values change up/down all the time ....

Answer 1

When Domain & range are Positive Integers , there must be some minimum value of $f$ , which we can use.
Let that minimum occur first at $a$.

(CASE A) When that minimum occurs again later at $a+b$ , then we have what we wanted : $f(a) = f(a+b) \le f(a+2b)$ : we do not have to worry about the value at $a+2b$ , because it can not be less than the minimum.

(CASE B) When that minimum never occurs again , then we have more work to try out.

ALGORITHM :
Let us take $b = b_1 = 1$ , then $f(a) \lt f(a+b_1)$ according to the Criteria for our Case.
Check the value $f(a+2b_1)$ :
(CASE B1) If it is $f(a+b_1) \le f(a+2b_1)$ , then we have what we wanted : $f(a) \lt f(a+b) \le f(a+2b)$ where $b=b_1$ : we can terminate our algorithm.
(CASE B2) If it is $f(a+b_1) \gt f(a+2b_1)$ , then we do not yet have what we wanted.
Consider the value $c_1 = f(a+2b_1) - f(a)$
We will update $b_2=2b_1$ ( In general , $b_{n+1}=2b_{n}$ ) & then we go back to algorithm with the new value of $b$.
We know that algorithm will eventually terminate & we will eventually get the $b_n$ because $c_1 \gt c_2 \gt c_3 \gt c_4 \gt c_5 \gt \cdots \gt 0$ is impossible : In very iteration of the algorithm , $c_n$ , which is the gap between $f(a)$ & $f(b)$ , is reducing & that gap will go to $0$ eventually.
When the algorithm terminates , we will have $f(a) \lt f(a+b_{n}) \le f(a+2b_{n})$ where $b = b_{n}$

VISUALIZATION :

CASE B2 will look like this :

Here , the yellow lines indicate the gaps which are reducing. The gaps can not reduce arbitrarily & must eventually reduce to $0$ & the algorithm must terminate with CASE B1.

Answer 2

What about this:
Let $S$ be the image of $f$. By the well-ordering principle, it has a minimum element, say $f(a)$. Pick the smallest such value of $a$. Then if $f(a+b) = f(a)$ for some $b>0$, we are done. Otherwise, let $S = \mathrm{Im}(f) - \{f(1),f(2),\ldots , f(a)\}$. Note that $S$ is non-empty. Again, we can take $f(a+b)$ which is the smallest value in $S$. Pick the smallest such value of $b$. Then, $f(a+2b)\ge f(a+b)$. Thus: $$\boxed{f(a)\le f(a+b)\le f(a+2b)}$$