Олимпиадная задача по математике: перекраска квадратов 2×2 в шахматном поле
Задача
Дан квадрат n×n. Изначально его клетки раскрашены в белый и чёрный цвета в шахматном порядке, причём хотя бы одна из угловых клеток чёрная. За один ход разрешается в некотором квадрате 2×2 одновременно перекрасить входящие в него четыре клетки по следующему правилу: каждую белую перекрасить в чёрный цвет, каждую чёрную – в зелёный, а каждую зелёную – в белый. При каких n за несколько ходов можно получить шахматную раскраску, в которой чёрный и белый цвета поменялись местами?
Решение
Предположим, что нам удалось перекрасить клетки так, как требуют условия задачи. Будем называть клетками первого типа те, которые первоначально были белыми, а второго типа – те, которые были чёрными. Заметим, что если какую-то клетку перекрасили три раза, то в итоге она свой цвет не поменяла. Поэтому для того, чтобы клетка первого типа стала чёрной, её нужно перекрасить 3k + 1 раз при некотором целом k (для разных клеток k может быть разным). Значит, если a – количество клеток первого типа, то общее количество перекрашиваний этих клеток равно 3K + a при некотором целом K. Чтобы клетка второго типа стала белой, её нужно перекрасить 3m + 2 раза. Значит, если b – количество клеток второго типа, то общее количество перекрашиваний этих клеток равно 3M + 2b.
В каждом квадрате 2×2 клеток первого и второго типа поровну. Поэтому суммарно клетки первого и второго типов будут перекрашены одинаковое число раз, то есть 3K + a = 3M + 2b. Отсюда n² = a + b кратно 3. Значит, и n кратно 3.
Осталось показать, как перекрасить квадрат со стороной, кратной 3. Разрежем его на квадраты 3×3. Рассмотрим один из таких квадратов. Есть два случая – либо угловые клетки белые, либо чёрные. В первом случае перекрашиваем каждый из четырёх квадратов, примыкающих к углам по одному разу, а во втором случае – по два раза. Легко проверить, что при таком перекрашивании шахматная раскраска поменяется на противоположную.
Ответ
При всех n, кратных 3.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь