×

# Maximum coverage by n rectangles

In one of my problems that I posted recently, Sir Brian Charlesworth posed a question asking what was the maximum possible coverage by n rectangles.

I honestly have no idea how to do this, so I figured I'd ask you guys, the Brilliant community, to see what you guys could think of.

I don't even know if this is answerable, but we'll see.

My plan is:

1. Find the positioning of n-squares that will allow for maximal coverage

2. Find the maximum coverage possible by n squares.

3. Find what shape n-rectangles will take.

4. Find the maximal coverage of n-rectangles.

Note by Trevor Arashiro
1 year, 11 months ago

Sort by:

Me and my big mouth. :) O.k., well, I have an idea of how to at least set a bar for others to try and beat for odd $$n$$. I think it is a safe(?) assumption that for odd $$n$$ we can look at symmetric configurations, while for even $$n \gt 2$$ I sense that the optimal configurations may not be symmetric, which make things a whole lot messier.

Anyway, with the assumption of symmetry for $$n = 2k - 1$$ for integers $$k \ge 1$$ we need only focus on the first quadrant. Draw $$k$$ radii in the first quadrant of a unit circle at angles $$\theta_{m} = m*\frac{90^{\circ}}{k + 1}$$ from $$m = 1$$ to $$m = k$$, (the angles being measured counter-clockwise from the positive $$x$$-axis). The horizontal lines $$x = \cos(\theta_{m})$$ will then serve as the top sides for a 'sequence' of non-overlapping rectangles of varying widths, with the 'base' of rectangle $$k$$ being the $$y$$-axis. (By symmetry the base of rectangle $$k$$ will coincide with the base of a corresponding rectangle to the left of the $$y$$-axis, thus giving us a total of $$2k - 1 = n$$ rectangles.) We then tally up the areas using some basic trigonometry.

So, for example, for $$n = 3, k = 2$$, we have $$\theta_{1} = 30^{\circ}$$ and $$\theta_{2} = 60^{\circ}$$. The areas of the rectangles in the first quadrant will then be

$$\sin(30^{\circ}) * (\cos(30^{\circ}) - \cos(60^{\circ})) + \sin(60^{\circ})*\cos(60^{\circ})$$,

which when multiplied by $$\frac{4}{\pi} * 100$$% gives a percentage coverage of about $$78.43$$% of the unit circle, which is just shy of the actual maximum found in the optimization question I posted previously.

For $$n = 5, k = 3$$ the percentage coverage comes out to

$$\frac{4}{\pi} * [\sin(22.5^{\circ})*(\cos(22.5^{\circ}) - \cos(45^{\circ})) + \sin(45^{\circ})*(\cos(45^{\circ}) - \cos(67.5^{\circ})) + \sin(67.5^{\circ})*\cos(67.5^{\circ})] * 100$$%

$$= 84.79$$% to $$2$$ decimal places.

I still need to clean up the trig a bit and establish a general equation for the percentage coverage $$P_{n}$$ by $$n = 2k - 1$$ rectangles, but I thought I'd just get the ball rolling. This won't be the 'best' solution, but it will be good enough to get some idea of how the coverage increases as we allow for more rectangles.

I can only hope that $$\lim_{n \rightarrow \infty} P_{n} = 100$$%...........

P.S.. I did do some googling before starting this and found nothing relevant to the generalized problem, which doesn't mean that it hasn't been dealt with before, (I'm sure it has), but it does mean we can at least pretend that it's novel. :)

EDIT: A few more calculations:

$$P_{7} = 88.28$$%, $$P_{9} = 90.48$$%, $$P_{11} = 91.99$$%, $$P_{13} = 93.09$$%,

$$P_{15} = 93.92$$%, $$P_{17} = 94.58$$%, $$P_{19} = 95.11$$%, $$P_{21} = 95.54$$%.

The formula I'm using for $$n = 2k - 1$$ is

$$P_{2k - 1} = \dfrac{2}{\pi} \displaystyle\sum_{m=1}^{k} \sin((\frac{m}{k+1})*180^{\circ}) - \frac{4}{\pi} \displaystyle\sum_{m=1}^{k-1} \sin((\frac{m}{k+1})*90^{\circ}) \cos((\frac{m+1}{k+1})*90^{\circ})$$.

Hmmmm.... I do tend to obsess a bit when I find a problem interesting ..... :)

EDIT #2: A few more values: $$P_{41} = 97.64$$%, $$P_{61} = 98.40$$%, $$P_{81} = 98.79$$%, $$P_{101} = 99.02$$%.

WolframAlpha is starting to creak and groan at this point, but at least we got past $$99$$% coverage, (even if it did take $$101$$ rectangles to do it). · 1 year, 11 months ago