I was wondering if anything is known about this problem. We are given a square of side length $n$ and we wish to embed $n$ smaller (integer) squares inside it such that the sum of the side-lengths of the squares inside is maximised. Let $f(n)$ be the maximum sum of side-lengths one can produce in this way. I have computed some values of $f(n)$, and have displayed them below. Apologies for the handwritten drawing, but I think the picture does help explain what I'm trying to get at.
The inequalities I have highlighted in red are written so because I am unsure if this is the maximum that can be achieved. In particular, for $n=8$ we don't even use $8$ squares, but I cannot figure out a configuration of $8$ squares that beats $20$. (I have reason to believe that $f(8)\leq 21$, and it would be nice if this could be attained with equality.) The values I have written as equality I am more sure about, based on exhaustive computer simulation. Is anything known about this function $f$? Even basic upper and lower bounds would be really helpful. It certainly seems to be roughly $n^{3/2}$.
Update. I made my simulations a bit more efficient, and they seem to indicate that $f(8) = 20$ and $f(10)=30$ are indeed equalities. We also have $f(11)\geq 35$ (and this is likely equality, since my program is taking a while trying to find an example with sum $36$.).
Edit. I appreciate all of the comments! Since the constraints of original question may be a bit too difficult (and possibly artificially so), I would like to weaken the requirements slightly. In this new version of the problem, we have a rectangle of integer side lengths $a$ and $b$ and wish to fill it with $c$ squares in order to maximise the sum of side lengths of the inner squares. Thus the original problem was when $a = b = c = n$. The weaker assumptions may make it easier to form an inductive argument. I am still working on this, but would appreciate any help!
