Разбиение доски на части

Оценка. Выделим центральный квадрат и закрасим его крайние клетки. Получится рамка из клеток. Ещё закрасим клетки больших диагоналей вне рамки. Всего закрашено клеток. Если полоска вылезает за границу доски, то она накрывает хотя бы одну закрашенную клетку. Значит, таких полосок не более и они накрывают не более клеток вне доски. Вместе с клетками доски всего накрыто не более клетки, поэтому полосок не больше, чем то есть не больше

Пример. Будем накрывать доску прямоугольниками ширины Верхний край накроем прямоугольником разбив его на вертикальных полосок, вылезающих за доску на клетки. Аналогично накрываем нижний край Оставшиеся непокрытыми правый и левый край накроем вылезающими на прямоугольниками В центральном квадрате выделим от верхнего края два прямоугольника и покроем их вертикальными полосками. В оставшемся прямоугольнике покроем горизонтальными полосками часть оставив в углу непокрытый квадрат Итого использовано полосок.