Anti-van der Waerden numbers of 3-term arithmetic progressions

Abstract

The \emph{anti-van der Waerden number}, denoted by $aw([n],k)$, is the smallest $r$ such that every exact $r$-coloring of $[n]$ contains a rainbow $k$-term arithmetic progression. Butler et. al. showed that $\lceil {\log }_{3}n\rceil +2\le aw([n],3)\le \lceil {\log }_{2}n\rceil +1$, and conjectured that there exists a constant $C$ such that $aw([n],3)\le \lceil {\log }_{3}n\rceil +C$. In this paper, we show this conjecture is true by determining $aw([n],3)$ for all $n$. We prove that for $7\cdot 3^{m-2}+1\le n\le 21\cdot 3^{m-2}$, \[ aw([n],3)=\left\{\begin{array}{ll} m+2, & \mbox{if $n=3^m$}\\ m+3, & \mbox{otherwise}. \end{array}\right.\]