Олимпиадная задача: расстановка звёздочек в квадрате 10×10 по условиям 2×2 и 3×1
Задача
Можно ли в клетки квадрата 10×10 поставить некоторое количество звёздочек так, чтобы в каждом квадрате 2×2 было ровно две звёздочки, а в каждом прямоугольнике 3×1 – ровно одна звёздочка? (В каждой клетке может стоять не более одной звёздочки.)
Решение
Первый способ. Пусть так расставить звёздочки удалось. Квадрат 10×10 можно разбить на 25 непересекающихся квадратов 2×2. Так как в каждом из них – по две звёздочки, то всего звёздочек 50. С другой стороны, 99 клеток исходного квадрата можно разбить на 33 непересекающихся прямоугольника 3×1. В каждом из них – по одной звёздочке, поэтому всего в квадрате – не больше 34 звёздочек. Противоречие. Второй способ. Докажем, что требуемым образом нельзя заполнить даже квадрат 3×3. Действительно, так как в каждом прямоугольнике 3×1 должна стоять только одна звёздочка, то в каждой строке и в каждом столбце квадрата 3×3 должно стоять только по одной звёздочке. Рассмотрим левый верхний квадрат 2×2. В нём должно быть две звёздочки. Но тогда в третьем столбце первой и второй строки не должно быть звёздочек, значит, в правом верхнем квадрате 2×2 будет стоять только одна звёздочка, а не две.
Ответ
Нельзя.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь