11
$\begingroup$

You have a closed cord of length 100 meters which touches point $P$. There is a line $L$ whose closest point is 20 meters from point $P$.

The value of a layout of cord is defined by the area enclosed on the side of the line with point $P$ plus twice the area enclosed on the opposite side.

What is the optimal shape of the cord that maximizes value?

See diagram below:

Diagram

$\endgroup$
  • $\begingroup$ Can I cut the cord? In my solution, does the cord still have to touch point P? $\endgroup$ – A E Nov 13 '14 at 13:08
  • 1
    $\begingroup$ @AE No, you cannot cut the cord. Yes, the cord must touch point P and it must be closed, sorry. :) $\endgroup$ – Neil Nov 13 '14 at 13:09
  • 2
    $\begingroup$ Can't add a reply - my best answer is a Cubic Bezier Curve starting and ending at P with control points at distance of 69.629m and angle ±45.722° (elevation from x-axis) from P. Gives a value of 1128.924. See: jsfiddle.net/jfca22k2/1 $\endgroup$ – MT0 Nov 14 '14 at 11:17
  • $\begingroup$ How did you come up with this?! $\endgroup$ – smci Feb 13 '18 at 9:57
6
$\begingroup$

My best solution: $score = 1142.5655\ m^2$

Best solution

As Jeffrey also explained, the curve is made of 3 arcs, one going from P to A, the second from A to B, the third going from B to P. The local optimality of the use of the available length implies constant curvature. It is only at boundaries, where the value of the surface changes, that the curvature can change.

The curvature is proportional to the value of the area. You can think of it as pressure. The higher the pressure, the more the lines curves out. Or to put it differently, the higher the value of the enclosed surface, the more it is worth to make an incursion in that area. That translates to higher curvature.

Anyway, the area right of the line counting twice, the curvature is double and the radius of the arc is halved. If the radius of the semi-circle on the right is $r$, then the radius of the 2 arcs left is $R = 2r$.

The problem being symmetrical, I will assume the optimal curve is also symmetrical relative to the horizontal axis. So I will only consider the upper half of the curve.

Solution explanations

$CA$ is at an angle $\alpha$ from the horizontal.
$DP$ is at an angle $\alpha+\beta$.

From the image, we can see some relations beteen $\alpha$, $\beta$ and $r$:

The distance from $P$ to the axis is 20. It can be computed from $\alpha$, $\beta$ and $2r$:
(1) $20 = 2r\cos\alpha - 2r\cos(\alpha+\beta)$

The length of the curve is half of the available length of 100:
(2) $50 = r\alpha + 2r\beta$

The distance from A to the horizontal axis can be computed in 2 ways:
$dist = r\sin(\alpha) = 2r\sin(\alpha+\beta)$
(3) $\sin(\alpha) = 2\sin(\alpha+\beta)$

We have 3 equations, (1), (2) and (3), and 3 unknowns. We can solve it numerically:

$\alpha=1.7390005916$, $\beta=0.8871224528$, $r=14.2318548591$.

It places A at $(x_0,0)$, C at $(0,y_1)$ and D at $(2x_0,-y_1)$
where $x_0 = -r\sin(\alpha) = 2.38258653$
and $y_1 = r\cos(\alpha) = 14.03100047$.

The areas can be computed (for the whole curve):
$area\ right = \alpha r^2 + x_0 y_1 = 385.657152221015$
$area\ left = \beta (2r)^2 - (20+x_0) y_1 - x_0 y_1 = 371.25117209358604$

And the final scores evaluates to:
$area\ left + 2\ area\ right = 1142.565477$.

$\endgroup$
  • $\begingroup$ Awesome. Isn't it counterintuitive that there's a cusp at P? $\endgroup$ – smci Feb 13 '18 at 10:41
  • $\begingroup$ Not to me. P is a mandatory point. The value of that point is infinite (or the penalty of not including it is infinite), so the curvature can be infinite at that point. Imagine P is a tree and a rope must go around the tree and enclose the largest possible area. The tree could well pull on the rope. $\endgroup$ – Florian F Feb 14 '18 at 9:19
  • $\begingroup$ I guess the intuition is "any slack on the LHS wastes area on the higher-scoring RHS" $\endgroup$ – smci Feb 15 '18 at 1:26
3
$\begingroup$

Best value: 1116.34 (two semiellipses)

This question is interesting. I would like to answer it.

The most efficient shape is the a raindrop shape type. That is: an isosceles triangle with a semicircle.

Indeed, we are looking to maximize the area in the right because of the x2 incentive. The best way to maximize the area of a shape with a cord is a circle. We can't create a full circle (P would be outside of it otherwise), so the other side of the circle has to be transformed.

