МОШ 2020, 11 класс, задача 4
Из шахматной доски вырезали клеток. Известно, что среди вырезанных клеток есть как чёрные, так и белые. Какое наибольшее количество двухклеточных прямоугольников можно после этого гарантированно вырезать из этой доски?
Ответ. .
Решение.
Каждый двухклеточный прямоугольник содержит чёрную и белую клетки, поэтому если вырезано белых клеток, то больше прямоугольников вырезать не получится.
Разрежем доску так, как показано на рис. 1. Вырезанные из доски клетки при разрезании «испортят» не более прямоугольников. Следовательно, у нас уже есть по крайней мере целых прямоугольника. Покажем, как увеличить количество целых прямоугольников на . Рассмотрим изображённую на рис. 1 замкнутую цепочку клеток (по цепи идём от клетки вверх). Поскольку вырезаны как белые, так и чёрные клетки, в этой цепи обязательно есть вырезанная белая клетка, за которой идёт вырезанная чёрная клетка. Если эти клетки соседние, то они «портят» только один прямоугольник, значит, при таком разрезании будет не менее целых прямоугольников. В противном случае, если между ними есть ещё клетки, разделим доску между ними так, чтобы новый прямоугольник начинался сразу после вырезанной белой клетки (см. рис. 2). Тогда количество целых прямоугольников увеличится на . Следовательно, опять будет не менее целых прямоугольников.