Triangles packed into a unit circle

2014 triangles have non-overlapping interiors contained in a unit circle.What is the largest possible value of the sum of their areas?

What are some ideas that might help me start this?

Note that the 2014 points do not have to lie on the circle.

• If it is a contest, shouldn't you show your knowledge of math..? – Bak1139 Apr 16 '14 at 12:26
• I'm not sure how that is relevant here. . . ? – Ayesha Apr 16 '14 at 12:28
• @Ayesha Typically, we like to see people demonstrate an attempt at solving a problem, particularly if it is (or if it resembles) homework. Some people extend this to include requiring work for all questions, rather than just basic questions, which is what Bak1139 seems to be doing. (I, personally, think that contest problems--and other "for fun" problems--should have a lower "demonstrated effort" expectation than homework, but I'm just attempting to explain Bak1139's comment.) – apnorton May 8 '14 at 19:38
• – user41281 Jun 19 '14 at 2:38

The first triangle placed must have 3 edges. A triangle placed after that with the largest area should share a side with the original triangle, and cover 1 original side, and add 2 new sides, giving it an extra side overall. Therefore, with 2013 more triangles than the first one, there should be a 2016 (3+2013) sided figure created for largest area covered. For this 2016-gon to have the largest area, it should be a regular 2016-gon, which can be done with 2014 triangles. The area for this is $\frac{1}{2}nR^2\sin{\frac{360^\circ}{n}}$ with R being the circle radius, and n being the number of sides. The rest can easily be plugged in to find the total area of the 2014 triangles.

• Sadly, no. See this (problem 2): web.mit.edu/hmmt/www/february/invitational/2014/… – Ayesha May 3 '14 at 1:40
• That a regular polygon maximizes the area (given n-gon) is easy, just use the isometric theorem, or apply Jensens to the sine function. However, it is not clear that the figure must be convex, or even that it should have a hole in the middle. Bearing in mind that even the contest organizers are having issues, there are certain subtitle ties in this problem that you can't sweep under a rug. – Calvin Lin May 4 '14 at 4:55
• Hole in the middle? I dont remember saying anything of that sort. And yes, i do realize that my proof is far from complete, merely an idea that may have helped the reader come to the correct proof themselves. – Asimov May 4 '14 at 13:41
• Interesting. I would suggest to start with something provable, like when you have one triangle the largest area is a equilateral, and then continue until 2014. I think you should try to start small, try it with 4, 10 or 20 triangles and see if you can find a rule. If you can't solve it for 20, you won't solve it for 2014. – WalyKu May 5 '14 at 10:40
• Just as a note to everyone, one of the organizers did write a bit about the problem: artofproblemsolving.com/Forum/viewtopic.php?f=433&t=584485 – Ayesha May 9 '14 at 20:42

I started to really like this problem after the first month!

We will prove that the $(n+2)$-gon is always the solution for $n$-triangles, by method of elimination.

Definitions:

$A_n$ is a solution satisfying the given conditions for $n$ triangles. By nature $A_n$ is a polygon or a collection of disjoint polygons.

$h(A_n)$ will denote the hull of $A_n$, while $ch(A_n)$ will denote the convex hull.

Proof:

We will start with a trivial, but nonetheless useful observation - if moving a set of vertices can increase the total area, $A_n$ is not a solution.

Any simple polygon with $n$-vertices consists of exactly $n-2$ triangles. Thus any simple polygon can be deformed into another simple polygon with the same amount of vertices, without changing the amount of triangles needed.

In general, if for a certain set of probable solutions, there exists a method to increase the area, then said set can be dismissed. On that we will begin:

1. $A_n$ cannot be a disjoint collection of polygons;

Proof: if we connect said polygons, we will increase the total area.

2. The hull vertices of $A_n$ are convex.

Proof: if $h(A_N)$ contains more vertices than $ch(A_n)$, then its worthwhile to substitute, as we will have more triangles to fill up the space.

3. Any "hole" in $A_n$ must have all its vertices in the $h(A_n)$;

Proof: If we move a vertex of a polygon $P$, such that it doesn't create an intersection, overlap with another vertex, or lie on a segment generated by two other vertices, then the overall amount of triangles required for a triangulization of $P$ does not change.

If we have a vertex in $A_n$, which is not in $h(A_n)$, then it can be moved onto it, reducing the amount of vertices, getting a spare triangle to fill up the space and increasing the span of $A_n$ edges.

4. $A_n$ touches the unit circle atleast once.

Proof: Let $m$ denote the maximum distance from the origin of all vertices in $A_n$. Since we are dealing with the unit circle, the following must hold $m^{-1}A_n = A_n$, which means that the maximum length will always be $1$ or that $A_n$ touches the unit circle at least once.

!! On a side note, one convincing idea arises - if $A_n$ can be covered up with a convex polygon with $n+2$ or less vertices, which are all on the circle, then $A_n$ is not a solution. If one imagines an arbitrary messy polygon dangling from one point off the unit circle, overlapped by a convex polygon, one is quite convinced how convex the hull of $A_n$ must be.

So, we are left with "incomplete" triangulizations of simple convex polygons.

5. In a convex incomplete simple, all "holes" can be patched up with an increase in area.

Proof: If we remove three adjacent vertices in a convex polygon, the remaining vertices are still in convex arrangement.

First, we start with a lemma - the smallest area triangle in a convex polygon is always composed of three adjacent vertices - proof.

Any "hole" is a polygon in $A_n$. By the lemma, it follows that we can always swap out all the constituent triangles of said polygon for the triangles composed of three adjacent vertices, increasing the area for each swap. Which in the end results in a simple convex polygon, with total greater area.

6. The largest simple convex polygon with $n$ triangles in the unit circle, is the $(n+2)$-gon.

Proof: Extending any vertex of a simple convex polygon to the perimeter of the unit circle, increases the area. Thus all the vertices are on the circle.

If we move a point $B$, in between two adjacent points $A$ and $C$, the area of $\Delta ABC$ will be maximum, when the altitude to $B$ is in the middle of $AC$. Therefore, any vertex on the unit circle is equally distanced from its neighbours.

Such a configuration can only be achieved by the $(n+2)$-gon with $n$-triangles.

Therefore, the $(n+2)$-gon, with all of its vertices on the unit circle, is the largest polygon that can be assembled from $n$-triangles.

The area of an ($n+2$)-gon, is equal to:

$S(n + 2) = \frac12(n+2)sin\frac{2\pi}{n+2}$

For the case $n = 2014$ :

$S(2016) = 1008sin\frac{\pi}{1008} \approx \pi - 5 \times 10^{-6}$

• Copied over from MO: I'm afraid I don't understand what you're doing. For example, what do you mean by the "hull" (vs. "convex hull"?) Also, in point (3), what do you mean by a "hole"? Unfortunately I don't see a reasonable interpretation for your claim "If we have a vertex in $A_n$, which is not in $(A_n)$, then it can be moved onto it, reducing the amount of vertices". Overall, I'm skeptical that an easy smoothing method exists (I will edit in a concrete obstruction soon), but it's certainly possible... in any case I would appreciate clarification on your solution. – Victor Wang Aug 18 '14 at 21:45
• Link to the concrete obstruction: see the recent edit at mathoverflow.net/questions/163893/… – Victor Wang Aug 18 '14 at 22:05