Convex pentagons in a triangle
===
In the [17 May 2010 Issue of the New Yorker](http://www.newyorker.com/magazine/2010/05/17/roulette-russian) there is an interesting article about Andrey Ternovskiy, the founder of Chatroulette. A particular math problem stood out to me:
> How do you cut a square into convex pentagons? "Here's how Andrey solved it," Puchkov said, and sketched a square with two abutting pentagons in the center and lines radiating out cleanly to the perimeter. It was the simplest solution---and Ternovskiy had come to it far more quickly than Puchkov had.
I started thinking about related problems, generalizations. An easy modification is to swap out the square for a triangle.
# Problem
What is the least number of convex pentagons that can fit in a triangle snugly without overlap or leftover space?
That is, how do you cut a triangle _minimally_ into convex pentagons?
Here, I will provide a _sketch_ of a proof that the answer is 9. It is not rigorous, but is meant to give a rough idea.
# Solution
First, we know there is an upper bound of 9.
pic triangle_claim0.svg Illustration of the upper bound : A picture of how you might cut a triangle into 9 convex pentagons.
> **Claim 1**: Suppose a convex polygon with $n$ vertices can be cut into a minimum of $m$ convex pentagons. Then, a concave polygon $P$ with $n$ convex vertices cannot be cut into fewer than $m$ convex pentagons.
**Explanation**: For each concave vertex of $P$, there must be a cut at that vertex. So, we can "straighten out" this concave vertex by moving it outwards along the cut until it has an angle of $180^\circ$, in which case it is effectively no longer a vertex.
This won't affect the convexity of the pentagons inside $P$, and we can thus remove all the concave vertices of $P$ to be left with a convex polygon of $n$ vertices cut into convex pentagons. If $P$ were cut into fewer than $m$ convex pentagons, it would contradict the premise.
> **Claim 2**: Suppose a triangle is cut into the minimum number of convex pentagons. Then each of the triangle's edges must touch more than one convex pentagon.
**Explanation**: If there is an edge that touches only one convex pentagon, then the remainder area in the triangle still has three convex vertices. By Claim 1, this cannot be cut into fewer convex pentagons than a triangle can be. So this cannot be the minimal solution.
pic triangle_claim3.svg Illustration of Claim 2 : A picture showing the leftover space in a triangle if the bottom edge touches only one convex pentagon.
> **Claim 3**: Suppose a triangle is cut into the minimum number of convex pentagons. There is no need to cut a triangle at its corner, i.e. each corner only has to touch one pentagon.
**Explanation**: Let us consider two cases: Either we cut a triangle at its corner, or we don't. In both cases, after accounting for one convex pentagon touching the corner, the remaining area has 4 convex vertices. But in the former case, it has more concave vertices, which we can again "straighten out" using the logic behind Claim 1. So, it isn't any better than the latter case of letting each vertex of the triangle touch only one convex pentagon.
pic triangle_claim4.svg Illustration of Claim 3 : Cutting a triangle at its corner results in a remaining area with more concave vertices than otherwise.
At this point, you might note that you can fit Andrey Ternovskiy's solution for cutting a square into 8 convex pentagons into the leftover area here, and immediately arrive at the answer of 9. But let us pretend we never saw the New Yorker article and proceed with the proof.
> **Claim 4**: Suppose a convex quadrilateral is cut into the minimum number of convex pentagons. Then, it must have at least one edge that touches more than two convex pentagons.
**Explanation**: First we can rule out the case of a single convex pentagon touching an edge by the same logic as Claim 2. But if every edge touches two convex pentagons, then we are left with a remaining area that has 4 convex vertices --- again, not optimal due to Claim 1.
pic triangle_claim5.svg Illustration of Claim 4 : A convex quadrilateral cut such that every edge touches two convex pentagons is not optimal because the remaining area has 4 convex vertices.
> **Claim 5**: Suppose a triangle is cut into the minimum number of convex pentagons. Then, each edge must touch more than 2 convex pentagons.
**Explanation**: If there is an edge that touches only two convex pentagons, the remaining area has 4 convex vertices with at least 2 more concave vertices. But you can get essentially the same remaining area in [Figure 3](#fig3), but with one fewer convex pentagon used!
pic triangle_claim6.svg Illustration of Claim 5 : No matter how you let only two convex pentagons touch a single edge of the triangle, it cannot be optimal.
Actually, in the [above picture](#fig5), it might seem case C has a different remaining area than in [Figure 3](#fig3). But from Claim 4, we know a quadrilateral must have at least one edge that's cut twice. So, the remaining areas in case C and in the right side of [Figure 3](#fig3) need the same number of convex pentagons after all.
## Result
> **Proposition 1**: A triangle can be cut into a minimum of 9 convex pentagons.
**Explanation**: From Claim 5, we know each edge of the triangle must touch at least 3 convex pentagons. This already uses up 6 convex pentagons. There is no way to cover up the remaining area, which has 3 concave vertices, using only 2 convex pentagons, so at least 3 more must be used. This gives us a lower bound of 9 which matches the upper bound of 9 earlier. $\blacksquare$
pic triangle_claim7.svg Illustration of Proposition 1 : The center area marked with a question mark cannot be cut into fewer than 3 convex pentagons.
# Conclusion
It is interesting to note that we have pretty much also shown that it takes 8 convex pentagons to cover a convex quadrilateral (e.g. a square). Generalizing this to larger convex polygons is less interesting though...
| Number of sides | Minimum number of convex pentagons |
| 3 | 9 |
| 4 | 8 |
| 5 | 1 |
| 6 | 2 |
| 7 | 2 |
| 8 | 2 |
| 9 | 3 |
| 10 | 3 |
Table of the minimum number of convex pentagons it is possible to cut an arbitrary convex polygon into.
And thereafter, for a convex polygon of $n$ sides, you can cut it into $\left\lceil \frac{n}{4} \right\rceil$ convex pentagons. This is because a convex pentagon can contribute at most 4 sides, the fifth being used for an internal edge (a cut).