You have $n$ rectangles of area $1$ (and variable height). Pack as many as possible in a semicircle of area $n$. How many leftovers will there be?

Question

You have $n$ rectangles of area $1$ (and variable height). Pack as many of these rectangles as possible in a semicircle of area $n$. How many leftover rectangles will there be, in terms of $n$?

How to pack the rectangles

I believe that the most efficient way to pack the rectangles is to stack them (so that each rectangle has two vertices touching the arc), as shown below.

What about arranging the rectangles side by side? A simple argument shows that the stacked arrangement is more efficient than the side by side arrangement. In each arrangement, consider a quarter circle (for example the right half of the semicircle). In the stacked arrangement the rectangles have area $1/2$, whereas in the side by side arrangement the rectangles have area $1$. The smaller the rectangles, the more efficient the packing.

Expressing the problem in terms of a sequence

Let $a_k$ be the sequence of the $x$-coordinates of the upper-right vertex of each rectangle, from bottom to top.

We have
$\alpha_1=$ $\large{[}$ largest real root of $2x\sqrt{\frac{2n}{\pi}-x^2}=1$ $\large{]}$
$\alpha_{k+1}=$ $\large{[}$ largest real root of $2x\left(\sqrt{\frac{2n}{\pi}-x^2}-\sqrt{\frac{2n}{\pi}-{\alpha_k}^2}\right)=1$ $\large{]}$

So the number of leftover rectangles is $f(n)=n-$ (number of terms in sequence $\alpha_k$).

I am looking for an exact or asymptotic closed form expression for $f(n)$.

Further thoughts

I have found experimentally that $f(18)=1$ and $f(19)=2$.

Based on Gauss's circle problem, I would guess something like $f(n)\approx n^{\theta}$ for some $\theta<1$. I guess my problem should be easier than Gauss's circle problem, because my problem just depends on finding the number of terms in the well-defined sequence $\alpha_k$.

The functions $y=2x\sqrt{\frac{2n}{\pi}-x^2}-1$ and $y=2x\left(\sqrt{\frac{2n}{\pi}-x^2}-\sqrt{\frac{2n}{\pi}-{\alpha_k}^2}\right)-1$ have the following kind of appearance. (This example is with $n=19$.)

If we can find a pattern among the local maximum values, then we can predict how many curves there are, which equals the number of rectangles packed in the semicircle.

On the top curve, $y=2x\sqrt{\frac{2n}{\pi}-x^2}-1$, the coordinates of the maximum point are $\left(\sqrt{\frac{n}{\pi}},\frac{2n}{\pi}-1\right)$.

The gaps between the local maximum values slightly decrease from top to bottom.

Answer 1

This is an interestingly deep question. I'd like to start by posing a more general version, which has close ties to error estimation for the Riemann integral:

We're given a monotonically increasing function $f:[0,X]\rightarrow \mathbb{R}_{\ge 0}$. If the area under $f$ can be maximally packed with $N$ vertical rectangles of fixed area $\alpha > 0$, how does the error $\left(\int_{0}^{X}f(x)dx\right) - N\alpha$ (i.e., the area under the curve that is not covered by the rectangles) behave as $\alpha \rightarrow 0$?

This is similar to the usual lower Riemann sum, except that here it's the area of the rectangles, not their width, that is fixed. Since the height of a rectangle starting at $x$ is $f(x)$, its width is $w(x)=\alpha/f(x)$; and the uncovered area above it (treating it as a right triangle) is $\approx w(x)^2 f'(x)/2$. The uncovered area per unit length is this divided by $w(x)$, or $$ \frac{1}{2}w(x)f'(x)=\frac{\alpha}{2}\frac{f'(x)}{f(x)}= \frac{\alpha}{2}\left(\log f(x)\right)'. $$ This gives the leading-order approximation for the total uncovered area as $$ E(\alpha) = \int_{a}^{b}\frac{\alpha}{2}\left(\log f(x)\right)'dx=\frac{\alpha}{2}\log\frac{f(b)}{f(a)}. $$

