33-я Балканская математическая олимпиадаАлбания, Тирана, 2016 год

Плоскость разделена на единичные квадраты двумя семействами параллельных прямых, которые образуют бесконечную сетку. Каждый единичный квадрат покрашен в один из 1201 цвета так, что никакой прямоугольник с периметром 100, стороны которого лежат на линиях сетки, не содержит двух единичных квадратов одного цвета. Докажите, что никакой прямоугольник размера $1 \times 1201$ или $1201 \times 1$, стороны которого лежат на линиях сетки, не содержит двух единичных квадратов одного цвета.

Комментарий/решение

\textbf{Решение.}

Обозначим цвет клетки с координатами $(i,j)$ через $c(i,j)$.

По условию любой прямоугольник со сторонами на линиях сетки и периметром $100$

не содержит двух клеток одного цвета. Если стороны прямоугольника равны $a$ и $b$,

то

\[

2(a+b)=100 \Rightarrow a+b=50.

\]

Предположим противное: существует прямоугольник $1\times1201$, содержащий две

клетки одного цвета. Тогда существуют $x<y$ такие, что

\[

c(x,0)=c(y,0).

\]

Положим

\[

d=y-x.

\]

Заметим, что среди чисел $1,2,\dots,1200$ обязательно найдётся число,

сравнимое с $d$ по модулю $50$, и не превосходящее $49$.

Следовательно, существуют такие $k$ и $t$, что

\[

d=50k+t,\qquad 1\le t\le 49.

\]

Рассмотрим клетки

\[

(x,0),\qquad (x+t,50-t).

\]

Расстояния между их координатами равны

\[

t \quad\text{и}\quad 50-t,

\]

поэтому они являются противоположными углами прямоугольника со сторонами

$t$ и $50-t$. Для этого прямоугольника

\[

t+(50-t)=50,

\]

следовательно его периметр равен $100$.

Теперь рассмотрим клетки

\[

(y,0),\qquad (y-t,50-t).

\]

Они образуют такой же прямоугольник.

Так как $c(x,0)=c(y,0)$, то две клетки одинакового цвета оказываются

вершинами прямоугольника периметра $100$, что противоречит условию.

Следовательно, в любом прямоугольнике $1\times1201$ все клетки имеют

различные цвета.

Аналогичное рассуждение применяется для прямоугольника $1201\times1$.

Следовательно, никакой прямоугольник размеров $1\times1201$ или

$1201\times1$ не содержит двух клеток одного цвета.

\qed