Oops this fails.

rafayaashary1 wrote: Clearly by $\pmod{10}$ we must have at least $10$ elements. I claim that $\{1,12,23,34,45,56,67,78,89,100\}$ works. In fact since the common differences must be at most $10$, and that $11a(k+1)+1-a-(11ak+1+a)=9a$, we are done $\Box$ Note that $2,3,...,11$ is an arithmetic progression of length 10, and it does not intersect your set.

yaron235 wrote: rafayaashary1 wrote: Clearly by $\pmod{10}$ we must have at least $10$ elements. I claim that $\{1,12,23,34,45,56,67,78,89,100\}$ works. In fact since the common differences must be at most $10$, and that $11a(k+1)+1-a-(11ak+1+a)=9a$, we are done $\Box$ Note that $2,3,...,11$ is an arithmetic progression of length 10, and it does not intersect your set. In fact it is actually true that $N>10$. Assume that $N=10$. Let the blue numbers be $a_1 < a_2 < ... < a_10$. Then $10(i-1) < a_i \leq 10i$ for every $i$. Moreover $a_i-a_{i-1} \leq 10$ and $a_i \not\equiv a_j \pmod {10}$ for every $i \neq j$, therefore $a_i=9i+1$ for every $i$. But then the sequence $1,12,...,100$ does not contain any blue number. Thus $N>10$

For $N=16$ we can color $10,15,22,29,36,43,53,55,56,57,58,68,73,74,84,91$. We can check this easily, though may be time consuming. I do not know if $N<16$ works.