We are looking to minimize the area in the left side because of the x1 deterrent effect. The best way to minimize an area with a cord is a segment. But the lollipop strategy shows that it reduces dramaticaly the size of a full circle in the right area. So we need 3 sides; we need a triangle. The triangle can have straight sides or outwards curved sides (see below).

Last but not least, the shape must be symmetric. If not, the area of the semicircle is grazed by that of the triangle (see this example). Of course, the symmetry is not vertical (because we have two very different shapes), but horizontal.

A triangle + a semicircle + a mandatory horizontal symmetry = this shape, as discovered by our friend.Another option: two half-ellipses side by side (see below).

Shape 1: a triangle with straight sides : 1083.63

We need to compute the best areas of the triangle and the semicircle in order to have the highest value. To do so, I would like to add some information:

enter image description here

  • a) I add q at the center of the side of the triangle that is on L.
  • b) I add r at one end of this side.
  • c) Because the triangle is isosceles (horizontal symmetry), Pq is the altitude of the triangle. Its lenght is 20 (Pq = 20). Moreover, for the same reason, angle Pqr = 90°.
  • d) I name i the length of the side of the triangle that is on L, at the same time the diameter of the semicircle.
  • e) A1 is the area of the triangle; A2 the area of the semicircle.

Now, we know how to compute the area of a triangle with its altitude (20) and the base (i), and we know how to compute the area of a semicircle with its radius (here: i/2). If we find the optimal length i, then we have the solution.

To find i, I have coded a small c++ program.

#include <iostream>
#include <math.h>

#define PI 3.1415926535

int main()
{
    double i, // the length we are looking for
           area1, // area of the triangle
           area2, // area of the circle
           perimeter, // perimeter of the whole shape
           value; // the value to maximize

    for (i = 0; i < 200; i=i+0.001) { // 200 is an arbitrary integer way outside the maximum expected value of i
        area1 = (20 * i) / 2; // classic formula of the area of a triangle
        area2 = (PI*((i/2)*(i/2)))/2; // (classic formula of the area of a circle)/2
        value = area1 + area2 * 2; // We compute the expected value
        perimeter = (sqrt((20 * 20) + (i / 2)*(i / 2))) * 2// Perimeter = lengths of the sides minus the base (Pythagorean theorem)...
            + (i*PI) / 2; // ... plus (perimeter of a circle)/2
        if (perimeter > 99.999 && perimeter < 100.001) // if the perimeter +/- = 100, then show the solution
            std::cout << "i: " << i << " | p: " << perimeter << " | a1: " << area1 << " | a2 : " << area2 << " | value : "<< value << std::endl;
    }
}

After having incremented i by 0.001 steps, it appears that the optimal data are (for this shape):

i: 31.32 m. | p.: 100 (+/- .001) | area 1: 313.2 | area 2: 385.215

Value: 1083.63

Shape 2: a triangle with outwards curved sides (semiellipse+semicircle) : 1113.6

enter image description here

We suppose that the triangle is composed of 2 quarters of ellipse. See the following image. The curved triangle is ABC. It is composed of two quarters of an ellipse : ABO and AOC. Well, in fact, our triangle is more half an ellipse, but anyway. :)

enter image description here

I have modified my program.

First, the area of the triangle is computed with the curves of the ellipse instead of the original segments. The formula for an ellipse is pi * minor axis [i/2] * major axis [20].

Second, the perimeter of the triangle minus the base is computed thanks to a Ramanujan formula:

enter image description here

Then the new program is:

#include <iostream>
#include <math.h>

#define PI 3.1415926535

int main()
{
    double i, // the length we are looking for
           area1, // area of the triangle
           area2, // area of the circle
           perimeter, // perimeter of the whole shape
           value; // the value to maximize

    for (i = 0; i < 200; i=i+0.01) { // 200 is an arbitrary integer way outside the maximum expected value of i
        area1 = (PI*20*(i/2))/2; // ((area of ellipse))/4)*2
        area2 = (PI*((i/2)*(i/2)))/2; // (classic formula of the area of a circle)/2
        value = area1 + area2 * 2; // We compute the expected value
        perimeter = (PI*(3*(20 + (i / 2)) - sqrt(((3 * 20 + (i / 2))*(20 + 3 * (i / 2)))))) / 2 // Perimeter of 2*1/4 of the ellipses (Ramanujan formula)
            + (i*PI) / 2; // ... plus (perimeter of a circle)/2
        if (perimeter > 99.99 && perimeter < 100.01) // if the perimeter +/- = 100, then show all the possible solutions
            std::cout << "i: " << i << " | p: " << perimeter << " | a1: " << area1 << " | a2 : " << area2 << " | value : "<< value << std::endl;
    }
}

The optimal data with outwards curved triangle are:

