Задача 104068
|
|
 |
Условие
Петя закрасил одну клетку прямоугольника. Саша может закрашивать другие клетки этого прямоугольника по следующему правилу: можно красить любую клетку, у которой нечётное число закрашенных соседей (по стороне). Сможет ли Саша закрасить все клетки прямоугольника (независимо от того, какую клетку выбрал Петя), если размеры прямоугольника а) 8×9 клеток? б) 8×10 клеток?Решение
а) Сначала закрасим ряд длиной 9 клеток, содержащий изначально закрашенную клетку (см. первый рисунок). Далее будем красить столбцы через один, начиная закраску от покрашенного ряда (см. второй рисунок). После этого закрасить оставшиеся клетки доски совсем просто.Комментарий. Данный способ покраски обобщается на тот случай, когда хотя бы одна из сторон прямоугольника имеет нечётную длину. Повернём прямоугольник так, чтобы его ширина была нечётной, а после этого повторим только что описанную процедуру: красим ряд нечётной длины, и так далее.
б) Первый способ. Посмотрим на полупериметр фигуры, состоящей из закрашенных клеток. Вначале, когда закрасили одну клетку, полупериметр равен 2. На каждом шаге полупериметр или увеличивается на 1 (если у клетки была только одна соседняя закрашенная клетка) или уменьшается на 1 (если таких соседей было 3), то есть полупериметр увеличивается или уменьшается на 1. Следовательно, когда закрашено чётное число клеток, полупериметр закрашенной фигуры нечётен. Заметим, что полупериметр всего прямоугольника 8×10 равен 18, то есть чётный, поэтому весь прямоугольник закрасить нельзя.
Второй способ. Докажем, что для чётных m и n прямоугольник m×n нельзя закрасить ни при какой начальной закрашенной клетке. Посмотрим, сколько всего сторон имеют клеточки (включая внешние). Сторон клеточек m(n+1)+n(m+1)=2mn+m+n, то есть чётное число. Предположим, что мы смогли закрасить весь прямоугольник. Будем называть сторону закрашенной, если закрашена хотя бы одна из прилегающих к ней клеток. Вначале закрашено 4 стороны. На каждом шаге закрашивается 1 или 3 стороны. Всего таких шагов нужно сделать nm-1. Поскольку m и n чётны, то число nm-1 нечётно. Итак, если бы мы смогли закрасить весь прямоугольник, то было бы закрашено 4+(нечётное число раз по нечётному числу) сторон, то есть нечётное число, но, как мы уже посчитали, таких сторон чётное число, значит, весь прямоугольник закрасить нельзя.
