48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

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+pa+qb}$ 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\ge 1$, so $a_1\ge 3$.

Choose integers $k$ and $\ell$ such that $k{a}_1-\ell b_1=1$ and therefore $ka-\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+ka-\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+2d}$ 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),B=\left(t+2d,y_1\right),C=\left(u+2d,y_2\right),D=\left(u,y_3\right).$$ Let $\phi =\sqrt{a_1^2-4}$. By Pythagoras' theorem, $$y_1=B{B}_0=\sqrt{a^2-4d^2}=d\sqrt{a_1^2-4}=d\phi$$ So, by the similar triangles $AD{D}_0$ and $BA{B}_0$, we have the constraint $$\begin{array}{c}u-t=A{D}_0=\frac{AD}{AB}\cdot B{B}_0=\frac{bd}{a}\phi \end{array}\text{\hspace{1em}(1)}$$ 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 $\phi$ is irrational, because ${\phi }^2$ is an integer, but $\phi$ is not: $a_1>\phi \ge \sqrt{a_1^2-2a_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},\dots ,S_{n_0+w-1}$ with the same color, say red. (Since $S_{n_0+d}$ must be blue, we have $w\le 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{bd}{a}\phi ,n_0+\frac{bd}{a}\phi +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{bd}{a}\phi$, 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.