Раскраска целочисленной решётки

[Ktina]

Можно ли на координатной плоскости раскрасить все точки с целочисленными координатами в два цвета так, чтобы у любого прямоугольника с раскрашенными вершинами, сторонами, параллельными линиям сетки и площадью, равной степени двойки (с целым неотрицательным показателем -- прим. ред.), нашлись бы вершины обоих цветов? (Латвия, 2001)

[hippie]

Можно.

Если $x+y$ кратно 3, то красим точку $(x,\ y)$ в первый цвет, иначе — во второй.

Больше того, если покрасить вершины в 3 цвета, в зависимости от $(x+y) \mod 3,$ то у каждого прямоугольника с целочисленными вершинами, сторонами, параллельными линиям сетки и площадью не кратной трём будут вершины всех трёх цветов.

[Ktina]

hippie,
Даже неудобно как-то.
У меня то же самое, ещё вчера черновик заготовила:


Я бы покрасила все точки, сумма координат которых кратна трём, в один цвет, а остальные -- в другой.

Будем использовать тот факт, что сторона такого прямоугольника также равна некоторой степени двойки с ЦНП, а значит, на 3 не делится.

Предположим противное -- нашёлся такой прямоугольник, все вершины которого одного цвета. Это означает, что либо все вершины кратны 3 (что невозможно), либо все вершины не кратны 3.
Итак, если нашёлся такой прямоугольник, все его вершины не кратны 3.

Пусть левый нижий угол дает остаток 1 при делении на 3.
Тогда левый верхний должен давать 2.
Тогда правый верхний должен давать 1.
Тогда правый нижний должен давать 2.

Но тогда получается, что при переходе от левого нижнего к левому верхнему сумма координат увеличивается на число, дающее остаток 1 при делении на 3, а при переходе от правого нижнего к правому верхнему -- остаток 2 при делении на 3. Противоречие.

Аналогично доказывается случай, когда левый нижний угол даёт не 1, а 2.