|
|
 |
Условие
Можно ли покрасить некоторые клетки доски 8×8 так, чтобы в любом
квадрате 3×3 было ровно 5 закрашенных клеток, а в каждом прямоугольнике 2×4
(вертикальном или горизонтальном) – ровно 4 закрашенные клетки?
Решение
Ответ: нельзя.Решение. Предположим, что такая раскраска возможна. На всех рисунках не заштрихованы клетки, про которые выяснено, что они не закрашены; штриховкой обозначены клетки, про которые ещё не известно, закрашены они или нет; двойной штриховкой - заведомо закрашенные.
Рис. 11
Доску 8*8 можно разрезать на восемь прямоугольников 4×2, поэтому на ней ровно 8×4=32 закрашенные клетки.
Также её можно разрезать на четыре квадрата 3×3, три прямоугольника 4×2 и угловой квадратик 2×2 (рис. 11). В четырёх квадратах 3×3 и трёх прямоугольниках 4×2 уже 4×5+3×4=32 клетки, поэтому в угловом квадратике 2×2 не должно быть ни одной закрашенной клетки. Аналогично можно доказать, что и в остальных угловых квадратиках 2×2 нет закрашенных клеток.
Рис. 12
Доску без угловых квадратиков 2×2 можно разрезать на шесть прямоугольников 4×2 (рис. 12). Получаем, что всего на доске 6×4=24 закрашенные клетки. Противоречие.
Примечание. Доказав, что угловые квадратики 2×2 не закрашены, можно действовать и по-другому, например, так. Разместим на доске четыре квадрата 3×3 и два прямоугольника 4×2 как показано на рис. 13. На оставшееся место приходится 32-(4×5+2×4)=4 закрашенные клетки, и туда можно поместить два прямоугольника 4×2, перекрывающиеся по квадратику 2×2. В каждом из них четыре закрашенные клетки, и вместе у них четыре закрашенных клетки - значит, закрашено их пересечение, и угловой квадратик 2×2 должен быть полностью закрашен. Противоречие.
Приведём ещё одно решение. Покажем, что даже доску 6×6 нельзя раскрасить указанным в задаче образом. Так как её можно разрезать на четыре квадрата 3×3, в ней должно быть ровно 4×5=20 закрашенных клеток. Разрежем её на четыре прямоугольника 4×2 и квадратик 2×2 (рис. 14). В этих прямоугольниках 4×4=16 клеток, значит в 2×2 сосредоточены остальные 20-16=4 клетки, т. е. все клетки в нём закрашены.
Рис. 13
Переложив четыре прямоугольника другим образом, можно то же самое доказать про квадратики 2×2 в других углах, а также про квадратик в центре (рис. 15). Остальные клетки должны быть незакрашенными, так как в каждом прямоугольнике 4×2 уже есть по четыре закрашенные клетки. Теперь легко указать квадрат 3×3, в котором всего четыре закрашенные клетки (рис. 16).
| |
|
|
| Рис 14. | Рис 15. | Рис 16. |
