Как найти минимальное число квадратов кроме самого себя, которыми можно покрыть квадрат?

#алгоритм

Как найти это минимальное число на интуитивном уровне - понятно (см. рисунок)



Пусть задана сторона квадрата 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)

Тогда вопрос:

Как найти минимальное число квадратов кроме самого себя, которыми можно покрыть этот
квадрат ?
    

Ответы

Ответ 1

В общем случае ваше решение не оптимально. Для доказательства, к счастью, достаточно
контрпримера - вот он:



Слева - ваше решение, справа - немного получше (не буду утверждать, что оптимальное).

Тьфу, ну я даю... Тут же вообще можно было поделить квадрат 9x9 на 9 квадратов 3x3!
Ладно, оставлю уж свой позорняк... :)