, 2007

If $S_{n}$ and $S_{n+a}$ have the same color for some integer $n$, then we can choose the rectangle with vertices $(n, 0) \in S_{n}, (n, b) \in S_{n}, (n+a, 0) \in S_{n+a}$, and $(n+a, b) \in S_{n+a}$, and we are done. So it can be assumed that $S_{n}$ and $S_{n+a}$ have opposite colors for each $n$.

Similarly, it also can be assumed that $S_{n}$ and $S_{n+b}$ have opposite colors. Then, by induction on $|p|+|q|$, we obtain that for arbitrary integers $p$ and $q$, strips $S_{n}$ and $S_{n+p a+q b}$ have the same color if $p+q$ is even, and these two strips have opposite colors if $p+q$ is odd.

Let $d=\gcd(a, b)$, $a_{1}=a / d$ and $b_{1}=b / d$. Apply the result above for $p=b_{1}$ and $q=-a_{1}$. The strips $S_{0}$ and $S_{0+b_{1} a-a_{1} b}$ are identical and therefore they have the same color. Hence, $a_{1}+b_{1}$ is even. By the construction, $a_{1}$ and $b_{1}$ are coprime, so this is possible only if both are odd.

Without loss of generality, we can assume $a>b$. Then $a_{1}>b_{1} \geq 1$, so $a_{1} \geq 3$.

Choose integers $k$ and $\ell$ such that $k a_{1}-\ell b_{1}=1$ and therefore $k a-\ell b=d$. Since $a_{1}$ and $b_{1}$ are odd, $k+\ell$ is odd as well. Hence, for every integer $n$, strips $S_{n}$ and $S_{n+k a-\ell b}=S_{n+d}$ have opposite colors. This also implies that the coloring is periodic with period $2d$, i.e. strips $S_{n}$ and $S_{n+2 d}$ have the same color for every $n$.

Figure 1

We will construct the desired rectangle $ABCD$ with $AB=CD=a$ and $BC=AD=b$ in a position such that vertex $A$ lies on the $x$-axis, and the projection of side $AB$ onto the $x$-axis is of length $2d$ (see Figure 1). This is possible since $a=a_{1} d>2d$. The coordinates of the vertices will have the forms
$$A=(t, 0), \quad B=\left(t+2d, y_{1}\right), \quad C=\left(u+2d, y_{2}\right), \quad D=\left(u, y_{3}\right) .$$
Let $\varphi=\sqrt{a_{1}^{2}-4}$. By Pythagoras' theorem,
$$y_{1}=BB_{0}=\sqrt{a^{2}-4d^{2}}=d \sqrt{a_{1}^{2}-4}=d \varphi$$
So, by the similar triangles $ADD_{0}$ and $BAB_{0}$, we have the constraint
$$\begin{equation*} u-t=AD_{0}=\frac{AD}{AB} \cdot BB_{0}=\frac{b d}{a} \varphi \tag{1} \end{equation*}$$
for numbers $t$ and $u$. Computing the numbers $y_{2}$ and $y_{3}$ is not required since they have no effect to the colors.

Observe that the number $\varphi$ is irrational, because $\varphi^{2}$ is an integer, but $\varphi$ is not: $a_{1}>\varphi \geq \sqrt{a_{1}^{2}-2 a_{1}+2}>a_{1}-1$.

By the periodicity, points $A$ and $B$ have the same color; similarly, points $C$ and $D$ have the same color. Furthermore, these colors depend only on the values of $t$ and $u$. So it is sufficient to choose numbers $t$ and $u$ such that vertices $A$ and $D$ have the same color.

Let $w$ be the largest positive integer such that there exist $w$ consecutive strips $S_{n_{0}}, S_{n_{0}+1}, \ldots, S_{n_{0}+w-1}$ with the same color, say red. (Since $S_{n_{0}+d}$ must be blue, we have $w \leq d$.) We will choose $t$ from the interval $\left(n_{0}, n_{0}+w\right)$.

Figure 2

Consider the interval $I=\left(n_{0}+\frac{b d}{a} \varphi, n_{0}+\frac{b d}{a} \varphi+w\right)$ on the $x$-axis (see Figure 2). Its length is $w$, and the end-points are irrational. Therefore, this interval intersects $w+1$ consecutive strips. Since at most $w$ consecutive strips may have the same color, interval $I$ must contain both red and blue points. Choose $u \in I$ such that the line $x=u$ is red and set $t=u-\frac{b d}{a} \varphi$, according to the constraint (1). Then $t \in\left(n_{0}, n_{0}+w\right)$ and $A=(t, 0)$ is red as well as $D=\left(u, y_{3}\right)$.

Hence, variables $u$ and $t$ can be set such that they provide a rectangle with four red vertices.