\documentclass[12pt]{article}
\usepackage{latexsym} 
\usepackage{amsfonts} 
\textwidth= 6.25in
\textheight= 9.0in
\topmargin = -10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9 
\usepackage{amsfonts,amsmath,latexsym,color,epsfig}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{question}{Question}
\newtheorem{claim}{Claim}
\newtheorem{problem}{Problem}
\newcommand{\definition}
      {\medskip\noindent {\bf Definition:\hspace{0em}}}
\newcommand{\remark}
      {\medskip\noindent {\bf Remark:\hspace{0em}}}
\newenvironment{proof}
      {\medskip\noindent{\it Proof.}\hspace{1mm}}
      {\hfill$\Box$\medskip}
\newenvironment{proofof}[1]
      {\medskip\noindent{\bf Proof of #1:}\hspace{1mm}}
      {\hfill$\Box$\medskip}
%\input{epsf}
%usage: \fig{LABEL}{FIGURE-SIZE}{CAPTION}{FILENAME}
%\newcommand{\fig}[4]{
%	\begin{figure}
%        \setlength{\epsfysize}{#2}
%	\vspace{3mm}
%        \centerline{\epsfbox{#4}}
%        \caption{#3} \label{#1}
%	\end{figure}
%        }
\def\rados{Radoi\v ci\'c}
\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}
\def\I{\mathcal {I}}
\def\J{\mathcal {J}}
\def\qed{\ifvmode\mbox{ }\else\unskip\fi\hskip 1em plus 10fill$\Box$}


\begin{document}

\begin{center}
{\bf RAINBOW 3-TERM ARITHMETIC PROGRESSIONS}
\vskip 20pt
{\bf Veselin Jungi\'c}\\ 
{\smallit Department of Mathematics, Simon Fraser
University, Burnaby, B.C., Canada}\\
{\tt vjungic@sfu.ca}
\vskip 20pt
{\bf Rado\v{s} \rados}\\ 
{\smallit Department of Mathematics, MIT,
Cambridge, MA 02139, U.S.A.}\\
{\tt rados@math.mit.edu}
\end{center}
\vskip 30pt
\centerline{\smallit Received: 8/7/03, Revised: 11/17/03,
Accepted: 11/20/03, Published: 11/20/03}
\vskip 30pt 

\centerline{\bf Abstract}

\noindent Consider a coloring of $\{1, 2, \ldots, n\}$ in $3$ colors, where $n \equiv 0\pmod 3$.  
If all the color classes have the same cardinality, then there is a
$3$-term arithmetic progression whose elements are colored in distinct colors.
This rainbow variant of van der Waerden's theorem proves the conjecture of the
second author.

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC
JOURNAL OF COMBINATORIAL NUMBER
THEORY \smalltt 3 (2003), \#A18\hfill}

\thispagestyle{empty} 
\baselineskip=15pt 
\vskip 20pt


\section*{\normalsize 1. Introduction}

Given a coloring of a set of natural numbers, we say that a subset is
{\em monochromatic} if all of its elements have the same color and we say that
it is {\em rainbow} if all of its elements have distinct colors. 
A classical result in Ramsey theory is van der Waerden's theorem \cite{vW27},
which states
that for every $k$ and $t$ and sufficiently large $n$, every $k$-coloring of
$[n]:=
\{ 1, 2, \ldots, n\}$ contains a monochromatic arithmetic progression of length
$t$. Jungi\'c et. al. \cite{JLMNR} considered, for the first time in the literature,
a rainbow
counterpart of van der Waerden's theorem.  They proved that every $3$-coloring
of the set of natural numbers $\N$ with the upper density of each color greater
than $1/6$ contains a rainbow AP(3).  They also
asked whether the ``finite'' version of their theorem also holds, and,
backed by the computer evidence ($n \le 56$), posed the following
conjecture.

\begin{conjecture}
\label{strongconj}
For every $n\ge3$, every partition of $[n]$ into three color classes $R$, $G$,
and $B$
with $\min(|R|,|G|,|B|) > r(n)$, where
\begin{equation}
\label{defr}
r(n) := \left\{\begin{array}{ll}
\lfloor(n+2)/6\rfloor & \mbox{ if }n\not\equiv2\pmod6\\
(n+4)/6 & \mbox{ if }n\equiv2\pmod6\end{array}\right.
\end{equation}
contains a rainbow $AP(3)$.
\end{conjecture}

Moreover, they constructed a $3$-coloring of $[n]$ with  
$\min(|R|, |G|, |B|) = r(n)$, where $r$ is the function defined in (\ref{defr}),
that contains no rainbow $AP(3)$. This shows that Conjecture \ref{strongconj},
if true, is the best possible.

A weaker form of this conjecture, due to the second author, was 
posed at the open problem session of the 2000 MIT Combinatorics Seminar \cite{JLMNR}.

\begin{conjecture}
\label{radosconj}
Let $n \equiv 0\pmod 3$. For every equinumerous $3$-coloring of $[n]$, that is,
a coloring in which
all color classes have the same cardinality, there exists a rainbow $AP(3)$.
\end{conjecture}

In this paper, we prove Conjecture~\ref{radosconj}.

\section*{\normalsize 2. Proof of Conjecture~\ref{radosconj}}

Given a $3$-coloring of $[n]$ with colors Red ($R$), Green ($G$) and Blue ($B$),
a $B$-{\em block} is a string of consecutive
elements of $[n]$ that are colored Blue. $R$-block and $G$-block are defined
similarly.  We say that the coloring is {\em rainbow-free} if it contains no
rainbow $AP(3)$.

First, we show that every rainbow-free 3-coloring contains a {\em dominant
color}, that is, a color $z\in \{ B,G,R\}$ such that for every two consecutive
numbers that are colored with different colors, 
one of them is colored with $z$.  We will need the following two lemmata.

\begin{lemma}\label{1}
Let $c:[n]\to \{B,G,R\}$ be a $3$-coloring of $[n]$ such that every two
different 
colors appear next to each other. Then there exist $p, r\in [n]$, $p<r$, such
that 
\begin{enumerate}
\item $c(p)=c(r)$,
\item $c(p+1)\not= c(p)$,
\item $c(r-1)\not\in \{c(p),c(p+1)\}$, and
\item no element in the interval $[p+1, r-1]$ is colored by the color $c(p)$.
\end{enumerate}
\end{lemma}
\begin{proof}
Let $G$ be the first color to appear and let the first $G$-block be followed
by an $R$-block. Since $G$ appears next to $B$, there exists a $G$-block that is next to
a $B$-block.
If this $G$-block is preceded by a $B$-block,

{\small 
$$\begin{array}{rccclc}
G\ldots G&R\ldots R& \ldots &B\ldots B&G\ldots G&\ldots \\
\uparrow &&&&\uparrow & \\
p&&&&r&\\
\end{array}
$$
}then the lemma follows. So, suppose that ${\mathcal {G}}$, the first $G$-block that
is next to a $B$-block, is preceded by an $R$-block and followed by a $B$-block 
${\mathcal {B}}$. {\small
$$\begin{array}{ccccccc}
G\ldots G&R\ldots R& \ldots &R\ldots R&G\ldots G&B\ldots B&\ldots \\
&&&&\uparrow &\uparrow &\\
&&&&{\mathcal {G}} & {\mathcal {B}} &\\

\end{array}
$$
}


Suppose there is a $B$-block between the two $G$-blocks. Consider the last such $B$-block and denote it by ${\mathcal
{B}}'$. The lemma immediately
follows, since we can take $p$ and $r$ to be the last element of ${\mathcal
{B}}'$
and the first element of ${\mathcal {B}}$.  

Now, suppose there is no $B$-block between the two $G$-blocks.

If ${\mathcal {B}}$ is followed by an $R$-block, then the lemma clearly follows. 
So, let ${\mathcal {B}}$ be followed by a $G$-block. The same reasoning as
above, combined with the assumption that $R$ appears next to $B$, implies that
one
of the following two scenarios happens:

{\small
$$\begin{array}{ccrccl}
\ldots &G\ldots G&R\ldots R&G\ldots G&B\ldots B&R\ldots R\\
\uparrow&&\uparrow &&&\uparrow \\
{\mathcal {G}}{\mathcal {B}}&&p&&&r\\
\end{array}
$$
}or
{\small
$$\begin{array}{ccrccl}
\ldots &G\ldots G&B\ldots B&G\ldots G&R\ldots R&B\ldots B\\
\uparrow&&\uparrow &&&\uparrow \\
{\mathcal {G}}{\mathcal {B}}&&p&&&r\\
\end{array}
$$
}which completes the proof. 
\end{proof}

\begin{lemma}\label{2}
Let $c:[n]\to \{B,G,R\}$ be a $3$-coloring of $[n]$ such that 
$$\min \{ |c^{-1}(B)|,|c^{-1}(G)|,|c^{-1}(R)|\} \geq 5$$
and every two different colors appear next to each other. 
Then there is a rainbow $AP(3)$.
\end{lemma}
\begin{proof}
By  Lemma 1, we can assume that there are $p$, $q$, $r$, such that

{\small
$$\begin{array}{cccccccc}
\ldots &G&R& \ldots &R&B\ldots B&G&\ldots \\
 &\uparrow && \uparrow  &\uparrow & \uparrow&\uparrow & \\
 &p&& R/B   &q &B&r& \\
 &&&  \mbox{ only}  & &\mbox{ only}&& \\
\end{array}
$$
}

If $q=p+1$ or $q=r-2$ we are done. So, we assume that  $p+2 \le q < r-2$, $c(p) = G$, $c(p+1) = R$, $c(q) = R$, $c(r) = G$, 
$c(i) = B$ for all $q < i < r$ and $c(j) \not= G$ for all $p+1 < j < q$.
Since $|c^{-1}(G)|\geq 5$, then $p\geq 3$ or $r\leq n-2$. Without loss of
generality, assume $p\geq 3$.\footnote{Otherwise, consider the coloring
$c':[n]\to \{B,G,R\}$, defined by $c'(i)=c(n-i+1)$ for every $i \in [n]$.}
If $r+q$ is even, then $q$, $\frac{r+q}{2}$, $r$ is a rainbow $AP(3)$.
So, let $r+q$ be odd. It follows that an even number of elements between
$q$ and $r$ are colored by $B$. If $c(q-1)=R$ then $q-1$, $\frac{r+q-1}{2}$,
$r$ is a rainbow $AP(3)$.
Let $c(q-1)=B$ and let $s=\min \{i\in[p,q]|c(i)=B\}$. 
Then, 

{\small
$$\begin{array}{cccccccccc}
\ldots &G&R\ldots R&B& \ldots &B&R&B\ldots B&G&\ldots \\
 &\uparrow &\uparrow &\uparrow &\uparrow &&\uparrow & \uparrow &\uparrow & \\
 &p&\mbox{only } R&s&R/B&&q&\mbox{only } B&r& \\
 &&&&&&&\mbox{even}\# && \\
\end{array}
$$
}

Notice that $s$ could be equal to $q-1$. 
Now, if $p+s$ is even, then $p$, $\frac{p+s}{2}$, $s$ is a rainbow
$AP(3)$.  Otherwise, an even number of elements between $p$ and $s$ are colored
by $R$. If $c(p-1) = G$, then $p-1$, $\frac{p+s-1}{2}$, $s$ is a rainbow
$AP(3)$.
So, let $c(p-1) = R$. If $c(s+1) = B$ (here, $s \not= q-1$), then $p$,
$\frac{p+s+1}{2}$, $s+1$ is a rainbow $AP(3)$.  Hence, let $c(s+1) = R$.  
Then, the interval $[p-1, r]$ is colored as follows. 

{\small
$$\begin{array}{cccccccccccc}
\ldots&R &G&R\ldots R&B&R& \ldots &B&R&B\ldots B&G&\ldots \\
 &\uparrow&\uparrow &\uparrow&\uparrow&\uparrow& &  &\uparrow &
\uparrow&\uparrow & \\
 &p-1&p&\mbox{only } R&s&s+1&&    &q &\mbox{only } B&r& \\
 &&&\mbox{even} \# &  & & & &&\mbox{even} \# & \\
\end{array}
$$
}

Suppose that $p+r-1$ is even. If $c(\frac{p+r-1}{2})=R$, then
$p$, $\frac{p+r-1}{2}$, $r-1$ is a rainbow $AP(3)$. If $c(\frac{p+r-1}{2})=B$,
then $p-1$, $\frac{p+r-1}{2}$, $r$ is a rainbow $AP(3)$.

So, let $p+r-1$ be odd. If $c(p-2)= B$ then $p-2, p-1, p$ is a
rainbow
$AP(3)$.  Suppose $c(p-2) = R$.  If $c(\frac{p+r-2}{2})=R$, then $p$,
$\frac{p+r-2}{2}$, $r-2$ is a rainbow $AP(3)$. If $c(\frac{p+r-2}{2})=B$, then
$p-2$, $\frac{p+r-2}{2}$, $r$ is a rainbow $AP(3)$. Hence, the only remaining
case
is when $c(p-2)=G$.

{\small
$$\begin{array}{ccccccccccccc}
\ldots&G&R&G&R\ldots R&B&R& \ldots &B&R&B\ldots B&G&\ldots \\
 &\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&&&\uparrow &
\uparrow&\uparrow & \\
 &p-2&p-1&p&\mbox{only} R&s&s+1&&&q&\mbox{only} B&r& \\
 &&&&\mbox{even} \# &  & & & &&\mbox{even} \# && \\
\end{array}
$$
}

Since an even number of elements between $q$ and $r$ are colored by $B$, there
exists $k$, $2\leq k < \frac{r-p}{2}$, such that 
$c(p+2k)=B$. Suppose that $k$ is the smallest number with this property. Now,
consider elements $\frac{p+p+2k}{2}=p+k$ and $\frac{p-2+p+2k}{2}=p+k-1$. By
the property of $k$ and the fact that one of the elements $k, k-1$ is even, we
conclude that either $c(p+k)=R$ or $c(p+k-1)=R$. Then, either $p-2$, $p+k-1$,
$p+2k$ or
$p$, $p+k$, $p+2k$ is a rainbow $AP(3)$.
\end{proof}

Lemma~\ref{2} immediately implies
\begin{corollary}\label{dominant}
Let $c:[n]\to \{B,G,R\}$ be a rainbow-free $3$-coloring of $[n]$ such that 
$$\min \{ |c^{-1}(B)|,|c^{-1}(G)|,|c^{-1}(R)|\} \geq 5.$$
Then there exists a dominant color.
\end{corollary}

\vskip -12pt
Clearly, there can be only one dominant color
\vskip -3pt
The following lemma will be instrumental in showing that in every rainbow-free
$3$-coloring of $[n]$ there exists a {\em recessive color}, that is, a color
$w\in
\{ B,G,R\}$ such that no two consecutive numbers are colored by $w$. 

\begin{lemma}\label{3}
Let $c:[n]\to \{B,G,R\}$ be a $3$-coloring of $[n]$ such that 
$R$ is the dominant color.  Suppose there exist $i$ and $j$, so that  
$i+2<j$, $c(i)=c(i+1)=B$, $c(i+2)=c(j-1)=R$, $c(j)=c(j+1)=G$. Suppose also that the 
interval $[i+2, j-1]$ does not contain two consecutive elements that are both
colored by $B$ or by $G$. Then, there is a rainbow $AP(3)$.
\end{lemma} 
\vskip -10pt
\begin{proof}
Suppose there exists a rainbow-free coloring $c$ with the
properties above. Consider the interval $[i, j+1]$. \vskip -20pt
{\small
$$\begin{array}{llcccll}
\ldots & BB&R&\ldots &R&GG&\ldots \\
 & \uparrow &\uparrow &\uparrow &\uparrow &\uparrow &  \\
 & i &i+2 &\mbox{no }BB, \mbox{ no }GG&j-1 &j &  \\
\end{array}
$$
}

Suppose no element of $[i+3, j-2]$ is colored by $R$. Since $R$ is the
dominant color, $[i+3, j-2]$ is either a $B$-block or a $G$-block.  Then, either 
$i+1$, $i+2$, $i+3$ or $j-2$, $j-1$, $j$ is a rainbow $AP(3)$, contradicting the
assumption
that $c$ is rainbow-free.  

Suppose no element of $[i+3, j-2]$ is colored by $G$. Since $c(j) = G$
and $c(j-1) = R$, then $c(j-2) = R$. Since $c(j+1) = G$ and $c(j-1) = R$, then
$c(j-3) = R$. Iterating this reasoning from right to left, we conclude that
$[i+2, j-1]$
is an $R$-block.  Then, clearly, there exists a rainbow $AP(3)$, and, thus, we
arrive at a contradiction.  A symmetric argument shows that at least one of
the elements of $[i+3, j-2]$ is colored by $B$. 

Therefore, there is at least one element of each color in $[i+3, j-2]$.

Suppose $i+j+1$ is odd. Since $R$ is the dominant color and there are no
consecutive elements in $[i+3, j-2]$ both colored by $B$ or by $G$, at least
one of the
elements $\left\lfloor \frac{i+j+1}{2}\right\rfloor$, $\left\lfloor
\frac{i+j+1}{2}\right\rfloor +1$ is colored by $R$.  This implies that one of
the arithmetic progressions 
$$
%\begin{array}{ccc}
%i,&\frac{i+j}{2}=\left\lfloor \frac{i+j+1}{2}\right\rfloor ,&j\\
%i+1,&\frac{i+j+2}{2}=\left\lfloor \frac{i+j+1}{2}\right\rfloor +1,&j+1\\
%\end{array}
i,\frac{i+j}{2}=\left\lfloor \frac{i+j+1}{2}\right\rfloor ,j \mbox{\,\,\,\,
or\,\,\,\, } i+1,\frac{i+j+2}{2}=\left\lfloor \frac{i+j+1}{2}\right\rfloor +1,j+1
$$
is a rainbow $AP(3)$. 

Therefore, if $c$ is rainbow-free then $i+j+1$ is even. It follows that $c\left( \frac{i+j+1}{2}\right) \not= R$,
otherwise, $i$, $\frac{i+j+1}{2}$, $j$ is a rainbow $AP(3)$.

If there exists $i+2<k< \frac{i+j+1}{2}$, with $c(k) = G$, then $c(2k-i)
\not= R$ and $c(2k-i-1) \not= R$, otherwise $i$, $k$, $2k-i$ or $i+1$, $k$,
$2k-i-1$ is a rainbow $AP(3)$. Since $R$ is the dominant color, it follows that
$2k-i$ and $2k-i-1$ are both colored by $B$ or by $G$, which contradicts the
assumed property of $i$ and $j$. Therefore, if $c(k)=G$, where $i+2<k<j-1$, then
$k\geq  \frac{i+j+1}{2}$.
\vskip -5pt
A symmetric argument implies that if $c(k)=B$, $i+2<k<j-1$, then $k\leq 
\frac{i+j+1}{2}$.
\vskip -5pt
Without loss of generality, assume that $c\left( \frac{i+j+1}{2}\right) = G$,
the other case being symmetric.  Then, interval $[i, j+1]$ is colored as
follows.
{\small
$$\begin{array}{llcccccll}
\ldots & BB&R&\ldots &RGR&\ldots &R&GG&\ldots \\
 & \uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &  \\
 & i &i+2 &\mbox{no } BB &\frac{i+j+1}{2}&\mbox{no } GG &j-1 &j &  \\
&  & &\mbox{no } G&&\mbox{no } B & & &  \\
\end{array}
$$
}Hence, there are no elements colored by $G$ in $[i, \frac{i+j-1}{2}]$ and
there are no elements colored by $B$ in $[\frac{i+j+1}{2}, j+1]$. 
Since an element of each color appears in $[i+2, j-1]$, there exists $p\geq2$
such that 
$c\left( \frac{i+j+1}{2}-l\right) = R$ for all $l\in [1,p]$ and $c\left
( \frac{i+j+1}{2}-p-1\right) = B$.  Moreover, since $c$ is rainbow-free, $p$
must be even.  It follows that $c\left( \frac{i+j+1}{2}+p+1\right) = G$.
%
%{\small
%$$\begin{array}{lcclcrccl}
% BB&R&\ldots &BR\ldots&RGR&\ldots G&\ldots &R&GG \\
% \uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow
%&\uparrow  \\
% i &i+2 &\mbox{single } B
%\mbox{s}&\frac{i+j+1}{2}-p-1&\frac{i+j+1}{2}&\frac{i+j+1}{2}+p+1&\mbox{single }
%G \mbox{s} &j-1 &j   \\
% & &\mbox{no } G \mbox{s}&&&&\mbox{no } B \mbox{s} & &   \\
%\end{array}
%$$
%}

Let $x= \frac{i+j+1}{2}-p-1$ and $y= \frac{i+j+1}{2}+p+1$.
Define intervals $\I _s = [a_s, b_s]$, $\J _{s} = [c_{s}, d_{s}]$, $s \in [0,
r-1]$,
where $a_s = i + 2(sp + s + 1)$, $b_s = i + 2((s+1)p+s) + 1$, $c_{s} = j -
2((s+1)p
+ s)$, $d_s = j - 2(sp + s + 1) + 1$, and $r$ is the smallest index such
that 
$1 \le c_{r-1} - y = x - b_{r-1} \le 2p$. 
Notice that the number of elements in each of these intervals is $2p$.

For each $l \in [p]$, the following two arithmetic progressions
$$\begin{array}{ccc}
i,&\frac{i+j+1}{2}-l,&i+j+1-2l-i=j-2l+1\\
i+1,&\frac{i+j+1}{2}-l,&i+j+1-2l-i-1=j-2l\\
\end{array}
$$
are not rainbow only if both $j-2l$ and $j-2l+1$ are red. 
Hence, $\J _0$ is an $R$-block.  This implies that $\I _0$ is an $R$-block,
since
$c(\frac{i+j+1}{2}) = G$ and $c$ is rainbow-free.
Since $\I _0$ is an $R$-block and $c(x) = B$, we conclude that $\J _1$ is an
$R$-block.
This, in turn, implies that $\I _1$ is an $R$-block, since $c(\frac{i+j+1}{2}) =
G$.
Iterating this argument, we conclude that all the intervals $\I _s$, $\J _s$,
$s \in [0, r-1]$, are $R$-blocks. 
We have the following two cases.
\begin{itemize}
\item {\bf Case 1.} $2 < c_{r-1} - y = x - b_{r-1} \le 2p.$
In this case, $y + 2p + 2 \in \J _{r-1}$ and $x$, $y$, $y + 2p + 2$ is a rainbow
$AP(3)$,
contradicting our assumption that $c$ is rainbow-free.

\item {\bf Case 2.} $c_{r-1} - y = x - b_{r-1} = 1$ or $c_{r-1} - y = x -
b_{r-1} = 2.$
In this case, $x - p - 1 \in \I _{r-1}$ and $x - p - 1$, $x$, $\frac{i+j+1}{2}$
is a
rainbow $AP(3)$, thus, arriving at a contradiction.
\end{itemize}
Therefore, $c$ cannot be rainbow-free.
\end{proof}

\begin{corollary}\label{recessive}
Let $c:[n]\to \{B,G,R\}$ be a rainbow-free $3$-coloring of $[n]$ such that 
$R$ is the dominant color.  Then, either $B$ or $G$ is a recessive color.
\end{corollary}
\begin{proof}
Suppose that neither $B$ nor $G$ is a recessive color. 
Then, among all pairs of elements $(i, j)$, such that 
$c(i)=c(i+1)=B$ and $c(j)=c(j+1)=G$, choose the one where $|j-i|$ is minimal.
Without loss of generality, assume that $i+2 < j$.
Then, by the choice of $i$ and $j$, $c(i+2) = R$, $c(j-1) = R$ and 
interval $[i+2, j-1]$ does not contain two consecutive elements both
colored by $B$ or by $G$.
Lemma 3 implies that $c$ contains a rainbow $AP(3)$, which is a
contradiction.
\end{proof}

Finally, we are in a position to prove Conjecture~\ref{radosconj}.
\begin{theorem}\label{main}
Let $n \equiv 0\pmod 3$. For every equinumerous $3$-coloring of $[n]$ there exists a rainbow $AP(3)$.
\end{theorem}
\begin{proof}
The claim is true for $n \le 15$ \cite{JLMNR}.
Let $n \ge 15$, $n \equiv 0\pmod 3$, and let $c:[1,n]\to \{ B,G,R\}$ be an
equinumerous  $3$-coloring. Suppose that $c$ is rainbow-free. 
By Corollary 1, there is a dominant color, say $R$. 
By Corollary 2, one of the remaining colors, say $G$, is recessive. 
It follows that every element colored by $G$ is followed\footnote{or
preceded, if $c(n)=G$} by an element colored by $R$. 
Since there are elements of $[n]$ 
colored by $B$, there exists at least one pair $i,j \in [n]$, such that
$c(i)=B$, $c(j)=G$, and all the elements between $i$ and $j$ are colored with
$R$. Since the number of elements between $i$ and $j$ must be greater than or
equal to two, or else we have a rainbow $3$-term arithmetic progression, at least one of these elements is such that both of its 
neighbors are not colored by $G$. It follows that $\left| c^{-1}(G)\right|
<\left| c^{-1}(R)\right|$,
which contradicts our assumption that $c$ is equinumerous.
Therefore, $c$ is not rainbow-free.
\end{proof}

\section*{\normalsize 3. Concluding remarks}

This note settles the question of the existence of a rainbow arithmetic
progression in equinumerous $3$-colorings of $[n]$.  However, 
Conjecture~\ref{strongconj} is still open.  We hope that our lemmas in Section
2 with some additional ideas could prove that conjecture as well.

There are many directions and generalizations one might consider.  For a
discussion on this topic, as well as similar results for $\Z _n$, consult
\cite{JLMNR}. One natural direction is imitating the well known Rado's
theorem for the monochromatic analogue \cite{GRS90} and generalizing the
problems above for
rainbow solutions of other linear equations, under appropriate conditions 
on the cardinality of the color classes. The equation $x+y=z$ has
already been studied. Alekseev and Savchev~\cite{AS87, G94} proved that every
equinumerous $3$-coloring of $[3n]$ contains a rainbow solution of this
equation. Sch\"onheim~\cite{Sch90, S95}, answering the question of E. and G.
Szekeres, proved that for every $3$-coloring of $[n]$, such that every color class has
cardinality greater than $n/4$, 
the equation $x + y = z$ has rainbow solutions. Here, $n/4$ is optimal.

Finally, it would be very interesting to prove similar rainbow-type results 
for longer arithmetic progressions and larger numbers of colors.  
For example, it is not known whether every equinumerous $4$-coloring of $[4n]$ 
contains a rainbow $AP(4)$. However, note that for every $n$ and $k>3$, there 
exists a $k$-coloring of $[n]$ with
no rainbow $AP(k)$ and with each color class of size at least 
$\lfloor \frac{n+2}{3\lfloor (k+4)/3\rfloor} \rfloor$ \cite{JLMNR}.

 
\begin{thebibliography}{}

%\footnotesize 

\bibitem[AS87]{AS87}
{V. E. Alekseev, S. Savchev:}
{Problem M. 1040,}
{\it Kvant} {\bf 4} (1987), 23.

\bibitem[G94]{G94}
{R. K. Guy:}
{Unsolved Problems in Number Theory,}
{\it Springer-Verlag} 1994. (E11--12)

\bibitem[GRS90]{GRS90}
{R. L. Graham, B. L. Rothschild, J. H. Spencer:}
{Ramsey Theory,}
{\it John Wiley and Sons} 1990.

\bibitem[JLMNR]{JLMNR}
{V. Jungi\'{c}, J. Licht, M. Mahdian, J. Ne\v{s}et\v{r}il, R. \rados :}
{Rainbow arithmetic progressions and anti-Ramsey results,}
{\it Combinatorics, Probability, and Computing}, to appear.

\bibitem[Sch90]{Sch90}
{J. Sch\"onheim:}
{On partitions of the positive integers with no $x$, $y$, $z$ belonging to
distinct classes satisfying $x + y = z$,}
{in {\it R. A. Mollin (ed.) Number theory (Proceedings of the First Conference
of the
Canadian Number Theory Association, Banff 1988)}}, {de Gruyter} (1990),
515--528.

\bibitem[S16]{S16}
{I. Schur:}
{\"Uber die Kongruenz $x^m + y^m \equiv z^m$ mod $p$,}
{\it Jahresb. Deutsche Math. Verein} {\bf 25} (1916), 114--117.

\bibitem[S95]{S95}
{G. Sz\'ekely, ed.:}
{Contests in Higher Mathematics, Mikl\'os Schweitzer Competition 1962-1991,}
{Problem Books in Mathematics,}
{\it Springer} 1995. (C.22)

\bibitem[Sz75]{Sz75}
{E. Szemer\'edi:}
{On sets of integers containing no k elements in arithmetic progression,}
{\it Acta Arithmetica} {\bf 27} (1975), 199--245.

\bibitem[vW27]{vW27}
{B. L. van der Waerden:}
{Beweis einer Baudetschen Vermutung,}
{\it Nieuw Archief voor Wiskunde} {\bf 15} (1927), 212--216.

\end{thebibliography}
\end{document}











_