Note that the result doesn't depend on the details of $f$. From here out, we will assume that $f(X)=1$, in which case $E(\alpha) = -(\alpha/2)\log f(0)$. If $f(0) > 0$, then this is a complete answer: the number of "wasted rectangles" will converge to $-(1/2)\log f(0)$. However, if $f(0)=0$ (as it does in OP's problem), then we need to handle at least the first rectangle more carefully. Assuming the first rectangle extends from $x_0$ to $x_1$, the total wasted space is $$ -\alpha + \int_{0}^{x_1}f(x)dx - \frac{\alpha}{2}\log f(x_1). $$ This is minimized by setting its derivative with respect to $x_1$, $$ f(x_1) - \frac{\alpha}{2}f'(x_1)/f(x_1), $$ to zero. Suppose $f(x)\sim x^{\theta}$ for small $x$ and $0<\theta<1$ (here $\theta=1/2$). Then the derivative becomes $$ x_1^{\theta} - \frac{\alpha \theta}{2 x_1}, $$ which is zero at $$ x_1 \approx \left(\frac{\alpha \theta}{2}\right)^{\frac{1}{1+\theta}}. $$ Plugging this back in, we find the optimal wasted space to be approximately $$ -\alpha + \frac{\alpha\theta}{2(1+\theta)}\left(1 - \log(\alpha\theta/2)\right) = -\alpha + \frac{\alpha\theta}{2(1+\theta)}\left(1 - \log(\alpha)-\log(\theta/2)\right) = -\frac{\alpha\theta}{2(1+\theta)}\log\alpha + O(\alpha). $$ Specifically, for $\theta=1/2$, the wasted area is asymptotic to $$ \alpha\left(-\frac{1}{6}\log\alpha + O(1)\right). $$ We are finally in a position to give an answer to the original problem. When packing a quarter-circle of height $1$ with rectangles of area $\alpha$, the wasted area is the above. If the original area is divided into $N$ equal parts, then $\alpha = \pi/(4N)$, and the number of wasted rectangles is $$ \frac{1}{6}\log N + O(1). $$ The same result holds for a semicircle, since both the rectangles' area and the wasted area are doubled.

Answer 2

I have evidence that, for large $n$, the number of leftover rectangles is approximately $\color{red}{\frac16\log{n}+c}$, where $c\approx 0.482$.

We will pack the circles from $\color{red}{\text{top to bottom}}$ (instead of from bottom to top as suggested in the OP). We can prove that packing bottom to top, or top to bottom, always results in the same number of leftover rectangles, by using proof by contradiction.

Assume that packing bottom to top admits more rectangles than packing top to bottom. Take the (non-optimal) top to bottom arrangement - call it the original arrangement - and starting with the lowest rectangle, shift all the rectangles down as much as possible; call this new arrangement the shifted down arrangement. Then add one more rectangle at the top (this is possible, according to our assumption!). Now the top rectangle in the shifted down arrangement, must be no higher than the top rectangle in the original arrangement (because in the original arrangement, the top rectangle was as high as possible, by definition). So essentially, going from the original arrangement to the shifted down arrangement, we moved the top rectangle down, and created space for one more rectangle. But that is clearly impossible. Hence packing bottom to top cannot admit more rectangles than packing top to bottom. A similar argument shows the converse is also true.

Packing top to bottom, I let $\color{red}{(\alpha_k,\beta_k)}$ be the coordinates of the $\color{red}{\text{lower-right}}$ vertex of the $k$th rectangle from the top.

For a large value of $n$ (say $n=10000)$, I found $\color{red}{\text{$\alpha_1$ and $\beta_1$}}$ as follows. For a general rectangle, the area is $2\alpha\left(\sqrt{2n/\pi-\alpha^2}-\beta\right)=1$. The curve of $\beta$ against $\alpha$ has a maximum point, which corresponds to the rectangle with the highest possible base. So $\alpha_1$ is the largest real root of $\frac{d\beta}{d\alpha}=0\implies 4\alpha^6+\alpha^2-2n/\pi=0$, and $\beta_1=\sqrt{2n/\pi-{\alpha_1}^2}-\frac{1}{2\alpha_1}$.

Then using the fact that the area of the $(k+1)^{\text{th}}$ rectangle from the top is $2\alpha_{k+1}(\beta_k-\beta_{k+1})=2\sqrt{2n/\pi-{\beta_k}^2}(\beta_k-\beta_{k+1})=1$, I got $\color{red}{\text{recursive relations}}$:

$$\begin{align}\beta_{k+1}&=\beta_k-\frac{1}{2\sqrt{2n/\pi-{\beta_k}^2}}\\ \alpha_{k+1}&=\sqrt{2n/\pi-{\beta_k}^2}\end{align}$$

I used Excel to find all $(\alpha_k,\beta_k)$. Then I approximated the gaps on the left and right of the rectangles as right triangles, and added up their areas. (I am not sure if the error of this approximation approaches $0$, or approaches some positive number, as $n\to\infty$.) On each side of the semicircle, the area of the $k$th "triangular" gap from the top, is $\frac12(\alpha_{k+1}-\alpha_k)(\beta_{k-1}-\beta_k)$.

Then I found the area of the gap at the top of the semicircle, which is $2\int_0^{a_1} \left(\sqrt{2n/\pi-x^2}-\sqrt{2n/\pi-{\alpha_1}^2}\right)dx$, which can be shown to approach $1/3$ as $n\to\infty$.

$\color{red}{\text{The total area of the gaps equals the number of leftover rectangles.}}$ Working with the trendline function in Excel, I got that the number of leftover rectangles is approximately $\frac16\log{n}+c$, where $c\approx 0.482$.

But this is all numerical investigation. Is there a proof?