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.

Cross-posted on MSE.

Answer 1

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?