I thought back to this question, which I think is quite interesting. The poster claimed to have proved the three-term AP case, but this isn't obvious to me. The question:
Let $\sigma:\mathbb{N}\rightarrow \mathbb{N}$ be a permutation of the set $\mathbb{N}$ of all positive integers. Show that there must be an arithmetic progression $a,a+d,a+2d$ where $d>0$ such that $\sigma(a)<\sigma(a+d)<\sigma(a+2d).$
I can prove something easier: if $\ \sigma:\mathbb{N}\to\mathbb{N}\ $ is a bijection (i.e. permuatation), then there is an increasing sequence of integers $\ (x_n)_{n\in\mathbb{N} }\ $ such that $\ \sigma(x_1) < \sigma(x_2) < \sigma(x_3) < \ldots.$
Proof: Let $\ k_1 = \sigma^{\ -1}(1).\ $ Let $\ k_2 = \sigma^{\ -1}(1) + 1.\ $ Then $\ \sigma(k_2) > \sigma(k_1).\ $ By PHP, $\ \exists\ k_3\in [k_2 + 1, k_2 + \sigma(k_2)]\ $ such that $\ \sigma(k_3) > \sigma(k_2),\ $ etc.
But I'm not sure how to prove the above three-term A.P. question. Any hints?
Look at $\sigma(1)$. There's only finitely many $k$ such that $\sigma(k+1) < \sigma(1)$ or $\sigma(2k+1) < \sigma(1)$.
Let $N$ be larger than all those finitely many exceptions. Then either there is some $k \ge N$ such that $\sigma(1) < \sigma(k+1) < \sigma(2k+1)$ - and we're done - or else for all $k\ge N$ we have $\sigma(k+1) > \sigma(2k+1)$.
In the second case, by applying this to $k=N, 2N, 4N, 8N,\dots$ we must have $$ \sigma(N+1) > \sigma(2N+1) > \sigma(4N+1) > \sigma(8N+1) > \dots $$ which is impossible to continue for more than $\sigma(N+1)$ steps. Contradiction!