ComplexPhi wrote: Can we partition the positive integers in two sets such that none of the sets contains an infinite arithmetic progression of nonzero ratio ? Yes. Let $f(x)$ from $\mathbb Z_{>0}\to\mathbb Z_{\ge 0}$ defined as : $f(1)=0$ $f(\prod p_i^{n_i})=\sum{n_i}$ Let $A=\{x\in\mathbb Z_{>0}$ such that $f(x)$ is even$\}$ Let $B=\{x\in\mathbb Z_{>0}$ such that $f(x)$ is odd$\}$ Let any arithmetic progression $\{u+nr\}_{n\in\mathbb Z_{\ge 0}}$ with $u,r\in\mathbb Z_{>0}$ Dirichlet theorem claims that it exists infinitely many prime numbers in the sequence $1+kr$ Let $p=1+mr$ such a prime number Then $f(u+mur)=f(pu)=1+f(u)$ and so $u+mur$ and $u$ are not in the same set And so no infinite non constant AP may be in the same set. Q.E.D.

I will present an absolutely unintuitive construction,as follows. Define $f:\mathbb Z_{>0}\to\mathbb Z_{>0}$ as: $f(1)=1$ $f(\prod p_i^{n_i})=\frac{\prod p_i^{n_i}}{p}$,where $p$ is the largest prime in the product. Consider the function $g(x)$,defined by the number of times $f(x)$ appears in the multiset $f(1),f(2),...,f(n)$. By taking numbers $xp$ with $p$ prime and $p>x$,we get $f(xp)=x$;since there are an infinite number of primes greater than a given $x$,we get that the set $A_x$=$\{y \in \mathbb Z_{>0}|f(y)=x\}$ is infinite;we order its elements in increasing order,and label them using a function $ h:(\mathbb Z_{>0})^2\to\mathbb Z_{>0}$:$A_x=\{h(x,1),h(x,2),...\}$.Notably,$h$ is bijective;this is easy to prove. Now we define yet another function $g:\mathbb Z_{>0}\to\mathbb Z_{>0}$ as $g(h(i,j))=j$ for every pair $(i,j)$ in $(\mathbb Z_{>0})^2$;by bijectivity of $h$ our function $g$ is properly and fully defined. It is time to define our two partitions,name them $A$ and $B=\mathbb Z_{>0}- A$. Let $y_n$ be defined as follows: $y_1=1$ $y_n$ is the smallest number for which $y_n>2y_{n-1}$ and $y_n \equiv g(n)$ $mod$ $f(n)$ hold. Now we simply take $A=(y_n)_{n>0}$.Because $y_n$ is strictly increasing and $y_{n+1}-y_n$ is also strictly increasing,trivially we cannot have any arithmetic progressions in $A$. If any such progression existed in $B$,then let its 1st term be $m$ and its ratio be $r$;we take $q$ to be $m$'s residue mod $r$.Now every term of our sequence has to be $q$ mod $r$,thus every natural number that is $q$ mod $r$ and $\ge m$ has to be in $B$.But by taking the sequence $z_n=y_{h(r,r+nq)}$ we get that this sequence is unbounded and that $z_n \equiv q(mod r)$;this last claim follows from the definition of the sequences $y$ and $z$. But the sequence $z_n$ is fully part of $A$,yet it also has to have terms in $B$ due to its unboundedness,contradiction. So neither $A$ nor $B$ contain any arithmetic sequence,Q.E.D.

Partion it like this:First number is in $A$,two next numbers are in $B$,$3$ next numbers are in $A$,etc($abbaaabbbbaaaaa...$)...Denote A1,A2,... numbers in $A$ and B1,B2,... in $B$.The cruial thing is that we want that there exist an arbirtary large difference A(i+1)-Ai and B(i+1)-Bi,cause if the difference of the proggresion is $d$,it will fail cause it must have two elements which differ by at least an arbirtary large number for some A(i+1)-Ai.The above partition clearly satisfayes this.

http://artofproblemsolving.com/community/c6h553495

Really? Just take $A=\{(2)(4,5)(8,9,10,11)...\}$ $B=\{(3)(6,7)(12,13,14,15)...\}$