shortlistBMO 2011

It is easy to exhibit such a partition: set $$A_1=\bigcup _{n=1}^{\infty }\{n(2n-1)+1,n(2n-1)+2,\dots ,n(2n-1)+2n\},$$ $$A_2=\bigcup _{n=0}^{\infty }\{n(2n+1)+1,n(2n+1)+2,\dots ,n(2n+1)+2n+1\}.$$ Since each class has arbitrarily large gaps, it cannot contain an infinite arithmetic sequence.

To exhibit such a partition for the further question, we will rely on building a bijection that will allow us to "destroy" every single infinite arithmetic progression, within each of the two partition classes. Take any bijection $$\varphi :\{1,2,\dots \}\to \{1,2\}\times \{1,2,\dots \}\times \{1,2,\dots \}.$$ Define $A(a,r)=\{a+nr:n=0,1,\dots \}$ for $a,r\in \{1,2,\dots \}$; these are all possible infinite arithmetic progressions made of positive integers. At step $s=0$, both classes $A_1,A_2$ are empty. Denote by $v_{s+1}$ the next value to be distributed in the sets of the partition, so at step $s=0$ take $v_1=1$. Now proceed in an algorithmic way.

At step $s\ge 1$, let be $\varphi (s)=(c,a,r)$. There exists a least $k\ge 0$ such that $v_s+k\in A(a,r)$. Put $v_s,v_s+1,\dots ,v_s+k$ alternatively in $A_1,A_2$, starting with the one having the least maximum. If this ends with $v_s+k\in A_c$, then take $v_{s+1}=v_s+k+1$; if not, then force $v_s+k\in A_c$ and put $v_s+k+1$ in the other class, then take $v_{s+1}=v_s+k+2$. Continue with the next step $s+1$.

This ensures that neither of the arithmetic progressions $A(a,r)$ will be contained in any of the two classes $A_1,A_2$, while the differences between pairs of consecutive elements within each class is at most $3$.