= Solution
Apply the <Gallai theorem for an integer lattice> to the finite pattern
$$
F=\bigcup_{0\le r<s<m}\{(su-rv,\ v-u):0\le u,v<m\}\subseteq\mathbb Z^2.
$$
Although some coordinates are negative, translating $F$ into the positive quadrant and applying the positive-lattice theorem produces a <monochromatic> copy $F_0=(a_0,d_0)+qF\subseteq\mathbb N^2$, with integer $q>0$. The translation is absorbed into $(a_0,d_0)$. Let $(r,s)$ be the common position-pair label on this copy.
For each $0\le u,v<m$, the starting point and step
$$
a=a_0+q(su-rv),\qquad d=d_0+q(v-u)
$$
label the red edge at positions $r,s$. Its endpoints simplify to
$$
a+rd=a_0+rd_0+q(s-r)u,\qquad
a+sd=a_0+sd_0+q(s-r)v.
$$
Thus the two <arithmetic progressions>
$$
A=\{a_0+rd_0+q(s-r)u:0\le u<m\},\qquad
B=\{a_0+sd_0+q(s-r)v:0\le v<m\}
$$
have a positive <common difference> $q(s-r)$, and every cross-pair is red. Their entries are positive because they occur as endpoints of the positive-start, positive-step progressions represented in $F_0$.
It remains to check disjointness, rather than infer it merely from distinct starting points. The pattern contains points whose second coordinate is $-(m-1)$. Since all of $F_0$ lies in $\mathbb N^2$,
$$
d_0-q(m-1)>0.
$$
Consequently
$$
\min B-\max A=(s-r)\bigl[d_0-q(m-1)\bigr]>0.
$$
Therefore \b[$A$ and $B$ are disjoint $m$-term <arithmetic progressions> with every cross-edge red]. Combined with the first branch, this proves the dichotomy.
Back to article page
