3

I'm not a mathematician. I'm trying to solve a difficult archived programming problem from Project Euler. I don't necessarily want to link it, because sharing exact solutions to problems is against PE site rules and I don't want anyone here to go too far solving the problem in a response, nor do I want someone to be able to find the answer by googling the problem. The question I'm asking here is just one intermediate step and is sufficiently general that it's within the spirit of the PE site to ask for help with it. If you really want to know the exact problem you probably can find it without too much work, or you can give me your email and I'll send it to you.

Basically my question is exactly as stated in the title. I have to imagine there's a well-known mathematical result that gives the solution, but I can't seem to find it. Ideally I'd also like to develop some intuition for how to find this answer myself.

Relevant info given in the problem description:

Let's say you have a square with side lengths of 500 meters. The area:perimeter ratio of this square is $125$ (this is what we're trying to maximize). The inscribed circle ($r = 250$) has the same ratio. If you cut from each corner of the square an isosceles triangle of sides $75, 75, 75 \sqrt{2}$, the resulting inscribed shape has an area:perimeter ratio of ~$130.87$.

Info from my work on the problem so far:

-A regular inscribed octagon has a ratio of $125$. Maybe this result can be generalized to any regular inscribed shape symmetric about both axes with >4 sides?

-An inscribed squircle of definition $x^4 + y^4 = r^4$, ($r = 250$), has a ratio of about $132.1$. None of my attempts at a solution based on this shape have worked, though, so I'm thinking this is not the optimal shape.

MAA1117
  • 35
  • I believe for any $2$-d shape, the circle maximizes the ratio of the area to perimeter (this follows from the isoperimetric inequality). If this doesn't answer your question, I'm not sure I understand it. – Alan Abraham Jan 11 '24 at 01:26
  • 1
    Yes the question seems confusing at first and I could probably describe it better somehow. I believe the key here is to recognize that while the circle maximizes perimeter/area for a given perimeter, that's not the constraint. The constraint is that it must fit within a square of a given size. I don't really know the best way to describe it other than what I've said in the original post, but if you work out the examples I've given it should help clarify things. My apologies for the insufficient description. – MAA1117 Jan 11 '24 at 01:36

1 Answers1

2

By the isoperimetric inequality, without further constraints the shape that maximizes the ratio of area to perimeter is a circle. Here, you have the constraint that the shape must lie within the given square. Since the optimality of the circle can be demonstrated using variational calculus, any portions of the optimizing shape in the interior of the square must be circular arcs. Thus, the optimal shape is one that follows the square for a while and then cuts the corner with a circular arc. The first derivative must be continuous because otherwise the ratio could be further optimized by cutting the remaining corner.

So if we use a square with side length $2$ centred at the origin and look at, say, the first quadrant, the shape follows the square from $(0,1)$ to some point $(1-r,1)$, forms a circular arc with radius $r$ to $(1,1-r)$ and then follows the square down to $(1,1)$. The resulting ratio is

$$ \frac{1-r^2+\frac\pi4r^2}{2-2r+\frac\pi2r}\;, $$

which is maximized by

$$ r=\frac2{2+\sqrt\pi}\approx0.53016\;, $$

which happens to also be the optimal value of the ratio.

Thus, for your square the optimal ratio is

$$ \frac{500}2\cdot\frac2{2+\sqrt\pi}\approx132.54\;, $$

so you got rather close in your attempts.

joriki
  • 238,052
  • 1
    Thank you! Very clear and simple explanation. I will attempt to solve the problem based on this shape and then update if I'm successful. – MAA1117 Jan 11 '24 at 15:22