Как найти это минимальное число на интуитивном уровне - понятно (см. рисунок)
Пусть задана сторона квадрата n
, тогда
это число равняется:
min = 4 + (n^2 - (3*floor(n/2)^2 + ceil(n/2)^2)
(1)
то есть для четных n
, min = 4
, а для нечётных min = 4 + кол-во единичных квадратов
Но непонятно, как формально доказать формулу (1)?
То есть что вот это
(n^2 - (3*floor(n/2)^2 + ceil(n/2)^2)
есть ни что иное, как минимально необходимое количество единичных квадратов.
update
как оказалось, формула 1 не оптимальна в общем случае (см пример @Harry)
Тогда вопрос:
Как найти минимальное число квадратов кроме самого себя, которыми можно покрыть этот квадрат ?