Областная олимпиада по математике, 2009 год, 9 класс

Дан квадрат $n \times n$, раскрашенный в шахматном порядке так, что левая верхняя угловая клетка черная. Над квадратом разрешается совершать следующую операцию: выбрать прямоугольник размером $3\times 2$ или $2 \times 3$, в котором ровно три белые клетки, и перекрасить их в черный цвет. При каких натуральных значениях $n$ при помощи таких операций можно перекрасить все клетки в черный цвет?

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

Задачу можно переформулировать так: Дан квадрат n$\times$n.При каких n квадрат можно покрыть без наложений фигурками 3$\times$2 и 2$\times$3. Всего нам понадобиться 6k фигурок, где k = n$^2$/6. То есть n должен делится и на 3 и на 2.

Ответ: n = 6m.

Можно накрыть когда n=6k+-1,например n=1или 5

$1)n=2k,$ тогда на доcке $k$ черных и $k$ белых клеток $\Rightarrow k=3m\Rightarrow n=6m$

$2)n=2k+1,$ тогда на доске $2k^2+2k$ белых клеток $\Rightarrow k\not\equiv 1 \pmod 3$

И легко можно доказать по индукции если работает на $6m-1$ то работает на $6m+1,$ и если работает на $6m+1$ то работает на $6m+5$

Ответ$:$ для всех натуральных $n$ которые дает остаток 0,1.5 по модулю 6