Задача
На доску $2018\times 2018$ клеток положили без наложений некоторое количество доминошек, каждая из которых закрывает ровно две клетки. Оказалось, что ни у каких двух доминошек нет общей целой стороны, т. е. никакие две не образуют ни квадрат $2\times 2$, ни прямоугольник $4\times 1$. Может ли при этом быть покрыто более 99% всех клеток доски?
Решение
Построим «паркет», в котором чередуются ряды вертикальных $2\times 1$ и горизонтальных $1\times 2$ доминошек. На рисунке эти ряды показаны серым и белым цветом для доски $12\times 12$ (непокрытые клетки доски закрашены чёрным).
Похожий пример можно построить и для доски размером $2018\times 2018$. Непокрытыми могут остаться лишь некоторые клетки первой строки и столбца, а также последней строки и столбца. Поэтому доля непокрытых клеток от их общего числа будет не более, чем $\frac{4\cdot 2017}{2018\cdot 2018} < \frac{4}{2018} < 1%$. Значит, будет покрыто более $99%$ всех клеток доски.
Ответ
Да, может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь