10
$\begingroup$

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.

enter image description here

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!

Improve this question
$\endgroup$
7
  • $\begingroup$ Do you insist on the squares being aligned, that is, not rotated with respect to the big square? $\endgroup$
    – Gerry Myerson
    Commented Feb 20, 2021 at 21:48
  • $\begingroup$ @GerryMyerson Yes. Sorry if I'm not being very formal with the parameters of the question, but indeed the squares have to be sort of "snapped to" the integer coordinates of the plane. $\endgroup$
    – Marcel K. Goh
    Commented Feb 20, 2021 at 21:57
  • $\begingroup$ Trivial update (posted here to avoid spamming the homepage, hopefully): $f(11) = 35$. $\endgroup$
    – Marcel K. Goh
    Commented Feb 20, 2021 at 22:04
  • $\begingroup$ The $n$ used as side length and the $n$ used as number of smaller squares don't seem to be the same in your examples. Is that right? If so you should use different letters for these two numbers. $\endgroup$
    – Sam Hopkins
    Commented Feb 20, 2021 at 23:28
  • $\begingroup$ @SamHopkins They are supposed to be the same $n$. The peculiar case is $n=8$, when only $7$ squares are needed to produce a maximal sum. Of course, we can artificially decompose one of the squares into two smaller ones, giving us $8$ squares, as prescribed. $\endgroup$
    – Marcel K. Goh
    Commented Feb 20, 2021 at 23:42

2 Answers 2

Reset to default
7
$\begingroup$

You get an upper bound of $n^{3/2}$ by applying Cauchy–Schwarz to the following relaxation of your program:

$$ \text{maximize} \quad \sum_{i=1}^n x_i \quad \text{subject to} \quad \sum_{i=1}^n x_i^2\leq n^2.$$

Explicitly, $\sum_{i=1}^n x_i=\langle x,1\rangle\leq\|x\|\|1\|\leq n\cdot n^{1/2}=n^{3/2}$.

For the other direction, the obvious feasible point gives a lower bound of $\lfloor\sqrt{n}\rfloor^3=(1−o(1))n^{3/2}$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yeah, that much is obvious, but what is that $o(1)$? Can you figure out at least the second term in the asymptotic (assuming that $n=N^2+\gamma N$, say where $\gamma\in(0,2)$ is a known constant)? The exact solution is, probably, out of reach, of course. $\endgroup$
    – fedja
    Commented Feb 24, 2021 at 1:00
8
$\begingroup$

$f(8)=21$:

enter image description here

The other reported values up through $n=11$ are optimal. You can solve the problem via integer linear programming as follows. For square with top left corner $(i,j)$ and side length $s$, let binary decision variable $x_{i,j,s}$ indicate whether that square is used. The problem is to maximize $\sum_{i,j,s} s x_{i,j,s}$ subject to \begin{align} \sum_{i,j,s} x_{i,j,s} &= n \tag1 \\ \sum_{\substack{i,j,s:\\ i \le i_0 \le i+s-1 \\ j \le j_0 \le j+s-1}} x_{i,j,s} &\le 1 &&\text{for $(i_0,j_0)\in \{1,\dots,n\}\times \{1,\dots,n\}$} \tag2 \\ \end{align} Constraint $(1)$ forces $n$ squares to be used. Constraint $(2)$ prevents covering cell $(i_0,j_0)$ more than once.

