Олимпиадная задача по математике: перекраска квадратов 2×2 в шахматном поле
Дан квадрат n×n. Изначально его клетки раскрашены в белый и чёрный цвета в шахматном порядке, причём хотя бы одна из угловых клеток чёрная. За один ход разрешается в некотором квадрате 2×2 одновременно перекрасить входящие в него четыре клетки по следующему правилу: каждую белую перекрасить в чёрный цвет, каждую чёрную – в зелёный, а каждую зелёную – в белый. При каких n за несколько ходов можно получить шахматную раскраску, в которой чёрный и белый цвета поменялись местами?
Показать ответ
При всех n, кратных 3.
Разобрать решение
Предположим, что нам удалось перекрасить клетки так, как требуют условия задачи. Будем называть клетками первого типа те, которые первоначально были белыми, а второго типа – те, которые были чёрными. Заметим, что если какую-то клетку перекрасили три раза, то в итоге она свой цвет не поменяла. Поэтому для того, чтобы клетка первого типа стала чёрной, её нужно перекрасить 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. Рассмотрим один из таких квадратов. Есть два случая – либо угловые клетки белые, либо чёрные. В первом случае перекрашиваем каждый из четырёх квадратов, примыкающих к углам по одному разу, а во втором случае – по два раза. Легко проверить, что при таком перекрашивании шахматная раскраска поменяется на противоположную.
Обсуждение
0Комментариев пока нет.