i: 28.96 m. | p.: 100 (+/- .002) | area 1: 454.903 | area 2: 329.349

Value: 1113.6

Shape 3: Two half-ellipses side by side : 1116.34

A last hypothesis. What happens if the shape on the right is, as well as that on the left, a semi-ellipse?

enter image description here

We have to add a new variable: the minor axis of the right ellipse. We could call this variable j.

My new program:

#include <iostream>
#include <math.h>

#define PI 3.14159265358979323846264338327950288419716939937510

int main()
{
    double i, j,// the lengths we are looking for
           area1, // area of right semiellipsis
           area2, // area of left semiellipsis
           perimeter, // perimeter of the whole shape
           value; // the value to maximize

    for (i = 0; i < 200; i = i + 0.01) {
        for (j = 0; j<200; j += 0.01) {// 200 is an arbitrary integer way outside the maximum expected value of i
            area1 = (PI * 20* (i/2) )/ 2; // area of semiellipse
            area2 = (PI * j * (i/2)) / 2;  // area of right semiellipse
            value = area1 + area2 * 2; // Computation of the expected value
            perimeter = (PI*(3 * (20 + (i/2)) - sqrt(((3 * 20 + (i/2))*(20 + 3 * (i/2)))))) / 2 // Perimeter of left semiellipse (Ramanujan formula)
                + (PI*(3 * (j + (i/2)) - sqrt(((3 * j + (i/2))*(j + 3 * (i/2)))))) / 2;  // ... plus Perimeter of right semiellipse 
            if (perimeter > 99.999 && perimeter < 100.001) // if the perimeter +/- = 100, then show all the possible solutions
                std::cout << "i: " << i << " | j: " << j << " | p: " << perimeter << " | a1: " << area1 << " | a2 : " << area2 << " | value : " << value << std::endl;
        }
    }
}

And now we have the best optimal value for this problem:

i: 27.87 | j: 15.5 | p.: 100 (+/- .001) | area 1: 437.781 | area 2: 339.28

value : 1116.34

My answer is then:

enter image description here

$\endgroup$
  • $\begingroup$ Your edited "curved" triangle isn't as efficient as the one with straight sides. Compared to a straight triangle, it uses more cord and gives less area. $\endgroup$ – Set Big O Nov 13 '14 at 19:27
  • $\begingroup$ Your ice-cream-cone diagram is at least 10,000 times better than mine. :) But if it made sense to have curved sides then they though should curve outwards to maximise the contained area. $\endgroup$ – A E Nov 13 '14 at 19:32
  • $\begingroup$ I wonder what would happen if you allowed the right half to be an ellipse as well. Intuitively it seems like it should be a circle, but most of us intuited that the left hand side should be straight lines... $\endgroup$ – Jason Patterson Nov 13 '14 at 20:18
  • $\begingroup$ @JasonPatterson: you were right. :) Updated. $\endgroup$ – LEGOlas Nov 13 '14 at 20:59
  • $\begingroup$ The classic problem "which shape with given perimeter has the greatest area" is uniquely answered by the circle. Therefore, replacing any elliptical arc in your answer by an equal-length circular arc will increase the value. (In particular, this means that the answer must be composed of three arcs, joined by one endpoint at P and two on L.) $\endgroup$ – Lopsy Nov 13 '14 at 21:20
1
$\begingroup$

For this, I did a little math and an angle at P of around 40 degrees to make this work.

enter image description here

$\endgroup$
  • $\begingroup$ I have a feeling you can do better if you nudge P upwards so it's aligned with the center of the circle. The area of the triangle shape is the same, and you'll have more slack to make the circle bigger. $\endgroup$ – Kevin Nov 13 '14 at 16:40
1
$\begingroup$

The shape has to be defined by three circular arcs:

  • one arc on the right side of L, between two points that I'll call A and B
  • one between P and A
  • one between P and B

Each three having curvature away.

Ratioanle: Given any optimal shape maximizing the weighted enclosed area, one can fix the points A and B as well as the line length in each area. Then, by keeping A and B and the segment lengths, each area is maximize by using a circular arc.

So, to find the optimal shape, just do a search by fixing the three lengths (so they sum to 100 m) and picking A and B. So, finding the maximum of a well-defined function over 4 variables (the last length is a function of the other two).

Shouldn't be to hard from here. :-)

$\endgroup$
  • $\begingroup$ I used the same principle. $\endgroup$ – Florian F Nov 14 '14 at 19:37
  • $\begingroup$ An anonymous user tried to post this comment by editing this answer: "Because the figure should be symmetry, we only need two variables: the length of AB and arc PA. Next is numerical optimization." I rejected the edit, but decided to post the comment here. $\endgroup$ – Victor Stafusa Dec 3 '14 at 5:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.