Here are results for $n \le 50$, where $u_1(n)$ is the one-dimensional integer knapsack upper bound and $u_2(n)$ is the one-dimensional continuous knapsack upper bound: \begin{matrix} n & \lfloor \sqrt{n}\rfloor^3 & f(n) & u_1(n) & \lfloor u_2(n) \rfloor & u_2(n) & \lfloor n^{3/2} \rfloor \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 2 & 2 & 2 & 2.666666667 & 2 \\ 3 & 1 & 4 & 5 & 5 & 5 & 5 \\ 4 & 8 & 8 & 8 & 8 & 8 & 8 \\ 5 & 8 & 10 & 11 & 11 & 11 & 11 \\ 6 & 8 & 14 & 14 & 14 & 14.4 & 14 \\ 7 & 8 & 17 & 18 & 18 & 18.2 & 18 \\ 8 & 8 & 21 & 22 & 22 & 22.4 & 22 \\ 9 & 27 & 27 & 27 & 27 & 27 & 27 \\ 10 & 27 & 30 & 31 & 31 & 31.42857143 & 31 \\ 11 & 27 & 35 & 36 & 36 & 36.14285714 & 36 \\ 12 & 27 & 40 & 41 & 41 & 41.14285714 & 41 \\ 13 & 27 & 45 & 46 & 46 & 46.42857143 & 46 \\ 14 & 27 & 51 & 52 & 52 & 52 & 52 \\ 15 & 27 & 56 & 57 & 57 & 57.85714286 & 58 \\ 16 & 64 & 64 & 64 & 64 & 64 & 64 \\ 17 & 64 & 68 & 69 & 69 & 69.88888889 & 70 \\ 18 & 64 & 75 & 76 & 76 & 76 & 76 \\ 19 & 64 & 80 & 82 & 82 & 82.33333333 & 82 \\ 20 & 64 & 88 & 88 & 88 & 88.88888889 & 89 \\ 21 & 64 & 94 & 95 & 95 & 95.66666667 & 96 \\ 22 & 64 & 100 & 102 & 102 & 102.6666667 & 103 \\ 23 & 64 & 108 & 109 & 109 & 109.8888889 & 110 \\ 24 & 64 & 115 & 117 & 117 & 117.3333333 & 117 \\ 25 & 125 & 125 & 125 & 125 & 125 & 125 \\ 26 & 125 & 130 & 132 & 132 & 132.3636364 & 132 \\ 27 & 125 & 138 & 139 & 139 & 139.9090909 & 140 \\ 28 & 125 & 145 & 147 & 147 & 147.6363636 & 148 \\ 29 & 125 & 154 & 155 & 155 & 155.5454546 & 156 \\ 30 & 125 & 162 & 163 & 163 & 163.6363636 & 164 \\ 31 & 125 & 170 & 171 & 171 & 171.9090909 & 172 \\ 32 & 125 & 178 & 180 & 180 & 180.3636364 & 181 \\ 33 & 125 & 186 & 189 & 189 & 189 & 189 \\ 34 & 125 & 195 & 197 & 197 & 197.8181818 & 198 \\ 35 & 125 & 204 & 206 & 206 & 206.8181818 & 207 \\ 36 & 216 & 216 & 216 & 216 & 216 & 216 \\ 37 & 216 & 222 & 224 & 224 & 224.8461539 & 225 \\ 38 & 216 & 232 & 233 & 233 & 233.8461539 & 234 \\ 39 & 216 & 240 & 243 & 243 & 243 & 243 \\ 40 & 216 & 250 & 252 & 252 & 252.3076923 & 252 \\ 41 & 216 & 259 & 261 & 261 & 261.7692308 & 262 \\ 42 & 216 & 270 & 271 & 271 & 271.3846154 & 272 \\ 43 & 216 & 278 & 281 & 281 & 281.1538462 & 281 \\ 44 & 216 & 288 & 291 & 291 & 291.0769231 & 291 \\ 45 & 216 & 299 & 301 & 301 & 301.1538462 & 301 \\ 46 & 216 & 308 & 311 & 311 & 311.3846154 & 311 \\ 47 & 216 & 319 & 321 & 321 & 321.7692308 & 322 \\ 48 & 216 & 329 & 332 & 332 & 332.3076923 & 332 \\ 49 & 343 & 343 & 343 & 343 & 343 & 343 \\ 50 & 343 & 350 & 353 & 353 & 353.3333333 & 353 \\ \end{matrix}

Improve this answer
$\endgroup$
4
  • $\begingroup$ Whoa! I guess shifting every square left and down as soon as they are generated cannot be done without loss of generality. Thanks for this! $\endgroup$
    – Marcel K. Goh
    Commented Feb 21, 2021 at 2:24
  • $\begingroup$ If I may ask, what was your procedure for finding a decomposition? $\endgroup$
    – Marcel K. Goh
    Commented Feb 21, 2021 at 2:31
  • 1
    $\begingroup$ @MarcelK.Goh I added my integer linear programming formulation. $\endgroup$
    – RobPratt
    Commented Feb 21, 2021 at 2:47
  • $\begingroup$ Hi, I just saw the table you added. Thanks, this is really cool! $\endgroup$
    – Marcel K. Goh
    Commented Feb 22, 2021 at 22:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .