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.

Feel free to skip to any step.

#Algebra #Geometry #NumberTheory #Calculus #Easymoney

Note by Trevor Arashiro
6 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

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 nn. I think it is a safe(?) assumption that for odd nn we can look at symmetric configurations, while for even n>2n \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=2k1n = 2k - 1 for integers k1k \ge 1 we need only focus on the first quadrant. Draw kk radii in the first quadrant of a unit circle at angles θm=m90k+1\theta_{m} = m*\frac{90^{\circ}}{k + 1} from m=1m = 1 to m=km = k, (the angles being measured counter-clockwise from the positive xx-axis). The horizontal lines x=cos(θm)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 kk being the yy-axis. (By symmetry the base of rectangle kk will coincide with the base of a corresponding rectangle to the left of the yy-axis, thus giving us a total of 2k1=n2k - 1 = n rectangles.) We then tally up the areas using some basic trigonometry.

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

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

which when multiplied by 4π100\frac{4}{\pi} * 100% gives a percentage coverage of about 78.4378.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=3n = 5, k = 3 the percentage coverage comes out to

4π[sin(22.5)(cos(22.5)cos(45))+sin(45)(cos(45)cos(67.5))+sin(67.5)cos(67.5)]100\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= 84.79% to 22 decimal places.

I still need to clean up the trig a bit and establish a general equation for the percentage coverage PnP_{n} by n=2k1n = 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 limnPn=100\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:

P7=88.28P_{7} = 88.28%, P9=90.48P_{9} = 90.48%, P11=91.99P_{11} = 91.99%, P13=93.09P_{13} = 93.09%,

P15=93.92P_{15} = 93.92%, P17=94.58P_{17} = 94.58%, P19=95.11P_{19} = 95.11%, P21=95.54P_{21} = 95.54%.

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

P2k1=2πm=1ksin((mk+1)180)4πm=1k1sin((mk+1)90)cos((m+1k+1)90)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: P41=97.64P_{41} = 97.64%, P61=98.40P_{61} = 98.40%, P81=98.79P_{81} = 98.79%, P101=99.02P_{101} = 99.02%.

WolframAlpha is starting to creak and groan at this point, but at least we got past 9999% coverage, (even if it did take 101101 rectangles to do it).

Brian Charlesworth - 6 years, 6 months ago
×

Problem Loading...

Note Loading...

Set Loading...